3.1 Elementary Sorts

In this section, we shall study two elementary sorting methods (selection sort and insertion sort) and a variation of one of them (shellsort).

Rules of the game. Our primary concern is algorithms for rearranging an array of keys into ascending order. In Java, the abstract notion of a key is captured in a built-in mechanism - the Comparable interface - that is described later in this section. With but a few exceptions, our sort code refers to the data only through two operations: the method less() that compares objects and the method exch() that exchanges them. The exch() method is easy to implement, and the Comparable interface makes it easy to implement less().

private static boolean less(Comparable v, Comparable w) {
   return (v.compareTo(w) < 0);
}

private static void exch(Comparable[] a, int i, int j) {
   Comparable swap = a[i];
   a[i] = a[j];
   a[j] = swap;
}

Our sort code is effective for any type of data that implements Java's Comparable interface. Java's numeric wrapper types like Integer and Double implement the Comparable interface, as do String and various advanced types such as Date, Time and File. To implement the Comparable interface for your own type of data, you need to implement a method compareTo() so that v.compareTo(w):

Returns a negative integer if v is less than w;
Returns a positive integer if v is greater than w;
Returns zero if v equals w;
Throws an exception if v and w are of incompatible types or one is null.

In addition, it must implement total order:

Reflexive: a = a.
Antisymmetric: if (a < b) then (b > a); if (a = b) then (b = a).
Transitive: if (a ≤ b) and (b ≤ c), then a ≤ c.

Record.java is a simple data type that implements the Comparable interface.

Selection sort.

One of the simplest sorting algorithms works as follows: First, find the smallest element in the array, and exchange it with the element in the first position. Then, find the next smallest element and exchange it with the element in the second position. Continue in this way until the entire array is sorted. This method is called selection sort because it works by repeatedly selecting the smallest remaining element. Selection.java is an implementation of this method.

Proposition A.

Selection sort uses ~N²/2 compares and N exchanges.

Insertion sort. The algorithm that people often use to sort bridge hands is to consider the cards one at a time, inserting each into its proper place among those already considered (keeping them sorted). In a computer implementation, we need to make space for the element being inserted by moving larger elements one position to the right, and then inserting the element into the vacated position. Insertion.java is an implementation of this method, which is called insertion sort.

Proposition B.

For randomly ordered input with distinct keys, insertion sort uses ~N²/4 compares and ~N²/4 exchanges on the average. The worst case is ~ N²/2 compares and ~ N²/2 exchanges and the best case is N-1 compares and 0 exchanges.

Insertion sort works well for certain types of nonrandom arrays that often arise in practice, even if they are huge. An inversion is a pair of keys that are out of order in the array. For instance, E X A M P L E has 11 inversions: E-A, X-A, X-M, X-P, X-L, X-E, M-L, M-E, P-L, P-E, and L-E. If the number of inversions in an array is less than a constant multiple of the array size, we say that the array is partially sorted.

Proposition C.

The number of exchanges used by insertion sort is equal to the number of inversions in the array, and the number of compares is at least equal to the number of inversions and at most equal to the number of inversions plus the array size.

Property D.

The running times of insertion sort and selection sort are quadratic and within a small constant factor of one another for randomly ordered arrays.

SortCompare.java uses the sort() methods in the classes named as command-line arguments to perform the given number of experiments (sorting arrays of the given size) and prints the ratio of the observed running times of the algorithms.

Shellsort.

Shellsort is a simple extension of insertion sort that gains speed by allowing exchanges of elements that are far apart, to produce partially sorted arrays that can be efficiently sorted, eventually by insertion sort. The idea is to rearrange the array to give it the property that taking every hth element (starting anywhere) yields a sorted sequence. Such an array is said to be h-sorted.

By h-sorting for some large values of h, we can move elements in the array long distances and thus make it easier to h-sort for smaller values of h. Using such a procedure for any increment sequence of values of h that ends in 1 will produce a sorted array: that is shellsort. Shell.java is an implementation of this method.

Proposition E.

With the 3x + 1 increment sequence (1, 4, 13, 40, 121, ...), shellsort uses O(N^3/2) compares.

The study of performance characteristics of shellsort requires mathematical arguments that are beyond the scope of this book. If you want to be convinced, start by thinking about how you would prove the following fact: when an h-sorted file is k-sorted, it remains h-sorted.

