Searching

Sequental Search dan Binary Search


A.              Squental search

Adalah suatu teknik pencarian data dalam array (1 dimensi)yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu. Pencarian berurutan menggunakan prinsip sebagai berikut : data yang ada dibandingkan satu per satu secara berurutan dengan yang dicari sampai data tersebut ditemukan atau tidak ditemukan.

B.               Binary search

Sebuah algoritma pencarian biner (atau pemilahan biner) adalah sebuah teknik untuk menemukan nilai tertentu dalam sebuah larik (array) linear, dengan menghilangkan setengah data pada setiap langkah, dipakai secara luas tetapi tidak secara ekslusif dalam ilmu Komputer. Sebuah pencarian biner mencari nilai tengah (median), melakukan sebuah pembandingan untuk menentukan apakah nilai yang dicari ada sebelum atau sesudahnya, kemudian mencari setengah sisanya dengan cara yang sama. Sebuah pencarian biner adalah salah satu contoh dari algoritma divide and conquer (atau lebih khusus algoritma decrease and conquer) dan sebuah pencarian dikotomi (lebih rinci di Algoritma pencarian).
Penerapan terbanyak dari pencarian biner adalah untuk mencari sebuah nilai tertentu dalam sebuah list terurut. Jika dibayangkan, pencarian biner dapat dilihat sebagai sebuah permainan tebak-tebakan, kita menebak sebuah bilangan, atau nomor tempat, dari daftar (list) nilai.
Pencarian diawali dengan memeriksa nilai yang ada pada posisi tengah list; oleh karena nilai-nilainya terurut, kita mengetahui apakah nilai terletak sebelum atau sesudah nilai yang di tengah tersebut, dan pencarian selanjutnya dilakukan terhadap setengah bagian dengan cara yang sama.

Binary Search dengan C++

Pencarian Biner (Binary Search) dilakukan untuk :

•     Memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya.

•     Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).

•     Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.

Keunggulan Binary Search 

Keunggulan utama dari algoritma binary search adalah kompleksitas 

algoritmanya yang lebih kecil daripada kompleksitas algoritma sequential search. Hal ini menyebabkan waktu yang dibutuhkan algoritma binary search dalam mencari sebuah record dalam sebuah tabel lebih kecil daripada waktu yang dibutuhkan algoritma sequential search

===============================================================

Contoh Program Squental Search :

#include <conio.h>
#include <iostream.h>
main(){
int c,i,posisi;
int A[20]={3,2,4,10,20,1,5,8,7,9,6,5,11,12,14,13,16,15,17,19};


cout<<"Data : ";
for(i=0;i<20;i++){
 cout<<A[i]<<" ";
}

cout<<"\nData yang ingin dicari : ";
cin>>c;
i=0;
posisi=0;
while(i<19 && A[i]!=c){
 i++;
}
if (A[i]!=c){
 cout<<"Maaf data yang dicari tidak ada";
}else if(posisi=i+1)
   cout<<"ditemukan pada posisi ke "<<posisi;
getch();
}

===============================================================

Contoh Program Binary Search :

#include <iostream.h>
#include <conio.h>

main ()
{
    int jd, cari,no, kiri,kanan,tengah,data[50];

   cout<<"\n\t\t *************************************** \n";
   cout<<"\t\t | \t\t\t\t       | \n";
   cout<<"\t\t | \t     Proses Pencarian \t       | \n";
   cout<<"\t\t | Menggunakan Algoritma Binary Search | \n";
   cout<<"\t\t | \t\t\t\t       | \n";
   cout<<"\t\t *************************************** \n\n\n";

   cout<<" Input Jumlah Data  : ";
   cin>>jd;

   cout<<endl;
    for (no=0;no<jd;no++)
    {
        cout<<" Input Data Ke-"<<(no+1)<<"    : ";
       cin>>data[no];
    }

   cout<<endl;
    cout<<" Input Nilai Dicari : ";
    cin>>cari;

    kiri=0;
    kanan=jd-1;
    tengah=(kanan-kiri)/2;

    while ((data[tengah]!=cari) && (kiri>=0)&& (kanan<jd) && (kanan>=kiri))
    {
        if (cari>data[tengah])
       {
           kiri=tengah+1;
       }
       else if (cari<data[tengah])
       {
           kanan=tengah-1;
       }
       tengah=kiri+(kanan-kiri)/2;
    }

   cout<<endl;
   if (data[tengah]==cari)
    {
        cout<<" Keterangan         : Data Ditemukan";
    }
    else
    {
        cout<<" Keterangan         : Data Tidak Ditemukan";
    }

    getch();
}


