Chapter Seven. Quicksort
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 ...
Get Algorithms in Java, Third Edition, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
