Chapter 10: Sorting, Sets, and Selection

The Second Law of Thermodynamics suggests that Nature tends toward disorder. Humans, on the other hand, prefer order. Indeed, there are several advantages to keeping data in order. For example, the binary search algorithm, discussed earlier, works correctly only for an ordered vector. Since computers are intended to be tools for humans, we devote this chapter to the study of sorting algorithms and their applications. We recall that the sorting problem is defined as follows. Let S be a sequence of n elements that can be compared to each other according to a total order relation, that is, it is always possible to compare two elements of S to see which is larger or smaller, or if the two of them are equal. We want to rearrange S in such a way that the elements appear in increasing order (or in nondecreasing order if there are equal elements in S).

We have already presented several sorting algorithms in the previous chapters. In particular, we presented a simple sorting scheme, which is called PriorityQueueSort, that consists of inserting elements into a priority queue and then extracting them in nondecreasing order, by means of a series of removeMin operations. If the priority queue is implemented by means of a sequence, then PriorityQueueSort runs in quadratic time and corresponds to the sorting method known as either insertion-sort or selection-sort, depending on whether the sequence realizing the priority queue is kept ordered or not. If, on the other hand, the priority queue is implemented by means of a heap, then PriorityQueueSort runs in O(n log n) time and corresponds to the sorting method known as heap-sort.