please visit the link :
http://www.stikom-bali.ac.id/

Sorting

 Selection Sort, Insertion Sort, dan Bubble Sort

1.       Selection sort

Adalah metode sorting dimana elemen- elemen di perbandingkan satu-persatu sampai pada elemen terakhir dan disusun berdasarkan ketentuan ketentuan berlaku (terbesar atau terkecil).

2.       Insertion sort

Insertion sort adalah metode pengurutan dengan cara menyisipkan elemen larik pada posisi yang tepat.

3.       Bubble sort

Bubble sort (metode gelembung) adalah metode/algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat.

Metode pengurutan gelembung (Bubble Sort) diinspirasikan oleh gelembung sabun yang berada dipermukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan. Prinsip di atas dipakai pada pengurutan gelembung.

Algoritma bubble sort adalah salah satu algoritma pengurutan yang paling simple, baik dalam hal pengertian maupun penerapannya. Ide dari algoritma ini adalah mengulang proses pembandingan antara tiap-tiap elemen array dan menukarnya apabila urutannya salah. Pembandingan elemen-elemen ini akan terus diulang hingga tidak perlu dilakukan penukaran lagi. Algoritma ini termasuk dalam golongan algoritma comparison sort, karena menggunakan perbandingan dalam operasi antar elemennya.

Berikut ini adalah gambaran dari algoritma bubble sort. Misalkan kita mempunyai sebuah array dengan.  Elemen-elemen “4 2 5 3 9”.

Proses yang akan terjadi apabila digunakan algoritma bubblesort adalah sebagai berikut :

Pass pertama

(4 2 5 3 9) menjadi (2 4 5 3 9)

(2 4 5 3 9) menjadi (2 4 5 3 9)

(2 4 5 3 9) menjadi (2 4 3 5 9)

(2 4 3 5 9) menjadi (2 4 3 5 9)

Pass kedua

(2 4 3 5 9) menjadi (2 4 3 5 9)

(2 4 3 5 9) menjadi (2 3 4 5 9)

(2 3 4 5 9) menjadi (2 3 4 5 9)

(2 3 4 5 9) menjadi (2 3 4 5 9)

Pass ketiga

(2 3 4 5 9) menjadi (2 3 4 5 9)

(2 3 4 5 9) menjadi (2 3 4 5 9)

(2 3 4 5 9) menjadi (2 3 4 5 9)

(2 3 4 5 9) menjadi (2 3 4 5 9)

Dapat dilihat pada proses di atas, sebenarnya pada pass kedua, langkah kedua, array telah terurut. Namun algoritma tetap dilanjutkan hingga pass kedua berakhir. Pass ketiga dilakukan karena definisi terurut dalam algoritma bubblesort adalah tidak ada satupun penukaran pada suatu pass, sehingga pass ketiga dibutuhkan untuk memverifikasi keurutan array tersebut.

B.      Algoritma Bubble Sort

1.    Membandingkan data ke-i dengan data ke-(i+1) (tepat bersebelahan). Jika tidak sesuai maka tukar (data ke-i = data ke-(i+1) dan data ke-(i+1) = data ke-i). Apa maksudnya tidak sesuai? Jika kita menginginkan algoritme menghasilkan data dengan urutan ascending (A-Z) kondisi tidak sesuai adalah data ke-i > data ke-i+1, dan sebaliknya untuk urutan descending (A-Z).

