Quick Sort

Quicksort ditemukan oleh C.A.R Hoare.  algoritma ini  berdasar pada pola divide-and-conquer.  algoritma ini
mengikuti langkah – langkah sebagai berikut :

1. Divide
Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu bagian dari prosedur pemisahan.


2. Conquer
Mengurutkan elemen pada sub-rangkaian secara rekursif Pada algoritma quicksort, langkah ”kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array

Setelah kondisi elemen kanan lebih kecil dari elemen kiri, kita cek apakah semua data sudah terurut, jika belum maka bagi data tersebut menjadi dua bagian, yaitu bagian sebelah kanan pivot dan sebelah kiri pivot, sedangkan elemen pivot bisa diikutkan kekanan atau kekiri. kemudian lakukan pengurutan dengan cara yang sama pada masing-masing bagian tadi

Algoritma
void quickSort(Object array[], int leftIdx, int rightIdx) {
        int pivotIdx;
/* Kondisi Terminasi */
           if (rightIdx > leftIdx) {
                     pivotIdx = partition(array, leftIdx, rightIdx);
                       quickSort(array, leftIdx, pivotIdx-1);
                       quickSort(array, pivotIdx+1, rightIdx);
             }
}