Beautiful Code [100]
sum = 0
for (i = 1; i <= n; i++)
sum += n-1 + t[i-1] + t[n-i]
t[n] = sum/n
This program is a rough transcription of Example 3-7 and replaces c(n) with t[n]. Its runtime is proportional to N2 and its space is proportional to N. One of its benefits is that at the end of execution, the array t contains the true average values (not just the estimate of sample means) for array elements 0 through N. Those values can be analyzed to yield insight about the functional form of the expected number of comparisons used by Quicksort.
We will now simplify that program further. The first step is to move the term n-1 out of the loop, as shown in Example 3-9.
Example 3-9. Quicksort calculation with code moved out of the loop
t[0] = 0
for (n = 1; n <= N; n++)
sum = 0
for (i = 1; i <= n; i++)
sum += t[i-1] + t[n-i]
t[n] = n-1 + sum/n
We will now further tune the loop by exploiting symmetry. When n is 4, for instance, the inner loop computes the sum:
t[0]+t[3] + t[1]+t[2] + t[2]+t[1] + t[3]+t[0]
In the sequence of pairs, the first elements increase while the second elements decrease. We can therefore rewrite the sum as:
2 * (t[0] + t[1] + t[2] + t[3])
We can use that symmetry to yield the Quicksort shown in Example 3-10.
Example 3-10. Quicksort calculation with symmetry
t[0] = 0
for (n = 1; n <= N; n++)
sum = 0
for (i = 0; i < n; i++)
sum += 2 * t[i]
t[n] = n-1 + sum/n
However, this code is once again wasteful because it recomputes the same sum over and over again. Rather than adding all the previous terms, we can initialize sum outside the loop and add the next term to yield Example 3-11.
Example 3-11. Quicksort calculation with the inner loop removed
sum = 0; t[0] = 0
for (n = 1; n <= N; n++)
sum += 2*t[n-1]
t[n] = n-1 + sum/n
This little program is indeed useful. In time proportional to N, it produces a table of the true expected runtimes of Quicksort for every integer from 1 to N.
Example 3-11 is straightforward to implement in a spreadsheet, where the values are immediately made available for further analysis. Table 3-1 shows the first rows.
Table 3-1. Output of spreadsheet implementation of Example 3-11
N Sum t[n]
0 0 0
1 0 0
2 0 1
3 2 2.667
4 7.333 4.833
5 17 7.4
6 31.8 10.3
7 52.4 13.486
8 79.371 16.921
The first row of numbers in this table is initialized with the three constants from the code. In spreadsheet notation, the next row of numbers (the third row of the spreadsheet) is calculated using the following relations:
A3 = A2+1 B3 = B2 + 2*C2 C3 = A3-1 + B3/A3
Dragging those (relative) relations down completes the spreadsheet. That spreadsheet is a real contender for "the most beautiful code I ever wrote," using the criterion of accomplishing a great deal with just a few lines of code.
But what if we don't need all the values? What if we would prefer to analyze just a few of the values along the way (for example, all the powers of 2 from 20 to 232)? Although Example 3-11 builds the complete table t, it uses only the most recent value of that table.
We can therefore replace the linear space of the table t[] with the constant space of the variable t, as shown in Example 3-12.
Example 3-12. Quicksort calculation—final version
sum = 0; t = 0
for (n = 1; n <= N; n++)
sum += 2*t
t = n-1 + sum/n
We could then insert an extra line of code to test for appropriateness of n, and print those results as needed.
This tiny program is the final step in our long path. Alan Perlis' observation is apt in consideration of the path this chapter has taken: "Simplicity does not precede complexity, but follows it" ("Epigrams on Programming," Sigplan Notices, Vol. 17, Issue 9).
The Most Beautiful Code I Never Wrote > Perspective
3.3. Perspective
Table 3-2 summarizes the programs used to analyze Quicksort throughout this chapter.
Table 3-2. Evolution of Quicksort comparison counting
Example Number Lines of code Type of answer Number of answer Runtime Space
2 13 Sample 1 n l g n N
3 13 " " " "
4 8 " " n lgn
5 8 " " " "
6 6 " "