2.    Membandingkan data ke-(i+1) dengan data ke-(i+2). Kita melakukan pembandingan ini sampai data terakhir. Contoh: 1 dgn 2; 2 dgn 3; 3 dgn 4; 4 dgn 5 … ; n-1 dgn n.

3.    Selesai satu iterasi, adalah jika kita sudah selesai membandingkan antara (n-1) dgn n. Setelah selesai satu iterasi kita lanjutkan lagi iterasi berikutnya sesuai dengan aturan ke-1. mulai dari data ke-1 dgn data ke-2, dst.

4.    Proses akan berhenti jika tidak ada pertukaran dalam satu iterasi.

Contoh Kasus Bubble Sort :

Misalkan kita punya data seperti ini: 6, 4, 3, 2 dan kita ingin mengurutkan data ini (ascending) dengan menggunakan bubble sort. Berikut ini adalah proses yang terjadi:

Iterasi ke-1: 4, 6, 3, 2 :: 4, 3, 6, 2 :: 4, 3, 2, 6 (ada 3 pertukaran)

Iterasi ke-2: 3, 4, 2, 6 :: 3, 2, 4, 6 :: 3, 2, 4, 6 (ada 2 pertukaran)

Iterasi ke-3: 2, 3, 4, 6 :: 2, 3, 4, 6 :: 2, 3, 4, 6 (ada 1 pertukaran)

Iterasi ke-4: 2, 3, 4, 6 :: 2, 3, 4, 6 :: 2, 3, 4, 6 (ada 0 pertukaran) -> proses selesai

C.      Kompleksitas Algoritma Bubble Sort

Kompleksitas Algoritma Bubble Sort dapat dilihat dari beberapa jenis kasus, yaitu worst-case, average-case, dan best-case.

• Kondisi Best-Case

Dalam kasus ini, data yang akan disorting telah terurut sebelumnya, sehingga proses perbandingan hanya dilakukan sebanyak (n-1) kali, dengan satu kali pass.

Proses perbandingan dilakukan hanya untuk memverifikasi keurutan data. Contoh Best-Case dapat dilihat pada pengurutan data “1 2 3 4” di bawah ini.

Pass Pertama

(1 2 3 4) menjadi (1 2 3 4)

(1 2 3 4) menjadi (1 2 3 4)

(1 2 3 4) menjadi (1 2 3 4)

Dari proses di atas, dapat dilihat bahwa tidak terjadi penukaran posisi satu kalipun, sehingga tidak dilakukan pass selanjutnya. Perbandingan elemen dilakukan sebanyak tiga kali. Proses perbandingan pada kondisi ini hanya dilakukan sebanyak (n-1) kali. Persamaan Big-O yang diperoleh dari proses ini adalah O(n). Dengan kata lain, pada kondisi Best-Case algoritma Bubble Sort termasuk pada algoritma

lanjar.

• Kondisi Worst-Ca

Dalam kasus ini, data terkecil berada pada ujung array. Contoh Worst-Case dapat dilihat pada pengurutan data “4 3 2 1” di bawah ini.

Pass Pertama

(4 3 2 1) menjadi (3 4 2 1)

(3 4 2 1) menjadi (3 2 4 1)

(3 2 4 1) menjadi (3 2 1 4)

Pass Kedua

(3 2 1 4) menjadi (2 3 1 4)

(2 3 1 4) menjadi (2 1 3 4)

(2 1 3 4) menjadi (2 1 3 4)

Pass Ketiga

(2 1 3 4) menjadi (1 2 3 4)

(1 2 3 4) menjadi (1 2 3 4)

(1 2 3 4) menjadi (1 2 3 4)

Pass Keempat

(1 2 3 4) menjadi (1 2 3 4)

(1 2 3 4) menjadi (1 2 3 4)

(1 2 3 4) menjadi (1 2 3 4)

Dari langkah pengurutan di atas, terlihat bahwa setiap kali melakukan satu pass, data terkecil akan bergeser ke arah awal sebanyak satu step. Dengan kata lain, untuk menggeser data terkecil dari urutan keempat menuju urutan pertama, dibutuhkan pass sebanyak tiga kali, ditambah satu kali pass untuk memverifikasi. Sehingga jumlah proses pada kondisi best case dapat dirumuskan sebagai berikut. Jumlah proses = n2+n (3)

Dalam persamaan (3) di atas, n adalah jumlah elemen yang akan diurutkan. Sehingga notasi Big-O yang didapat adalah O(n2). Dengan kata lain, pada kondisi worst-case, algoritma Bubble Sort termasuk dalam kategori algoritma kuadratik.

• Kondisi Average-Case

Pada kondisi average-case, jumlah pass ditentukan dari elemen mana yang mengalami penggeseran ke kiri paling banyak. Hal ini dapat ditunjukkan oleh proses pengurutan suatu array, misalkan saja (1 8 6 2). Dari (1 8 6 2), dapat dilihat bahwa yang akan mengalami proses penggeseran paling banyak adalah elemen 2, yaitu sebanyak dua kali.

Pass Pertama

(1 8 6 2) menjadi (1 8 6 2)

(1 8 6 2) menjadi (1 6 8 2)

(1 6 8 2) menjadi (1 6 2 8)

Pass Kedua

(1 6 2 8) menjadi (1 6 2 8)

(1 6 2 8) menjadi (1 2 6 8)

(1 2 6 8) menjadi (1 2 6 8)

Pass Ketiga

(1 2 6 8) menjadi (1 2 6 8)

(1 2 6 8) menjadi (1 2 6 8)

(1 2 6 8) menjadi (1 2 6 8)

Dari proses pengurutan di atas, dapat dilihat bahwa untuk mengurutkan diperlukan dua buah passing, ditambah satu buah passing untuk memverifikasi. Dengan kata lain, jumlah proses perbandingan dapat dihitung sebagai berikut. Jumlah proses = x2+x (4) Dalam persamaan (4) di atas, x adalah jumlah penggeseran terbanyak. Dalam hal ini, x tidak pernah lebih besar dari n, sehingga x dapat dirumuskan sebagai

Dari persamaan (4) dan (5) di atas, dapat disimpulkan bahwa notasi

big-O nya adalah O(n2). Dengan kata lain, pada kondisi average case algoritma Bubble Sort termasuk dalam algoritma kuadratik.

D.      Implementasi dalam Pseudo-Code

Setiap algoritma akan memiliki implementasi yang berbeda, tergantung dari bahasa program yang dipakai. Oleh karena itu berikut ini adalah pseudo-code dari algoritma bubblesort, untuk memudahkan implementasi bubblesort pada bahasa apapun.

procedure bubbleSort( A : list of

sortable items ) defined as:

do

swapped := false

for each i in 0 to length(A) - 2

inclusive do:

if A[i] > A[i+1] then

swap( A[i], A[i+1] )

swapped := true

end if

end for

while swapped

end procedure

E.       Kelebihan dan Kelemahan Bubble Sort

Kelebihan :

·      Metode Buble Sort merupakan metode yang paling simpel

·      Metode Buble Sort mudah dipahami algoritmanya

Kelemahan:

Meskipun simpel metode Bubble sort  merupakan metode pengurutan yang paling tidak efisien.  Kelemahan buble sort adalah pada saat mengurutkan data yang sangat besar akan mengalami kelambatan luar biasa, atau dengan kata lain kinerja memburuk cukup signifikan ketika data yang diolah jika  data cukup banyak. Kelemahan lain adalah jumlah pengulangan akan tetap sama jumlahnya walaupun data sesungguhnya sudah cukup terurut. Hal ini disebabkan setiap data dibandingkan dengan setiap data yang lain untuk menentukan posisinya. 

==========================================================================

