Sorting dengan Metode Quick Sort

Quick Sort sebenarnya sama seperti Merge sort yaitu menggunakan metode Divide & Conquer. Prinsip dalam algoritma quicksort sebagai berikut:

1. Bila elemen dalam array kurang dari jumlah tertentu (biasanya 2), proses selesai.
2. Ambil sebuah elemen yang berfungsi sebagai poros. 
3. Pisahkan array dalam 2 bagian, sebelah kiri lebih kecil dari poros, sebelah kanan lebih besar dari poros.
4. Ulangi proses secara rekursif pada tiap-tiap bagian.

Hal penting dari hal algoritma ini adalah: bagaimana memilih poros dengan tepat dan secara efisien mengatur tiap-tiap elemen sehingga didapat elemen kecil > poros > elemen besar dalam kondisi (mendekati) seimbang.

Contoh Quick sort dalam gambar

Contoh Pseudocode Quick Sort 

Quicksort(A as array, low as int, high as int) 
if (low < high) 
pivot_location = Partition(A,low,high) 
Quicksort(A,low, pivot_location - 1) 
Quicksort(A, pivot_location + 1, high) 
Partition(A as array, low as int, high as int) 
pivot = A[low] leftwall = low for i = low + 1 to high 
if (A[i] < pivot) 
then leftwall = leftwall + 1 swap(A[i], A[leftwall]) swap(A[low],A[leftwall]) 
return (leftwall)

Program selengkapnya ada disini (menggunakan Java)

SHARE THIS