Quicksort is a sorting algorithm whose worst-case running time is Θ(n^2) on an input array of n numbers. In spite of this slow worst-case running time, quicksort is often the best practical choice for sorting because it is remarkably efficient on the average: its expected running time is Θ(n lg n). Quicksort, like merge sort, is based on the divide-and-conquer method.
Here is the steps of divide-and-conquer process for sorting a typical subarray A[p ‥ r]. First, Partition the array A[p…r] into two subarrays A[p…q – 1] and A[q + 1…r], such that each element of A[p…q – 1] is less than or equal to A[q] while each element of A[q + 1…r] is larger than a[q]. Then, sort the two subarrays A[p…q -1] and A[q +1…r] by recursive calls to quicksort. Since the subarrays are sorted in place, the entire array is sorted.
OK, Let’s see the divide method implement in C++: Partition the array A[p… r] into two subarrays A[p…q -1] and A[q+1…r].
int partition(int a[], int p, int q)
{
int i,j;
for(i=p,j=p;j
In each iteration of the loop, it compare a[j] with a[ r ] which is the pivot here. If a[j] smaller than a[ r ], exchange A[i] with A[j] and plus i with 1. So that all the indices smaller that i store the elements smaller than a[ r ]! The above loop of the procedure adjust the array into the status is showed by the following pictures. The final two lines of the procedure move the pivot element into its place in the middle of the array by swapping it with the leftmost element that is greater than a[q].
The four regions maintained by the above procedure on a subarray A[p...r]. The values in A[p... i] are all less than or equal to a[ r ], the values in A[i + 1...j - 1] are all greater than a[ r ]. The values in A[j...r - 1] can take on any values.
However there is another implement for this partition procedure:
int Hoare_partition(int a[], int p, int r)
{
int pivot = a[p];
int i=p,j=r;
while(i=pivot && i
When the divide method is introduced above, the whole quick sort algorithm now can be figured out: Just sort the two subarrays A[p...q -1] and A[q +1...r] by using recursion either by partition procedure or Hoare_partition procedure. We partition the array until it only has one element which of course is sorted, we stop. Here is the C++ implement:
void quick_sort(int a[], int p, int r)
{
if(p
BTY, the quicksort procedure was invented by CAR Hoare.