Analgo: ouick sort

Metode Quick

Metode Quick sering disebut juga metode partisi (partition exchange sort).Metode ini diperkenalkan pertama kali oleh C.A.R. Hoare pada tahun 1962.Untuk mempertinggi efektifitas dari metode ini, digunakan teknik menukarkan dua elemen dengan jarak yang cukup besar.

Proses penukaran dengan metode quick dapat dijelaskan sebagai berikut.: mula mula dipilih data tertentu yang disebut pivot, misalnya x. Pivot dipilih untuk mengatur data di sebelah kiri agar lebih kecil daripada pivot dan data di sebelah kanan agar lebih besar daripada pivot. Pivot ini diletakkan pada posisi ke j sedemikian sehingga data antara 1 sampai dengan j-1 lebih kecil daripada x. Sedangkan data pada posisi ke j+1 sampai N lebih besar daripada x. Caranya dengan menukarkan data diantara posisi 1 sampai dengan j-1 yang lebih besar daripada x dengan data diantara posisi j+1 sampai dengan N yang lebih kecil daripada x. Ilustrasi dari metode quick dapat dilihAat pada Gambar.

Gambar diatas menunjukkan pembagian data menjadi sub-subbagian. Pivotdipilih dari data pertama tiap bagian maupun sub bagian, tetapi sebenarnya kita bisa memilih sembarang data sebagai pivot. Dari ilustrasi diatas bisa kita lihat bahwa metodeQuick Sort ini bisa kita implementasikan menggunakan dua cara, yaitu dengan cara nonrekursif dan rekursif. Pada kedua cara diatas, persoalan utama yang perlu kita perhatikanadalah bagaimana kita meletakkan suatu data pada posisinya yang tepat sehinggamemenuhi ketentuan diatas dan bagaimana menyimpan batas-batas subbagian. Dengancara seperti yang diperlihatkan pada Gambar 6.1, kita hanya menggerakkan data pertamasampai di suatu tempat yang sesuai. Dalam hal ini kita hanya bergerak dari satu arahsaja.Untuk mempercepat penempatan suatu data, kita bisa bergerak dari dua arah, kiridan kanan. Caranya adalah sebagai berikut : misalnya kia mempunyai 10 data (N=9) :

12 35 9 11 3 17 23 15 31 20

i=0 j=9

Pertama kali ditentukan i=0 (untuk bergerak dari kiri ke kanan), dan j=N (untuk bergerak dari kanan ke kiri). Proses akan dihentikan jika nilai i lebih besar atau sama dengan j.Sebagai contoh, kita akan menempatkan elemen pertama, 12 pada posisinya yang tepat dengan bergerak dari dua arah, dari kiri ke kanan dan dari kanan ke kiri secarabergantian. Dimulai dari data terakhir bergerak dari kanan ke kiri (j dikurangi 1),dilakukan pembandingan data sampai ditemukan data yang nilainya lebih kecil dari 12yaitu 3 dan kedua elemen data ini kita tukarkan sehingga diperoleh

3 35 9 11 12 17 23 15 31 20

i=0 j=4

Setelah itu bergerak dari kiri ke kanan dimulai dari data 3 (i ditambah 1), dilakukanpembandingan pada setiap data yang dilalui dengan 12, sampai ditemukan data yang nilainya lebih besar dari 12 yaitu 35. Kedua data kita tukarkan sehingga diperoleh

3 12 9 11 35 17 23 15 31 20

i=1 j=4

Berikutnya bergerak dari kanan ke kiri dimulai dari 11. Dan ternyata data 11 lebih kecil dari 12, kedua data ini ditukarkan sehingga diperoleh

3 11 9 12 35 17 23 15 31 20

i=1 j=3

Kemudian dimulai dari 9 bergerak dari kiri ke kanan. Pada langkah ini ternyata tidakditemukan data yang lebih besar dari 12 sampai nilai i=j. Hal ini berarti proses penempatan data yang bernilai 12 telah selesai, sehingga semua data yang lebih kecil dari 12 beradadi sebelah kiri dan data yang lebih besar dari 12 berada di sebelah kanan seperti terlihat di bawah ini