Bubble Sort, Selection Sort, dan Shell Sort

Sorting bisa didefinisikan sebagai suatu pengurutan data yang sebelumnya disusun secara acak, sehingga menjadi tersusun secara teratur menurut aturan tertentu. sorting yang kita terapkan menggunakan tipe data array agar pemahaman serta pengimplementasiannya lebih mudah                                                                                 

Pada umumnya metode yang digunakan untuk sorting adalah :

1. Buble\Exchange sort

2. Selection sort

3. Shell Sort

4. Quick sort

Bubble/Exchange sort

Diberi nama "Bubble" karena proses pengurutan secara berangsur-angsur bergera/berpindah ke posisi yang tepat , seperti gelembung yang keluar dari sebuah gelas bersoda. Bubble sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya. jika elemen sekarang  lebih besar dari elemen berikutnya maka elemen tersebut ditukar (untuk pengurutan ascending) jika elemen sekarang lebih kecil daripada elemen berikutnya, maka kedua elemen  tersebut ditukar (untuk pengurutan descending). algoritma ini seolanh olah menggeser satu per satu elemen dari kenan ke kiri atau kiri ke kanan. tergantung jenis pengurutannya. Ketika suatu proses telah selesai, maka bubble sort akan mengalami proses, demikian seterusnya. Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan,serta tercapai pengurutan yang telah diinginkan

Contoh pengurutan data yang dilakukan dengan metode bubble sort sebagai berikut :

Proses 1 :
22 10 15 3 8 2
22 10 15 3 2 8
22 10 15 2 3 8
22 10 2 15 3 8
22 10 2 15 3 8

22 2 10 15 3 8
2 22 10 15 3 8

Pengecekan dimulai dari data yang paling akhir, kemudian dibandingkan dengan data di depannya,jika data didepannya lebih besar maka akan di tukar.

Proses 2:
2 22 10 15 3 8
2 22 10 15 3 8
2 22 10 3 15 8
2 22 3 10 15 8
2 3 22 10 15 8

pengecekan dilakukan sampai dengan data ke-2 karena data pertama pasti sudah paling kecil.

Proses 3 :
2 3 22 10 15 8
2 3 22 10 8 15
2 3 22 8 10 15
2 3 8 22 10 15

Proses 4 :
2 3 8 22 10 15
2 3 8 22 15 10
2 3 8 15 22 10

Proses 5 :
2 3 8 15 22 10
2 3 8 15 10 22

Pengurutan berhenti.

Contoh Program :

#include

#include

#include

bubble_acak()

