Metode Quick Sort

Metoda quick sort dikenalkan pertama kali oleh C.A.R. Hoare pada tahun 1962. Metode ini sering juga disebut metoda partition exchange sort .

Dasar strateginya adalah "memecah dan menguasai". Quicksort dimulai dengan menscan daftar yang disortir untuk nilai median. Nilai median ini selanjutnya disebut tumpuan (pivot), kemudian dipindahkan ke satu sisi pada daftar dan butir-butir yang nilainya lebih besar dari tumpuan di pindahkan ke sisi lain. Dalam perkembangannnya nilai yang digunakan sebagai pivot tidak harus nilai median namun bisa sembarang nilai dalam data tersebut.

Misalkan ingin mengurutkan data sebanyak N elemen maka kita memilih salah satu nilai yang akan digunakan sebagai pivot dalam hal ini digunakan nilai paling depan yang diberi kode a . Selanjutnya nilai a akan membagi data menjadi 2 subvektor untuk nilai diatas a dan dibawah a yang diberi symbol masing-masing k untuk lebih dari a dan n-k untuk kurang dari a. Setelah terbagi maka langkah selanjutnya adalah melakukan hal yang sama pada kedua subvektor. Selanjutnya mengulangi langkah-langkah sampai subvektor dari subvektor habis yang biasa disebut rekursi. Secara visual dapat dilihat pada gambar berikut :

Gambar ini menunjukan subvektor data yang lebih dari a dengan symbol k dan kurang dari a dengan n-k.

Secara lebih detailnya metode ini adalah sebagai berikut :

1. Ambil sebuah Pivot (Tumpuan)

2. Bagi menjadi dua subvektor data yang kurang dan lebih dari pivot yang dipilih.

Dalam gambar ini nilai 5 digunakan sebagai pivot.

3. Melakukan rekursi ke subvektor-subvektor selanjutnya.

Analisis metode

Dalam beberapa jurnal diasumsikan pivot diambil secara random maka akan terdistribusi exponential dengan running time sebesar O(n log₂ n). Metode ini akan meksimal bila nilai pengambilan pivot pertama bagus dalam artian tepat sebagai median yang membagi data subvektor sama besar dan sebaliknya bila pengambilan pivot dalam setiap subvektor adalah data yang tertinggi atau terendah sehingga pembagian subvektor satunya nilai diatas atau dibawah pivot dan subvektor keduanya adalah subvektor yang kosong maka metode ini tidak berjalan maksimal atau biasa disebut worst case dengan running time sebesar O(N²). Hal ini dapat dilihat dalam gambar berikut :

Gambar (a) menunjukkan kondisi yang terbaik (best case) dimana pemilihan pivot tepat sebagai median vector tersebut, gambar (b) menunjukkan kondisi biasa (average case) dan gambar (c) menunjukkan kondisi terburuk (worst case).

Dalam jurnal Tamassia Goodrich perfoma beberapa metode pengurutan dapat dibandingkan sebagai berikut :

Dalam tabel tersebut metode quick sort sangat bagus untuk data yang banyak karena peluang worst case akan semakin kecil sehingga performanya akan lebih maksimum.

Dalam grafik tersebut memperlihatkan perbandingan kecepatan dalam menyelesaikan suatu kasus. Untuk data kecil kecepatan dalam pengurutan tidak berbeda jauh namun untuk data skala tinggi metode quick sort adalah yang paling optimal