Data Structures and the Java Collections Framework, Third Edition

CHAPTER 11

Sorting

One of the most common computer operations is sorting, that is, putting a collection of elements in order. From simple, one-time sorts for small collections to highly efficient sorts for frequently used mailing lists and dictionaries, the ability to choose among various sort methods is an important skill in every programmer's repertoire.

CHAPTER OBJECTIVES

1. Compare the Comparable interface to the Comparator interface, and know when to use each one.
2. Be able to decide which sort algorithm is appropriate for a given application.
3. Understand the limitations of each sort algorithm.
4. Explain the criteria for a divide-and-conquer algorithm.

11.1 Introduction

Our focus will be on comparison-based sorts; that is, the sorting entails comparing elements to other elements. Comparisons are not necessary if we know, in advance, the final position of each element. For example, if we start with an unsorted list of 100 distinct integers in the range 0 … 99, we know without any comparisons that the integer 0 must end up in position 0, and so on. The best- known sort algorithm that is not comparison-based is Radix Sort: see Section 11.5.

All of the sort algorithms presented in this chapter are generic algorithms, that is, static methods: they have no calling object and operate on the parameter that specifies the collection to be sorted. Two of the sort methods, Merge Sort and Quick Sort, are included in the Java Collections Framework, and can be found in the Collections or Arrays ...