PART III Sorting and Searching 229 7 Internal Sorting We sort many things in our everyday lives: A handful of cards when playing Bridge; bills and other piles of paper; jars of spices; and so on. And we have many intuitive strategies that we can use to do the sorting, depending on how many objects we have to sort and how hard they are to move around. Sorting is also one of the most frequently performed computing tasks. We might sort the records in a database so that we can search the collection efficiently.
We might sort the records by zip code so that we can print and mail them more cheaply. We might use sorting as an intrinsic part of an algorithm to solve some other problem, such as when computing the minimum-cost spanning tree (see Section 11. Because sorting is so important, naturally it has been studied intensively and many algorithms have been devised. Some of these algorithms are straightforward adaptations of schemes we use in everyday life.
Others are totally alien to how hu- mans do things, having been invented to sort thousands or even millions of records stored on the computer. After years of study, there are still unsolved problems related to sorting. New algorithms are still being developed and refined for special- purpose applications. While introducing this central problem in computer science, this chapter has a secondary purpose of illustrating issues in algorithm design and analysis.
For example, this collection of sorting algorithms shows multiple approaches to us- ing divide-and-conquer. In particular, there are multiple ways to do the dividing: Mergesort divides a list in half; Quicksort divides a list into big values and small values; and Radix Sort divides the problem by working on one digit of the key at a time. Sorting algorithms can also illustrate a wide variety of analysis techniques. We’ll find that it is possible for an algorithm to have an average case whose growth rate is significantly smaller than its worse case (Quicksort).
We’ll see how it is possible to speed up sorting algorithms (both Shellsort and Quicksort) by taking advantage of the best case behavior of another algorithm (Insertion sort). We’ll see several examples of how we can tune an algorithm for better performance. We’ll see that special case behavior by some algorithms makes them a good solution for 231 232 Chap. 7 Internal Sorting special niche applications (Heapsort).
Sorting provides an example of a significant technique for analyzing the lower bound for a problem. Sorting will also be used to motivate the introduction to file processing presented in Chapter 8. The present chapter covers several standard algorithms appropriate for sorting a collection of records that fit in the computer’s main memory. It begins with a dis- cussion of three simple, but relatively slow, algorithms requiring Θ(n2 ) time in the average and worst cases.
Several algorithms with considerably better performance are then presented, some with Θ(n log n) worst-case running time. The final sort- ing method presented requires only Θ(n) worst-case time under special conditions. The chapter concludes with a proof that sorting in general requires Ω(n log n) time in the worst case.1 Sorting Terminology and Notation Except where noted otherwise, input to the sorting algorithms presented in this chapter is a collection of records stored in an array. Records are compared to one another by means of a comparator class, as introduced in Section 4.
To simplify the discussion we will assume that each record has a key field whose value is ex- tracted from the record by the comparator. The key method of the comparator class is prior, which returns true when its first argument should appear prior to its sec- ond argument in the sorted list. We also assume that for every record type there is a swap function that can interchange the contents of two records in the array(see the Appendix). Given a set of records r1 , r2 , ., rn with key values k1 , k2 , ., kn , the Sorting Problem is to arrange the records into any order s such that records rs1 , rs2 , ., rsn have keys obeying the property ks1 ≤ ks2 ≤.
In other words, the sorting problem is to arrange a set of records so that the values of their key fields are in non-decreasing order. As defined, the Sorting Problem allows input with two or more records that have the same key value. Certain applications require that input not contain duplicate key values. The sorting algorithms presented in this chapter and in Chapter 8 can handle duplicate key values unless noted otherwise.
When duplicate key values are allowed, there might be an implicit ordering to the duplicates, typically based on their order of occurrence within the input. It might be desirable to maintain this initial ordering among duplicates. A sorting algorithm is said to be stable if it does not change the relative ordering of records with identical key values. Many, but not all, of the sorting algorithms presented in this chapter are stable, or can be made stable with minor changes.
When comparing two sorting algorithms, the most straightforward approach would seem to be simply program both and measure their running times. An ex- ample of such timings is presented in Figure 7. However, such a comparison Sec.2 Three Θ(n2 ) Sorting Algorithms 233 can be misleading because the running time for many sorting algorithms depends on specifics of the input values. In particular, the number of records, the size of the keys and the records, the allowable range of the key values, and the amount by which the input records are “out of order” can all greatly affect the relative running times for sorting algorithms.
When analyzing sorting algorithms, it is traditional to measure the number of comparisons made between keys. This measure is usually closely related to the running time for the algorithm and has the advantage of being machine and data- type independent. However, in some cases records might be so large that their physical movement might take a significant fraction of the total running time. If so, it might be appropriate to measure the number of swap operations performed by the algorithm.
In most applications we can assume that all records and keys are of fixed length, and that a single comparison or a single swap operation requires a constant amount of time regardless of which keys are involved. Some special situations “change the rules” for comparing sorting algorithms. For example, an application with records or keys having widely varying length (such as sorting a sequence of variable length strings) will benefit from a special-purpose sorting technique. Some applications require that a small number of records be sorted, but that the sort be performed frequently.
An example would be an application that repeatedly sorts groups of five numbers. In such cases, the constants in the runtime equations that are usually ignored in an asymptotic analysis now become crucial. Finally, some situations require that a sorting algorithm use as little memory as possible. We will note which sorting algorithms require significant extra memory beyond the input array.2 Three Θ(n2 ) Sorting Algorithms This section presents three simple sorting algorithms.
While easy to understand and implement, we will soon see that they are unacceptably slow when there are many records to sort. Nonetheless, there are situations where one of these simple algorithms is the best tool for the job.1 Insertion Sort Imagine that you have a stack of phone bills from the past two years and that you wish to organize them by date. A fairly natural way to do this might be to look at the first two bills and put them in order. Then take the third bill and put it into the right order with respect to the first two, and so on.
As you take each bill, you would add it to the sorted pile that you have already made. This naturally intuitive process is the inspiration for our first sorting algorithm, called Insertion Sort. Insertion Sort iterates through a list of records. Each record is inserted in turn at the correct position within a sorted list composed of those records already processed.
7 Internal Sorting i=1 2 3 4 5 6 7 42 20 17 13 13 13 13 13 20 42 20 17 17 14 14 14 17 17 42 20 20 17 17 15 13 13 13 42 28 20 20 17 28 28 28 28 42 28 23 20 14 14 14 14 14 42 28 23 23 23 23 23 23 23 42 28 15 15 15 15 15 15 15 42 Figure 7.1 An illustration of Insertion Sort. Each column shows the array after the iteration with the indicated value of i in the outer for loop. Values above the line in each column have been sorted. Arrows indicate the upward motions of records through the array.
following is a C++ implementation. The input is an array of n records stored in array A. template <typename E, typename Comp> void inssort(E A[], int n) { // Insertion Sort for (int i=1; i<n; i++) // Insert i’th record for (int j=i; (j>0) && (Comp::prior(A[j], A[j-1])); j--) swap(A, j, j-1); } Consider the case where inssort is processing the ith record, which has key value X. The record is moved upward in the array as long as X is less than the key value immediately above it.
As soon as a key value less than or equal to X is encountered, inssort is done with that record because all records above it in the array must have smaller keys.1 illustrates how Insertion Sort works. The body of inssort is made up of two nested for loops. The outer for loop is executed n − 1 times. The inner for loop is harder to analyze because the number of times it executes depends on how many keys in positions 1 to i − 1 have a value less than that of the key in position i.
In the worst case, each record must make its way to the top of the array. This would occur if the keys are initially arranged from highest to lowest, in the reverse of sorted order. In this case, the number of comparisons will be one the first time through the for loop, two the second time, and so on. Thus, the total number of comparisons will be n X i ≈ n2 /2 = Θ(n2 ).
i=2 In contrast, consider the best-case cost. This occurs when the keys begin in sorted order from lowest to highest. In this case, every pass through the inner for loop will fail immediately, and no values will be moved. The total number Sec.2 Three Θ(n2 ) Sorting Algorithms 235 of comparisons will be n − 1, which is the number of times the outer for loop executes.
Thus, the cost for Insertion Sort in the best case is Θ(n). While the best case is significantly faster than the worst case, the worst case is usually a more reliable indication of the “typical” running time. However, there are situations where we can expect the input to be in sorted or nearly sorted order. One example is when an already sorted list is slightly disordered by a small number of additions to the list; restoring sorted order using Insertion Sort might be a good idea if we know that the disordering is slight.
Examples of algorithms that take ad- vantage of Insertion Sort’s near-best-case running time are the Shellsort algorithm of Section 7.3 and the Quicksort algorithm of Section 7. What is the average-case cost of Insertion Sort? When record i is processed, the number of times through the inner for loop depends on how far “out of order” the record is. In particular, the inner for loop is executed once for each key greater than the key of record i that appears in array positions 0 through i−1.