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( void *a, int low, int high ) { int left, right; void *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 does not exceed 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. An encoding which adds an extra loop to do this may be found in Wikipedia.

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

The partition routine examines every item in the array at most once, so it is clearly O(n).

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 - equivalent to heapsort.

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

Note that the pseudo-code above assumes that the operators <= and > work on the items to be sorted. In general, we would use some ItemCmp function in the partition function. This assumes that there is an external declaration for ItemCmp and that in any one program, we only want to sort one type of object. Generally this will not be acceptable, so the formal specification for quicksort in the Unix and ANSI C libraries includes a function compar which is supplied to qsort when it is called. Passing the function, compar, which defines the ordering of objects when qsort is called avoids this problem in the same way that we passed an ItemCmp function to ConsCollection. Object oriented languages provide more elegant and flexible solutions: see code in Wikipedia for examples.

QuickSort Animation This animation uses the partition in place approach; it was written by Chien Wei Tan

Please email comments to morris@ee.uwa.edu.au

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)

Back to the Table of Contents

© John Morris, 1998