QuickSort can be tricky and atleast one of its implementations printed in a widely used book had in it a subtle bug.
Found an excellent concise implementation in the book “Programming Pearls” by John Bentley.
void quicksort(int left, int right)
{
if ( left <= right ) return;
int pivotIndex = rand(left, right);
int pivotValue = x[pivotIndex];
swap(x[left], x[pivotIndex]);
int partitionIndex = left;
for (int i = left + 1 ; i <= right; i ++)
if ( x[i] < pivotValue ) swap ( x[++partitionIndex], x[i]);
swap (x[left], x[partitionIndex]);
quicksort(left, partitionIndex -1);
quicksort(partitionIndex + 1, right);
}
Lets see how we could build the above program:
Step 1: Need a find a partition point m. Given m, we need to recurse with quicksort(l, m -1); quicksort (m + 1, u);
Step 2: For recursive programs, an exit strategy is required. if ( l >= u) return;
Step 3: It is difficult to have the pivot value in exactly the middle of the array bcz:
1. We really want to select the pivot location randomly.
2. There is no guarantee that the pivot value will end up dividing the array in two equal subarrays.
As John B mentions in the video, humans are prone to symmetry potentially leading to complex code in the quicksort implementations. So the approach to take is : select a pivot randomly and move it to the first location of the array.
And beautiful code is born !
9am 