Quicksort is an elegant algorithm that lends itself to subtle analysis. Around 1980, I had a wonderful discussion with Tony Hoare about the history of his algorithm. He told me that when he first developed Quicksort, he thought it was too simple to publish, and only wrote his classic "Quicksort" paper after he was able to analyze its expected runtime.
It is easy to see that in the worst case, Quicksort might take about n2 time to sort an array of n elements. In the best case, it chooses the median value as a partitioning element, and therefore sorts an array in about n lg n comparisons. So, how many comparisons does it use on the average for a random array of n distinct values?
Hoare's analysis of this question is beautiful, but unfortunately over the mathematical heads of many programmers. When I taught Quicksort to undergraduates, I was frustrated that many just didn't "get" the proof, even after sincere effort. We'll now attack that problem experimentally. We'll start with Hoare's program, and eventually end up with an analysis close to his.
Our task is to modify Example 3-1 of the randomizing Quicksort code to analyze the average number of comparisons used to sort an array of distinct inputs. We will also attempt to gain maximum insight with minimal code, runtime, and space.
To determine the average number of comparisons, we first augment
the program to count them. To do this, we increment the variable
comps before the comparison in the inner loop ...