Contoh Program Selection Sort :
#include <iostream.h>
#include <conio.h>
main()
{
    int i,j,data[10],simpan,min,posisi;

   for(i=0;i<5;i++)
   {
       cout<<"data "<<i<<" = ";
      cin>>data[i];
   }
   for(i=0;i<5;i++)
   {
       for(j=i+1;j<5;j++)
      {
            if(data[i]>data[j])
         {
              simpan=data[i];
              data[i]=data[j];
              data[j]=simpan;
         }
      }
   }
   cout<<"hasil= ";
   for(i=0;i<5;i++)
       cout<<data[i]<<" ";

getch();
}

==========================================================================

Contoh Program Insertion Sort :
 #include <iostream.h>
    int n,i,j,k,data[20],simpan;

    void main(){
    cout<<"Masukkan banyak data = ";cin>>n;
    for(i=1;i<=n;i++)
    {
     cout<<"Data ke-"<<i<<" = ";cin>>data[i];
    }

    cout<<endl<<"Perhitungan Eksekusi program :"<<endl;
    cout<<"awal = \n";
    for(i=1;i<=n;i++)
     cout<<data[i]<<"  ";
    cout<<endl<<endl;

    for(i=2;i<=n;i++)
    {
     j=i;
     while (j>0&&data[j]<data[j-1])
       {
      simpan=data[j];
      data[j]=data[j-1]; 
      data[j-1]=simpan;
      j--; 
     
          for(k=1;k<=n;k++) 
       cout<<data[k]<<"  ";
        cout<<endl; 
       }
    } 
     
    cout<<endl<<"Insertion Sort :"<<endl;
     
    for(i=1;i<=n;i++) 
     cout<<data[i]<<"  ";
    getch(); 
    }

==========================================================================

Contoh Program Bubble Sort :

#include<iostream>
using namespace std;

int main()
{   int a,k,c,d,g;
    k=4;
    int b[4];

    cout<<"BUBBLE SORT BY ZEFTAADETYA.BLOGSPOT.COM"<<endl;
    cout<<"mengurutkan nilai dari besar ke kecil"<<endl<<endl;
    for(a=0;a<k;a++)
    {
        cout<<"Masukkan nilai "<<a+1<<" : ";cin>>b[a];
    }
    for(a=0;a<k-1;a++)
    {

        for(d=a+1;d<k;d++)
        {
        c=a;
            if(b[c]<b[d])
            {
                c=d;
            }
        g=b[c];
        b[c]=b[a];
        b[a]=g;
        }

    }
    cout<<"\n setelah diurutkan akan menjadi : \n";
    for(a=0;a<k;a++)
    {
        cout<<b[a]<<" \n";
    }
}


please visit the link :
http://www.stikom-bali.ac.id/

Queue, Enqueue, dan Dequeue

A.               Queue

             Queue adalah antrian, dimana data yang datang pertama kali akan dipanggil pertama kali juga. 

Dalam queue sendiri terdapat beberapa operasi , yaitu :

·                       IsEmpty : Mengecek apakah queue kosong atau tidak

·                   IsFull : Mengecek apakah queue sudah penuh atau belum

·                   Enqueue : Menambahkan data di queue

·                   Dequeue : Mengambil data dari queue

·                   Clear : Menghapus data dalam antrian

·                   View : melihat data dalam antrian

Berbeda dengan stack, queue mempunyai 2 kata kunci, yaitu tail dan head.  Fungsi nya buat apa? Head adalah penanda urutan paling depan, sedangkan tail adalah penanda urutan paling belakang.  Karena jumlah operasinya banyak, kita kerjakan secara modular aja ya biar lebih mudah.

1.       Deklarasi Awal Queue

Variabel yang akan digunakan adalah data (array sebagai tempat queue), head, tail.  Sama seperti Stack, Nilai dari head dan tail dimulai dari -1 yang menandakan queue kosong.  Sebagai contoh kita akan membuat queue dengan data maksimal sebanyak 7 data.

2.       IsEmpty

Sama seperti di Stack, IsEmpty berguna untuk mengecek apakah queue kosong atau tidak.  Indikator bahwa queue kosong adalah nilai dari head dan tail bernilai -1.  Sehingga kita tinggal buat fungsi nya sebagai berikut :

3.       IsFull