Q + A

Q. Any sorting demos?

A. James Gosling created a number of sorting applets to market Java when it was just taking off. Here are some from UBC and some from RIT.

Exercises

Show in the style of the example trace with selection sort, how selection sort sorts the array
E A S Y Q U E S T I O N
What is the maximum number of exchanges involving any particular element during selection sort? What is the average number of exchanges involving an element?
Give an example of an array of N elements that maximizes the number of times the test (a[j] < a[min]) fails (and therefore, min gets updated) during the operation of selection sort.
Show in the style of the example trace with insertion sort, how insertion sort sorts the array
E A S Y Q U E S T I O N
For each of the two conditions in the inner for loop in insertion sort, describe an array of N elements where that condition is always false when the loop terminates.
Which method runs fastest for an array with all keys identical, selection sort or insertion sort?
Which method runs fastest for an array in reverse order, selection sort or insertion sort?
Suppose that we use insertion sort on a randomly ordered array where elements have only one of three values. Is the running time linear, quadratic, or something in between?
Show in the style of the example trace with shellsort, how shellsort sort sorts the array
E A S Y S H E L L S O R T Q U E S T I O N
Why not use selection sort for h-sorting in shellsort? how shellsort sort sorts the array
Instrument shellsort to print the number of compares divided by the file size for each increment. Write a test client that tests the hypthosis that this number is a samll constant, by sorting files of random Double values, using file sizes that are increasing powers of 10, starting at 100.

Creative Problems

Deck sort. Explain how you would put a deck of cards in order by suit (in the order spades, hearts, clubs, diamonds) and by rank within each suit, with the restriction that the cards must be laid out face down in a row, and the only allowed operations are to check the values of two cards and (optionally) to exchange them (keeping them face down).
Dequeue sort. Explain how you would sort a deck of cards, with the restriction that the only allowed operations are to look at the values of the top two cards, to exchange the top two cards, and to move the top card to the bottom of the deck.
Record sort test client. Add a toString() method to the Record.java class, then write a test client SortRecords that takes a command-line argument N, reads N lines from standard input (reading one String and one long from each line, making a record corresponding to each pair) sorts them using the natural order defined in Record, and prints the result onto standard output, one record per line.
User-defined comparable type. Develop a data type with test client that sorts the files described in the previous exercise by date rather than by numeric value.
Expensive exchange. A clerk at a shipping company is charged with the task of rearranging a number of large crates in order of the time they are to be shipped out. Thus, the cost of compares is very low (just look at the labels) relative to the cost of exchanges (move the crates). The warehouse is nearly fullthere is extra space sufficient to hold any one of the crates, but not two. What sorting method should the clerk use?
Correctness check. Write a check() method that calls sort() for a given array and returns true if sort() puts the array in order and leaves the same set of objects in the array as were there initially, false otherwise. Do not assume that sort() is restricted to move data only with exch(). The running time of your program should be subquadratic.
Animation. Add code to Insertion.java and Selection.java to make them draw the array contents as vertical bars like the visual traces in this section, redrawing the bars after each pass, to produce an animated effect, ending in a sorted picture where the bars appear in order of their height.
Hint: Use a client like the one in the text that generates random Double values, insert calls to show((Double[]) a) as appropriate in the sort code, and implement a show() method that clears the canvas and draws the bars.
Visual trace. Modify your solution to the previous exercise to make Insertion.java and Selection.java produce visual traces such as those depicted in this section.
Hint: Judicious use of setYscale() makes this problem easy.
Extra credit: Add the code necessary to produce red and gray color accents such as those in our figures.
Reflection. Write a version of the time() method for SortCompare.java that uses reflection to allow clients to name any sort (for which a .class file is available) at runtime.
Shellsort worst case. Construct an array of 100 elements containing the numbers 1 through 100 for which shellsort, with the increments 1 4 13 40, uses as large a number of compares as you can find.

Experiments

Web Exercises

Insertion sort with sentinel. Eliminate the array bounds check in insertion sort by putting the smallest element into position and using that as a sentinel. InsertionX.java is a version of insertion sort with half-exchanges and a sentinel.
Sorting networks. Write a program Sort3.java with three if statements (and no loops) that reads in three integers a, b, and c from the command line and prints them out in ascending order.
if (a > b) swap a and b if (a > c) swap a and c if (b > c) swap b and c

