Artikel Quick Sort

Quick sort merupakan divide and conquer algorithm. Algoritma ini mengambil salah satu elemen secara acak (biasanya dari tengah) lalu menyimpan semua elemen yang lebih kecil di sebelah kirinya dan semua elemen yang lebih besar di sebelah kanannya. Hal ini dilakukan secara rekursif terhadap elemen di sebelah kiri dan kanannya sampai semua elemen sudah terurut. Algoritma ini termasuk algoritma yang cukup baik dan cepat. Hal penting dalam algoritma ini adalah pemilihan nilai tengah yang baik sehingga tidak memperlambat proses sorting secara keseluruhan.Ide dari algoritma ini adalah sebagai berikut:
a. Pilih satu elemen secara acak
b. Pindahka semua elemen yang lebih kecil ke sebelah elemen tersebut dan semua elemen yang lebih besar ke sebelah kanannya. Elemen yang nilainya sama bisa disimpan di salah satunya. Ini disebut operasi partisi
c. Lakukan sort secara rekursif terhadap sublist sebelah kiri dan kanannya.
Quick sort adalah pengembangan dari binary tree sort, yang lebih menghemat ruang. Cara perbandingannya mirip, hanya pengurutannya berbeda. dibandingkan dengan merge sort, quick sort memiliki keuntungan di kompleksitas waktu sebesar T(log n), dibanding dengan merge sort sebesar T(n). Namun quick sort tidak mampu membandingkan linked list sebaik merge sort, karena ada kemungkinan pemilihan pivot yang buruk. Selain itu pada linked list merge sort memerlukan ruang yang lebih sedikit. Berdasarkan analisis tersebut quick sort termasuk algoritma sorting yang cukup baik, namun kita pun harus bisa memilih nilai pivot yang baik agar penggunaannya bisa optmal.
Kompleksitas algoritma Quick Sort adalah bergantung pada hasil partisi tersebut. Kondisi best case adalah jika dalam setiap partisi tidak dilakukan operasi pertukaran tempat dan pivot tepat berada di tengah subset (O(n)). Kondisi average case adalah jika partisi menghasilkan sub data set yang balance (O(n log n)). Kondisi worse case adalah jika partisi menghasilkan sub data set kosong dan yang lain besar (o(n2)). Walaupun demikian, algoritma ini cenderung untuk average case.

Pseudocode quick sort:
Procedure Quick (int data[ ], int awal, int akhir)
kiri = awal
kanan = akhir
While (kiri < kanan)
pivot = kiri
While (data[ pivot ] <= data[ kanan ]) dan (pivot < kanan)
kanan = kanan – 1
Endwhile
If (data[ pivot ] > data[ kanan ] then
tukar (data[ pivot ], data[ kanan ])
Endif
pivot = kanan
While (data[ kiri ] <= data[ pivot ]) dan (kiri < pivot)
kiri = kiri + 1
Endwhile
If (data[ kiri ] > data[ pivot ])
tukar (data[ kiri ], data[ pivot ])
Endif
Endwhile
If (kanan>awal) Quick(data,awal,(pivot-1))
If (kiriEnd