Most implementations of quick sort make use of the fact that you can partition in place by keeping two pointers: one moving in from the left and a second moving in from the right. They are moved towards the centre until the left pointer finds an element greater than the pivot and the right one finds an element less than the pivot. These two elements are then swapped. The pointers are then moved inward again until they "cross over". The pivot is then swapped into the slot to which the right pointer points and the partition is complete.

int partition( int a[], int low, int high ) { int left, right; int pivot_item; pivot_item = a[low]; pivot = left = low; right = high; while ( left < right ) { /* Move left while item < pivot */ while( a[left] <= pivot_item ) left++; /* Move right while item > pivot */ while( a[right] > pivot_item ) right--; if ( left < right ) SWAP(a,left,right); } /* right is final position for the pivot */ a[low] = a[right]; a[right] = pivot_item; return right; }

Note that this above code does not check that left exceeds the array bound. You need to add this check, before performing the swaps - both the one in the loop and the final one outside the loop.

partition ensures that all items less than the pivot precede it and returns the position of the pivot. This meets our condition for dividing the problem: all the items in the lower half are known to be less than the pivot and all items in the upper half are known to be greater than it.

Analysis

Usually, the partition routine will divide the problem into two roughly equal sized partitions. We know that we can divide n items in half log₂n times. This makes quicksort a O(nlogn) algorithm.

However, we have made an unjustified assumption - see if you can identify it before you continue.

Key terms

Divide and Conquer Algorithms Algorithms that solve (conquer) problems by dividing them into smaller sub-problems until the problem is so small that it is trivially solved.

Continue on to Quick Sort (cont)