7. Advanced Sorting

In This Chapter

Shellsort

Partitioning

Quicksort

Radix Sort

We discussed simple sorting in the aptly titled Chapter 3, “Simple Sorting.” The sorts described there—the bubble, selection, and insertion sorts—are easy to implement but are rather slow. In Chapter 6, “Recursion,” we described the mergesort. It runs much faster than the simple sorts but requires twice as much space as the original array; this is often a serious drawback.

This chapter covers two advanced approaches to sorting: Shellsort and quicksort. These sorts both operate much faster than the simple sorts: the Shellsort in about O(N*(logN)2) time, and quicksort in O(N*logN) time. Neither of these sorts requires a large amount of extra space, as mergesort ...

Get Data Structures and Algorithms in Java, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.