O'Reilly logo

Beautiful Code by Andy Oram, Greg Wilson

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

"

"

"

"

7

6

Exact

"

3N

N

8

6

"

N

N2

N

9

6

"

"

"

"

10

6

"

"

"

"

11

4

"

"

N

"

12

4

Exact

N

N

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:

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required