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 | | |

3 | 13 | " | " | " | " |

4 | 8 | " | " | | lg |

5 | 8 | " | " | " | " |

6 | 6 | " | " | " | " |

7 | 6 | Exact | " | 3 | |

8 | 6 | " | |
| |

9 | 6 | " | " | " | " |

10 | 6 | " | " | " | " |

11 | 4 | " | " | | " |

12 | 4 | Exact | | | 1 |

Each individual step in the evolution of our code was pretty straightforward; the transition from the sample in Example 3-6 to the exact answer in Example 3-7 is probably the most subtle. Along the way, as the code became faster and more useful, it also shrank in size. In the middle of the 19th century, Robert Browning observed that "less is more," and this table helps to quantify one instance of that minimalist philosophy.

We have seen three fundamentally different types of programs. Example 3-2 and Example 3-3 are working Quicksorts, instrumented to count comparisons as they sort a real array. Example 3-4 through Example 3-6 implement a simple model of Quicksort: they mimic one run of the algorithm, without actually doing the work of sorting. Example 3-7 through Example 3-12 implement a more sophisticated model: they compute the true average number of comparisons without ever tracing any particular run.

The techniques used to achieve each program are summarized as follows:

Example 3-2, Example 3-4, Example 3-7: Fundamental change of problem definition.

Example 3-5, Example 3-6, Example 3-12: Slight change of function definition.

Example 3-8: New data structure ...

Start Free Trial

No credit card required