Teknik Sorting (Quick Sort)
Metode Lower Bound (LB) & Upper Bound (UP)
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. Untuk menyelesaikan penguruta dengan Quick Sort selain menggunakan metode diatas, ada juga metode yang lain yaitu menggunakan metode penentuan nilai PIVOT.
Tags:
