3.3. Perspective by Andy Oram, Greg Wilson

Safari, the world’s most comprehensive technology and business learning platform.

Find the exact information you need to solve a problem on the fly, or go deeper to master the technologies and skills you need to succeed

Start Free Trial

No credit card required

O'Reilly logo

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:

Find the exact information you need to solve a problem on the fly, or go deeper to master the technologies and skills you need to succeed

Start Free Trial

No credit card required