Teknik Sorting (Quick Sort)
02/01/2013 15:07
Quick Sort merupakan suatu algoritma pengurutan data yang menggunakan teknik pemecahan data menjadi partisi-partisi (menjadi dua bagian) dengan menentukan batas bawah (Lower Bound-LB), batas atas (Upper Bound-UB) sehingga metode ini disebut juga dengan nama partition exchange sort. Untuk memulai irterasi pengurutan, pertama-tama sebuah elemen dipilih dari data, kemudian elemen-elemen data akan diurutkan diatur sedemikian rupa, sehingga nilai variabel Sementara berada di suatu posisi ke I yang memenuhi kondisi sebagai berikut :
Sort dgn iterasi secara urut dari posisi elemen 1, ke-2 dan seterusnya. Tukarkan setiap elemen pada posisi tersebut dengan elemen lain yang nilainya memang seharusnya berada pada posisi tersebut.
Prinsip Kerja dari Quick Sort adalah :
- Tentukan Lower Bound (Batas Bawah) & Upper Bound (Batas Atas)
- Bandingkan Lower Bound (LB) dengan Upper Bound (UB)
- Jika LB>UB, Tukar (cari operasi perbandingan yang optimal/terkecil)
- Jika LB =< UB, maka Next Upper Bound & Lower Bound
Ulangi langkah diatas s/d sort.
Terdapat kumpulan bilangan dengan data sebagai berikut:
25 10 30 15 5 35 28
Berikut langkah-langkah dalam pengurutan dengan menggunakan metode Quick Sort.
Tentukan Lower Bound (Batas Bawah) & Upper Bound (Batas Atas)
25 10 30 15 5 35 28
LB UB
Bandingkan Lower Bound (LB) dengan Upper Bound (UB)--> kerjakan langkah ke-3 dan ke-4
25 > 28 (Tidak), maka tidak terjadi pertukaran dan UB bergeser ke index sebelumnya (35)
25 > 35 (Tidak), maka tidak terjadi pertukaran dan UB bergeser ke index sebelumnya (5)
25 > 5 (Ya), maka terjadi pertukaran, sehingga urutannya menjadi
5 10 30 15 25 35 28
30 > 28 (Ya), maka terjadi pertukaran, sehingga urutannya menjadi
5 10 28 15 25 35 30
28 > 25 (Ya), maka terjadi pertukaran, sehingga urutannya menjadi
5 10 25 15 28 35 30
25 > 15 (Ya), maka terjadi pertukaran, sehingga urutannya menjadi
5 10 15 28 25 35 30
28 > 25 (Ya), maka terjadi pertukaran, sehingga urutannya menjadi
5 10 15 25 28 35 30
35 > 30 (Ya), maka terjadi pertukaran, sehingga urutannya menjadi
5 10 15 25 28 30 35 (sudah terurut)
Bagaimana...pengurutan dengan menggunakan metode quick sort ini, mudah bukan. Silahkan perbanyak latihan dengan deret bilangan lainnya.