Oblivious sorting network. Convince yourself that the following code fragment rearranges the integers stored in the variables A, B, C, and D so that A <= B <= C <= D.

if (A > B) { t = A; A = B; B = t; }
if (B > C) { t = B; B = C; C = t; }
if (A > B) { t = A; A = B; B = t; }
if (C > D) { t = C; C = D; D = t; }
if (B > C) { t = B; B = C; C = t; }
if (A > B) { t = A; A = B; B = t; }
if (D > E) { t = D; D = E; E = t; }
if (C > D) { t = C; C = D; D = t; }
if (B > C) { t = B; B = C; C = t; }
if (A > B) { t = A; A = B; B = t; }

Devise a sequence of statements that would sort 5 integers. How many if statements does your program use?

Optimal oblivious sorting networks. Create a program that sorts four integers using only 5 if statements, and one that sorts five integers using only 9 if statements of the type above? Oblivious sorting networks are useful for implementing sorting algorithms in hardware. How can you check that your program works for all inputs?
Answer: Sort4.java sorts 4 elements using 5 compare-exchanges. Sort5.java sorts 5 elements using 9 compare-exchanges.
The 0-1 principle says that you can verify the correctness of a (deterministic) sorting algorithm by checking whether it correctly sorts an input that is a sequence of 0s and 1s. Thus, to check that Sort5.java works, you only need to test it on the 2^5 = 32 possible inputs of 0s and 1s.
Optimal oblivious sorting (challenging). Find an optimal sorting network for 6, 7, and 8 inputs, using 12, 16, and 19 if statements of the form in the previous problem, respectively.
Answer: Sort6.java is the solution for sorting 6 elements.
Optimal non-oblivious sorting. Write a program that sorts 5 inputs using only 7 comparisons. Hint: First compare the first two numbers, the second two numbers, and the larger of the two groups, and label them so that a < b < d and c < d. Second, insert the remaining element e into its proper place in the chain a < b < d by first comparing against b, then either a or d depending on the outcome. Third, insert c into the proper place in the chain involving a, b, d, and e in the same manner that you inserted e (with the knowledge that c < d). This uses 3 (first step) + 2 (second step) + 2 (third step) = 7 comparisons. This method was first discovered by H. B. Demuth in 1956.
Stupidsort. Analyze the running time (worst case and best case), correctness, and stability of the following sorting algorithm. Scan the array from left to right until you find two consecutive items that are out-of-place. Swap them, and start over from the beginning. Repeat until the scan reaches the end of the array.
for (int i = 1; i < N; i++) { if (less(a[i], a[i-1])) { exch(i, i-1); i = 0; } }
Consider also the following recursive variant and analyze the worst case memory usage.
public static void sort(Comparable[] a) { for (int i = 1; i < a.length; i++) { if (less(a[i], a[i-1])) { exch(i, i-1); sort(a); } } }
Stoogesort. Analyze the running time and correctness of the following recursive sorting algorithm: if the leftmost element is larger than the rightmost element, swap them. If there are 2 or more elements in the current subarray, (i) sort the initial two-thirds of the array recursively, (ii) sort the final two-thirds of the array, (iii) sort the initial two-thirds of the array again.
Guess-sort. Pick two indices i and j at random; if a[i] > a[j], then swap them. Repeat until the input is sorted. Analyze the expected running time of this algorithm. Hint: after each swap, the number of inversions strictly decreases. If there are m bad pairs, then the expected time to find a bad pair is Theta(n^2/m). Summing up from m =1 to n^2 yields O(N^2 log N) overall, ala coupon collector. This bound is tight: consider input 1 0 3 2 5 4 7 6 ...
Bogosort. Bogosort is a randomized algorithm that works by throwing the N cards up in the air, collecting them, and checking whether they wound up in increasing order. If they didn't, repeat until they do. Implement bogosort using the shuffling algorithm from Section 1.4. Estimate the running time as a function of N.
Slow sort. Consider the following sorting algorithm: choose two integer i and j at random. If i < j, but a[i] > a[j], swap them. Repeat until the array is in ascending order. Argue that the algorithm will eventually finish (with probability 1). How long will it takes as a function of N? Hint: How many swaps will it make in the worst case?