Beautiful Code [99]
if (x[i] < x[l])
swap(++m, i);
This program sorts an array and counts the number of comparisons used while doing so. However, if our goal is only to count the comparisons, we don't really need to sort the array. Example 3-4 removes the "real work" of sorting the elements, and keeps only the "skeleton" of the various calls made by the program.
Example 3-4. Quicksort skeleton reduced to counting
void quickcount(int l, int u)
{ int m;
if (l >= u) return;
m = randint(l, u);
comps += u-l;
quickcount(l, m-1);
quickcount(m+1, u);
}
This program works because of the "randomizing" way in which Quicksort chooses its partitioning element, and because all of the elements are assumed to be distinct. This new program now runs in time proportional to n, and while Example 3-3 required space proportional to n, the space is now reduced to the recursion stack, which on average is proportional to lg n.
While the indexes (l and u) of the array are critical in an actual program, they don't matter in this skeleton version. We can replace these two indexes with a single integer (n) that specifies the size of the subarray to be sorted (see Example 3-5).
Example 3-5. Quicksort skeleton with single size argument
void qc(int n)
{ int m;
if (n <= 1) return;
m = randint(1, n);
comps += n-1;
qc(m-1);
qc(n-m);
}
It is now more natural to rephrase this procedure as a comparison count function that returns the number of comparisons used by one random Quicksort run. This function is shown in Example 3-6.
Example 3-6. Quicksort skeleton implemented as a function
int cc(int n)
{ int m;
if (n <= 1) return 0;
m = randint(1, n);
return n-1 + cc(m-1) + cc(n-m);
}
Example 3-4, Example 3-5, and Example 3-6 all solve the same basic problem, and they do so with the same runtime and memory usage. Each successor improves the form of the function and is thereby clearer and a bit more succinct than its predecessor.
In defining the inventor's paradox (How To Solve It, Princeton University Press), George Pólya says that "the more ambitious plan may have more chances of success." We will now try to exploit that paradox in the analysis of Quicksort. So far we have asked, "How many comparisons does Quicksort make on one run of size n?" We will now ask the more ambitious question, "How many comparisons does Quicksort make, on average, for a random array of size n?" We can extend Example 3-6 to yield the pseudocode in Example 3-7.
Example 3-7. Quicksort average comparisons as pseudocode
float c(int n)
if (n <= 1) return 0
sum = 0
for (m = 1; m <= n; m++)
sum += n-1 + c(m-1) + c(n-m)
return sum/n
If the input has a maximum of one element, Quicksort uses no comparisons, just as in Example 3-6. For larger n, this code considers each partition value m (from the first element to the last, each equally likely) and determines the cost of partitioning there. The code then calculates the sum of these values (thereby solving recursively one problem of size m-1 and one problem of size (n-m), and then divides that sum by n to return the average.
If we could compute this number it would make our experiments much more powerful. Rather than having to run many experiments at a single value of n to estimate the mean, a single experiment would give us the true mean. Unfortunately, that power comes at a price: the program runs in time proportional to 3n (it is an interesting, if self-referential, exercise to analyze that runtime using the techniques described in this chapter).
Example 3-7 takes the time that it does because it computes subanswers over and over again. When a program does that, we can often use dynamic programming to store the subanswers to avoid recomputing them. In this case, we'll introduce the table t[N+1], in which t[n] stores c(n), and compute its values in increasing order. We will let N denote the maximum size of n, which is the size of the array to be sorted. The result is shown in Example 3-8.
Example 3-8. Quicksort calculation with dynamic programming
t[0] = 0
for (n = 1; n <= N; n++)