Computer Science 477/677
A Quicksort Example

Revised October 18, 2005

1. The pivot item is always take to be the first item of the subarray being sorted.
2. At each iteration of the main loop of Partition:
   • If possible, we increment "lo" by one.
   • If possible, we decrement "hi" by one. (We might both increment "lo" and decrement "hi" in one iteration.)
   • If neither of those is possible, we swap and then increment "lo" and decrement "hi."
3. When "lo" and "hi" meet, we exchange the pivot item with the rightmost item in the left portion. (If the left portion is empty, we do nothing.)
4. If there are two or more subarrays that need to be sorted, we sort the smaller one first. If they are of equal size, we sort the leftmost one first.
5. In the illustrated file, we show the array at each step.
   • Items known to be in their final positions are colored black.
   • Items in the subarray that is currently being sorted that have not be inspected are colored orange.
   • The pivot item is colored blue.
   • Items in the left portion of the subarray currently being sorted are colored red.
   • Items in the right portion of the subarray currently being sorted are colored green.
   • Items in any subarray that has not been sorted and is not currently being sorted are colored brown.
   Updated Tuesday, October 18, 6:33 AM. The previous file had only one error, namely that I failed to follow the rule that when you recursively sort the two subarrays after partititioning, you sort the smaller one first. If you follow this rule, the depth of the recursion is Theta(log n), while if you don't, it's O(n), although the algorithm is still correct.
   Here is another example.
   Here is another example.