1.1 The Course of This Course 3

are inherently more eﬃcient than others. Almost invariably, no matter how powerful

the computer, a person intending serious use of the computer to support some

activity will run up against the performance limitations of the machine and will

need to use better algorithms.

There are two ways in which computational performance can be improved:

One can change from an ineﬃcient algorithm to an eﬃcient algorithm, or one can

change from a poor implementation to a good implementation. It is usually argued

that the real improvements in performance (factors of 10 and 100) come from

improved algorithms, and that improved implementations usually provide factors

of perhaps 2 to 4. One should therefore look for a good algorithm and implement

that, and one should do a good implementation. That being said, it’s also possible

to overdo both of these. The really good algorithms will also be more complicated

to implement (and thus more prone to error), and the beneﬁt of the algorithms is

usually only on large input sets. If the input data is small, then a good algorithm is

better than a naive algorithm and a great algorithm is probably overkill. Similarly,

if a small improvement in performance can be achieved by an implementation that

makes the code impossible to read, understand, and maintain, then maybe that’s

not good either.

1.1.3 Sorting

It will normally be the case that we want to keep an address book in sorted order,

usually by last name, because that is how we identify records for retrieval. It has

been estimated that perhaps a third of the CPU cycles expended in all of computing

are spent in sorting records to keep them accessible in a desired order. For this

reason, sorting records is an extremely important subject in data structures and in

computing in general, and thus we will spend an entire chapter on sorting.

There are sorting methods that are very simple to implement. Generally, since

there is no free lunch in this world, these are also the methods that are not very

good. The good sorting methods are somewhat more complicated, but it turns out

that a reasonably simple method—quicksort—is actually quite eﬀective. Although

we can prove (and will prove) that quicksort is not the best method for all sorting

problems, it is quite good on average. We will spend a little more time on the bigger

picture of sorting because the comparison of the major sorting methods—quicksort,

heapsort,andmergesort—provides a good introduction into the trade-oﬀs that good

software people need to make

• between good algorithms that might be hard to implement and poorer algo-

rithms that are easy to implement;

• between the best-case behavior,theworst-case behavior,andtheaverage-case

behavior of algorithms;

Start Free Trial

No credit card required