{

clrscr();

int arr[1000];

int x, i; //untuk array

int s, t, temp; //untuk sorting

//input jumlah data yang diproses

cout<<"angka yang akan dimasukkan : "; cin>>x;

//input nilai masing" array

srand(time(NULL));

for (i=0; i

arr[i] = rand() %1000;

//output nilai" array

clrscr();

cout<<"====== array ======"<

cout<<"angka angkanya :"<

for (i=0; i

cout<

//sorting

cout<

cout<<"====== sorting ======"<

s = 0;

for (s=0; s

{

for (t = s+1; t

{

if (arr[s]>arr[t])

{

temp = arr[s];

arr[s] = arr[t];

arr[t] = temp;

}

}

}

cout<<"setelah sorting :"<

for (i=0; i

cout<

getch();

}

bubble_manual()

{

clrscr();

int arr[1000];

int x, i; //untuk array

int s, t, temp; //untuk sorting

//input jumlah data yang diproses

cout<<"angka yang akan dimasukkan : "; cin>>x;

//input nilai masing" array

for (i=0; i

{

cout<<"masukkan angka ke-"<

cin>>arr[i];

}

//output nilai" array

clrscr();

cout<<"====== array ======"<

cout<<"angka angkanya :"<

for (i=0; i

cout<

//sorting

cout<

cout<<"====== sorting ======"<

s = 0;

for (s=0; s

{

for (t = s+1; t

{

if (arr[s]>arr[t])

{

temp = arr[s];

arr[s] = arr[t];

arr[t] = temp;

}

}

}

cout<<"setelah sorting :"<

for (i=0; i

cout<

//mission complete

getch();

}

main ()

{

int pilih;

char ulang;

do

{

clrscr ();

cout<<"tekan 1 : bilangan yang disorting dimasukan secara acak"<

cout<<"tekan 2 : bilangan yang disorting dimasukan secara manual"<

cout<<"masukkan pilihan : "; cin>>pilih;

switch (pilih)

{

case 1:

bubble_acak();

break;

case 2:

bubble_manual();

break;

default:

clrscr();

cout<<"\"maaf\""<

cout<<"\"pilihan yang dimasukkan salah\"";

break;

}

cout< "; cin>>ulang;

}

Dalam Procedure Pascal :
Procedure Bubble(Var Temp : Data; JmlData : Integer);
Var I,J : Integer;
Begin
     For I:=2 To JmlData Do
            For J:=JmlData DownTo I Do
                     If Temp[J] < Temp[J-1] Then           {Untuk Descending
>}
                      SWAP(Temp[J], Temp[J-1]);
End;


Dalam Procedure SWAP :
Var Temp : Char;
 Begin
           Temp := A;
           A := B;
           B := Temp;
End;

Selection Sort

Cara kerja metode ini didasarkan pada pencarian elemen dengan nilai terkecil. kemudian dilakukan penukaran dengan elemen ke-I. Secara singkat metode ini bisa dijelaskan sebagai berikut. Pada langkah pertama, dicari data yang terkecil dari data pertama sampai terakhir. Kemudian data tersebut kita tukar dari data pertama. Dengan demikian, data pertama sekarang mempunyai nilai paling kecil dibanding dengan data lain. Pada langkah kedua, data terkecil kita cari mulai dari data kedua sampai data terakhir. Data terkecil yang kita peroleh kita tukar dengan data kedua. Demikian seterusnya sampai seluruh data terurut.

Contoh dari proses sorting dengan menggunakan metode Selection sort : 

Dalam Procedure Pascal :

Procedure Selection(Var Temp : Data; JmlData : Integer); 

Var I,J, Lok : Integer; 

      Begin 

            For I:=1 To JmlData-1 Do 

                Begin 

                     Lok:=I; 

                     For J:=I+1 To JmlData Do 

                     If Temp[Lok] > Temp[J] Then Lok:=J; 

                     SWAP(Temp[I], Temp[Lok]); 

                 End; 

      End; 

Shell Sort

Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959. Dalam metode ini jarak antara dua elemen  yang dibandingkan dan ditukarkan tertentu. Secara singkat metode ini dijelaskan sebagai berikut. Pada langkah pertama, kita ambil elemen pertama dan kita bandingkan dan kita bandingkan dengan elemen pada jarak tertentu dari elemen pertama tersebut. Kemudain elemen kedua kita bandingkan dengan eleen lain dengan jarak yang sama seperti jarak yang sama seperti diatas. Demikian seterusnya sampai seluruh elemen dibandingkan. Pada langkah kedua proses diulang dengan langkah yang lebih kecil, pada langkah ketiga jarak tersebut diperkecil lagi seluruh proses dihentikan jika jarak sudah sama dengan satu.

Contoh dari proses Sorting dengan menggunakan metode Shell Sort :

Dalam Procedure Pascal :

Procedure Shell(Var Temp : Data; JmlData : Integer); 

Var I,J, Jarak : Integer; 

        Begin 

             Jarak := JmlData Div 2; 

              While Jarak > 0 Do 

                    Begin 

                        For I:=1 To JmlData-Jarak Do 

                             Begin 

                                 J := I + Jarak; 

                                 If Temp[I] > Temp[J] Then  

                                 SWAP(Temp[I], Temp[Lok]); 

                             End; 

                             Jarak := Jarak Div 2; 

                    End; 

          End;

Quick Sort

Metode ini dikembangkan oleh CAR Hoare. Secara garis besar metode ini dijelaskan sebagai berikut. Misalnya kita ingin mengurutkan data A yang membunyai N elemen. Kita pilih sembarang elemen dari data tersebut, biasanya elemen pertama, misalnya X. Kemudain semua elemen tersebut disusun dengan menempatkan X pada posisi J sedemikian rupa shingga elemen ke 1 sampai ke J-1 mempuyai nilai lebih besar dari X. Sampai berikutnya diulang untuk  setiap sub data.

Contoh dari proses Soring dengan menggunakan metode Quick Sort

Dalam Procedure Pascal :

Procedure Quick(Var Temp : Data; Awal, Akhir : Integer); 

      Var I,J : Integer; 

       Procedure ATUR; 

                   Begin 

                   I:=Awal +1; 

                   J:= Akhir; 

                    While Temp[I] < Temp[Awal] Do Inc(I);

                   While Temp[J] > Temp[Awal] Do Dec(J); 

                   While I < J Do 

                         Begin 

                                SWAP(Temp[I], Temp[J]); 

                                While Temp[I] < Temp[Awal] Do Inc(I); 

                                While Temp[J] > Temp[Awal] Do Dec(J); 

                         End; 

                   SWAP(Temp[Awal], Temp[J]); 

End; 

                  Begin 

                      If Awal < Akhir Then 

                             Begin 

                                  ATUR; 

                                  Quick(Temp, Awal, J-1); 

                                  Quick(Temp,J+1,Akhir); 

                             End; 

End;