Operasi IsFull digunakan untuk mengecek apakah queue sudah penuh atau belum.  Indikator kalau queue penuh adalah nilai tail = max – 1.  Mengapa? karena nilai maksimal pada array yang mempunyai index 7 pada saat diakses akan mempunyai nilai maksimal   

B.               Enqueue

Enqueue digunakan untuk memasukkan data kedalam queue.  Sama seperti push dalam stack.  Sebelum memasukkan data kedalam antrian, kita harus mengecek terlebih dahulu apakah queue / antrian sudah penuh atau belum.  Kalau belum maka kita harus mengecek apakah head sudah berada pada nilai 0 atau belum.  Ini sangat penting karena nilai head tidak akan lebih dari 0.  PERLU DIPERHATIKAN !  Yang akan bergerak terus adalah tail, sedangkan head hanya penunjuk urutan paling depan, sehingga nilainya tidak pernah lebih dari 0.  Kecuali antrian kosong, maka posisi head dan tail akan kembali menjadi -1.

Proses Enqueue

Saat memasukkan data pertama kali, maka nilai head dan tail berubah menjadi 0. Tetapi saat data yang dimasukkan sudah lebih dari 1 kali, maka yang akan terus berubah adalah tail, sedangkan nilai head tetap.

C.               Dequeue

Kebalikan dari fungsi enqueue, dequeue digunakan untuk mengambil data yang sudah masuk di urutan pertama.  Sehingga kita tinggal membaca data yang ada di posisi head.  Nah inilah fungsi dari head.  Jangan lupa kita cek dulu apakah queue kosong atau tidak.  Tapi jika ada isinya, setelah data diambil, data dibelakangnya digeser ke depan.

·               Clear

Operasi clear digunakan untuk menghapus data yang ada di dalam queue.  Caranya cukup merubah nilai pada head dan tail menjadi -1.  Tidak perlu diperhatikan data yang ada di dalam array

·               View

Operasi ini digunakan untuk melihat data yang ada didalam queue.  Caranya adalah dengan membaca data pada index yang terdapat diantara head sampai tail

Contoh Program :
#include <conio.h>
#include <iostream.h>


int tail, max, head;
int data[5];
int menu;

void create()
{
    tail = -1;
   head = 0;
   max = 4;
}
bool isfull()
{
    if (tail==max)
   {
       return true;
   }
   else
   {
       return false;
   }
}
bool isempty()
{
     if(tail<head) // tail == -1
   {
       return true;
   }
   else
   {
       return false;
   }
}
void clear()
{
    tail=-1;
}

void main()
{
    create(); // panggil dulu prosedur create
    home:
   clrscr();
    cout<<"Silahkan pilih salah satu"<<endl;
   cout<<"=========================="<<endl;
   cout<<"1. EnQueue"<<endl;  // sama dengan (push) +
   cout<<"2. DeQueue"<<endl;  // sama dengan (pop) -
   cout<<"3. Print"<<endl;
   cout<<"4. Clear"<<endl;
   cout<<"Pilih salah satu (1-4) : ";
   cin>>menu;

   switch(menu)
   {
       case 1:
          if (isfull()==true)
         {
             cout<<"Antrian Penuh";
         }
         else
         {
             tail++;
            cout<<"Masukan data ke - antrian : ";
            cin>>data[tail];
         }
          getch();
         goto home;
      break;

      case 2:
          if(isempty()==true)
         {
             cout<<"Antrian kosong";
         }
         else
         {
             cout<<"Data yang keluar adalah : ";
            cout<<data[head];
            for (int i=0; i<tail; i++)
            {
                data[i] = data[i+1];
            }
            tail--;
         }
         getch();
         goto home;
      break;

      case 3:
            if(isempty()==true)
            {
                cout<<"Antrian kosong";
            }
            else
                cout<<"Isi data pada antrian : ";
               for(int i=head; i<=tail; i++)
               {
                   cout<<data[i]<<" ";
               }

            getch();
            goto home;
      break;
   }
    getch();
}

 

please visit the link :
http://www.stikom-bali.ac.id/