Sorting 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)

Sumber