Quicksort

Quicksort ditemukan oleh C.A.R Hoare. Seperti pada merge sort, algoritma ini juga berdasar pada pola divide-and-conquer. Berbeda dengan merge sort, algoritma ini hanya 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

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);
}
}