Sorting bisa didefinisikan sebagai suatu proses pengurutan data yang sebelumnya disusun secara acak sehingga menjadi tersusun secara teratur menurut suatu aturan tertentu. Sorting yang kita terapkan menggunakan tipe data array agar pemahaman serta pengimplementasiannya lebih mudah. Pada umumnya terdapat dua jenis pengurutan :
§ Ascending (Naik).
§ Descending (Turun).
Contoh :
Data : Array [1..6] of Byte = (22, 10, 15, 3, 8, 2);
Data Acak : 22 10 15 3 8 2
Terurut Ascending : 2 3 8 10 15 22
Terurut Descending : 22 15 10 8 3 2
Untuk melakukan proses pengurutan tersebut dapat digunakan berbagai macam cara/metode.
Beberapa metode yang sudah umum digunakan diantaranya adalah :
1. Bubble / Exchange Sort
2. Selection Sort.
3. Shell Sort.
4. Quick Sort.
· Pengurutan berdasarkan perbandingan (comparison-based sorting)
� Bubble sort, exchange sort
· Pengurutan berdasarkan prioritas (priority queue sorting method)
� Selection sort, heap sort
· Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep sorted method)
� Insertion sort, tree sort
· Pengurutan berdasarkan pembagian dan penguasaan (devide and conquer method)
� Quick sort, merge sort
· Pengurutan berkurang menurun (diminishing increment sort method)
� Shell sort
7.2. Bubble/Exchange Sort
Metode ini merupakan metode yang paling sederhana dan paling tidak efisien, karena memerlukan waktu yang relatif lebih lama dibandingkan dengan metode-metode yang lainnya. Konsep dasar dari Bubble sort ialah membandingkan elemen yang sekarang degan elemen yang berikutnya, jika elemen sekarang > elemen berikutnya (untuk ascending), maka dilakukan proses penukaran. Proses sorting dapat dimulai dari data awal atau data akhir. Contoh dari proses Sorting dengan menggunakan metode Bubble Sort :
Iterasi Ke | A[1] | A[2] | A[3] | A[4] | A[5] | A[6] |
Awal | 22 | 10 | 15 | 3 | 2 | 8 |
1 | 10 | 22 | 15 | 3 | 2 | 8 |
10 | 15 | 22 | 3 | 2 | 8 | |
10 | 15 | 3 | 22 | 2 | 8 | |
10 | 15 | 3 | 2 | 22 | 8 | |
10 | 15 | 3 | 2 | 8 | 22 | |
2 | 10 | 15 | 3 | 2 | 8 | 22 |
10 | 3 | 15 | 2 | 8 | 22 | |
10 | 3 | 2 | 15 | 8 | 22 | |
10 | 3 | 2 | 8 | 15 | 22 | |
10 | 3 | 2 | 8 | 15 | 22 | |
3 | 3 | 10 | 2 | 8 | 15 | 22 |
3 | 2 | 10 | 8 | 15 | 22 | |
3 | 2 | 8 | 10 | 15 | 22 | |
3 | 2 | 8 | 10 | 15 | 22 | |
3 | 2 | 8 | 10 | 15 | 22 | |
4 | 2 | 3 | 8 | 10 | 15 | 22 |
2 | 3 | 8 | 10 | 15 | 22 | |
2 | 3 | 8 | 10 | 15 | 22 | |
2 | 3 | 8 | 10 | 15 | 22 | |
2 | 3 | 8 | 10 | 15 | 22 | |
5 | 2 | 3 | 8 | 10 | 15 | 22 |
2 | 3 | 8 | 10 | 15 | 22 | |
2 | 3 | 8 | 10 | 15 | 22 | |
2 | 3 | 8 | 10 | 15 | 22 | |
2 | 3 | 8 | 10 | 15 | 22 | |
Akhir | 2 | 3 | 8 | 10 | 15 | 22 |
Disini terlihat ketidak efisienan dari bubble sort yaitu harus menyelesaikan JumMax –1 dari data. Sedangkan jika kita melihat dari tabel diatas pada iterasi ke empat saja data sudah terurut dan seharusnya pada saat itu proses sudah berhenti, tapi dengan bubble sort proses harus dilakukan sampai looping selesai.
Pada seluruh prosedur yang menggunakan metode sorting pasti memerlukan prosedur tambahan tukar data (Swap) untuk menukarkan dua buah elemen dalam data.
Berikut ini merupakan prosedur untuk menukarkan dua buah data.
Procedure SWAP(Var A,B : Char);
Var Temp : Char;
Begin
Temp := A;
A := B;
B := Temp;
End;
Berikut ini merupakan Procedure BubbleSort pada 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;
7.3. 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 data terakhir. Kemudian data tersebut kita tukar dengan data pertama. Dengan demikian, data pertama sekarang mempunyai nilai paling kecil dibanding 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 suluruh data terurut.
Contoh dari proses Sorting dengan menggunakan metode Selection Sort :
Iterasi Ke | A[1] | A[2] | A[3] | A[4] | A[5] | A[6] |
Awal | 22 | 10 | 15 | 3 | 2 | 8 |
I=1, Lok=5 | 2 | 10 | 15 | 3 | 22 | 8 |
I=2, Lok=4 | 2 | 3 | 15 | 10 | 22 | 8 |
I=3, Lok=6 | 2 | 3 | 8 | 10 | 22 | 15 |
I=4, Lok=4 | 2 | 3 | 8 | 10 | 22 | 15 |
I=5, Lok=6 | 2 | 3 | 8 | 10 | 15 | 22 |
Akhir | 2 | 3 | 8 | 10 | 15 | 22 |
Berikut ini merupakan Procedure Selection Sort pada 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;
7.4. 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 dengan elemen pada jarak tertentu dari elemen pertama tersebut. Kemudian elemen kedua kita bandingkan dengan elemen lain dengan 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 Selection Sort :
Jarak | A[1] | A[2] | A[3] | A[4] | A[5] | A[6] |
Awal | 22 | 10 | 15 | 3 | 2 | 8 |
Jarak = 3 | 22 | 10 | 15 | 3 | 2 | 8 |
3 | 10 | 15 | 22 | 2 | 8 | |
3 | 2 | 15 | 22 | 10 | 8 | |
3 | 2 | 8 | 22 | 10 | 15 | |
Jarak = 1 | 3 | 2 | 8 | 22 | 10 | 15 |
2 | 3 | 8 | 22 | 10 | 15 | |
2 | 3 | 8 | 22 | 10 | 15 | |
2 | 3 | 8 | 22 | 10 | 15 | |
2 | 3 | 8 | 10 | 22 | 15 | |
2 | 3 | 8 | 10 | 15 | 22 | |
Akhir | 2 | 3 | 8 | 10 | 15 | 22 |
Berikut ini merupakan Procedure ShellSort pada 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;
7.5. Quick Sort
Metode ini dikembangkan oleh C.A.R Hoare. Secara garis besar metode ini dijelaskan sebagai berikut. Misalnya kita ingin mengurutkan data A yang mempunyai N elemen. Kita pilih sembarang elemen dari data tersebut, bisanya elemen pertama, misalnya X. kemudian semua elemen tersebut disusun dengan menempatkan X pada posisi J sedemikian rupa sehingga elemen ke 1 sampai ke J-1 mempunyai nilai lebih kecil dari X dan elemen J+1 sampai ke N mempunyai nilai lebih besar dari X. Sampai saat ini kita sudah mempunyai dua sub data (kiri dan kanan). Langkah berikutnya diulang untuk setiap sub data. Contoh dari proses Sorting dengan menggunakan metode Quick Sort :
Proses Sorting :
Berikut ini merupakan Procedure QuickSort pada 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;
Tidak ada komentar:
Posting Komentar