Algorithms in Java, Parts 1-4 (3rd Edition) (Pts.1-4)

The subject of this chapter is the sorting algorithm that is probably used more widely than any other, quicksort. The basic algorithm was invented in 1960 by C. A. R. Hoare, and it has been studied by many people since that time (see reference section). Quicksort is popular because it is not difficult to implement, works well for a variety of different kinds of input data, and consumes fewer resources than any other sorting method in many situations.

The quicksort algorithm's desirable features are that it is in-place (uses only a small auxiliary stack), requires time only proportional to N log N on the average to sort N items, and has an extremely short inner loop. Its drawbacks are that it is not stable, takes about N² operations in the worst case, and is fragile in the sense that a simple mistake in the implementation can go unnoticed and can cause it to perform badly for some files.

The performance of quicksort is well understood. The algorithm has been subjected to a thorough mathematical analysis, and we can make precise statements about its performance. The analysis has been verified by extensive empirical experience, and the algorithm has been refined to the point where it is the method of choice in a broad variety of practical sorting applications. It is therefore worthwhile for us to look more carefully than for other algorithms at ways of implementing quicksort efficiently. Similar implementation techniques are appropriate for other algorithms; with quicksort, we can use them with confidence, because we know precisely how they will affect performance.

It is tempting to try to develop ways to improve quicksort: A faster sorting algorithm is computer science's "better mousetrap," and quicksort is a venerable method that seems to invite tinkering. Almost from the moment Hoare first published the algorithm, improved versions have been appearing in the literature. Many ideas have been tried and analyzed, but it is easy to be deceived, because the algorithm is so well balanced that the effects of improvements in one part of the program can be more than offset by the effects of bad performance in another part of the program. We examine in detail three modifications that do improve quicksort substantially.

A carefully tuned version of quicksort is likely to run significantly faster on most computers than will any other sorting method, and quicksort is widely used as a library sort utility and for other serious sorting applications. Indeed, the the standard Java library's sort is an implementation of quicksort. Despite its deserved reputation as a fast algorithm, the running time of quicksort does depend on the input and ranges from linear to quadratic in the number of items to be sorted. People are sometimes surprised by undesirable and unexpected effects for some inputs, particularly in highly tuned versions of the algorithm. When an application does not justify the work required to be sure that a quicksort implementation is not flawed, some programmers turn to shellsort as a safer choice that will perform well for less implementation investment. For huge files, however, quicksort is likely to run 5 to 10 times as fast as shellsort, and it can adapt to be even more efficient for other types of files that might occur in practice.