Homework 2 Solutions

Exercise 6.5. Give all sequences of three compare-exchange operations that will sort three elements (see Program 6.1). The context of this and the next question is in Median-of-Three partitioning for Quicksort (Section 7.5). In Program 7.4, the first, middle, and last elements of the subfile to be sorted are arranged in order by the sequence of statements

compexch(a[l], a[r-1]);
compexch(a[l], a[r]);
compexch(a[r-1], a[r]);

(recall that the middle element has already been swapped into position r-1). The question is, what other sequences of compares and exchanges will guarantee that the three elements will be put in order? Suppose that our three elements are a[1], a[2], and a[3], and let us write i-j for the operation compexch(a[i], a[j]). Let's analyze the cases:

If the first operation is 1-2, then we know that the smaller of the first two elements will be put in position 1 and the larger in position 2. The second operation will have to compare one of these with element 3. If we compare 1 and 3, then we will know the smallest of the three elements; it should go to position 1, so the operation should be 1-3 (since 3-1 would put the smallest up in position 3). If instead we compare 2 and 3 on the second operation, then we will find out the largest element; we want it to go to position 3, so the operation should be 2-3. In either case, once we get the smallest or largest value in position, we just need to compare and exchange the other two values to get them in place, which gives us our third operation. This gives us two possible sequences starting with 1-2:
1-2, 1-3, 2-3
1-2, 2-3, 1-2
Now, if the first operation is 1-3, then similar reasoning gives us the following possible sequences:
1-3, 1-2, 2-3
1-3, 2-3, 1-2
If the first operation is 2-1, then that means that the smaller of the first two elements will be in position 2; if we now compare it against the value in position 3, we will find the smallest value after two operations, but it will be in either position 2 or 3, which does no good if we can only do one more operation to get the values in order. Therefore, the only choice we have for the second operation is to compare positions 1 and 3; this will find the largest value, so the operation should be 1-3 (since 3-1 would put the largest in position 1). After this, the third operation needs to arrange the smallest and middle values, so it must be 1-2. That is, we have found only one possible sequence starting with 2-1:
2-1, 1-3, 1-2
If the first operation is 2-3, then by reasoning similar to the first two cases we get the following possible sequences:
2-3, 1-2, 2-3
2-3, 1-3, 1-2
If the first operation is 3-1, then we are stuck. Comparing 1 and 2 will give us the largest value, but it won't be in position 3. Similarly, comparing 2 and 3 can find the smallest value on the second operation, but it can't put it into position 1. Therefore, no sequences of three compare-exchanges can start with 3-1.
Finally, if the first operation is 3-2, then we have a situation similar to the third case above, for 2-1. The second operation must be 1-3, which puts the smallest value in position 1. The third operation then has to be 2-3, so our eighth and final possible sequence is
3-2, 1-3, 2-3

Exercise 6.6. Give a sequence of five compare-exchange operations that will sort four elements. Here is one solution; I don't know how many there are: 1-2, 3-4, 1-3, 2-4, 2-3. The first two steps force the smallest item to be in either position 1 or 3, so the third step chooses between them and puts the smallest into position 1. The first two steps also force the largest item to be in either position 2 or 4, so the fourth step resolves the situation by putting the largest into 4. Finally, the two middle elements must be in positions 2 and 3, so the last step arranges them in proper order. Incidentally, it is easy to prove that these numbers cannot be improved. Since each compexch operation puts just two items in order, it can only cut the number of possible orderings of the elements down by a factor of two (the ultimate goal of a sorting procedure is to force any initial ordering into one particular one, so we can view each step as cutting down the range of possible permutations until only one remains). There are 6 possible orderings of three elements, so if two operations would only cut the possibilities down by a factor of 4, that is not enough. Similarly, there are 24 possible permutations of four elements (recall that, in general, there are n! permutations of n elements); four operations could only cut this down by a factor of at most 16, so they would not be sufficient.

Exercise 6.11. Show, in the style of Figure 6.2, how selection sort sorts the sample file E A S Y Q U E S T I O N.

$\begin{figure} \begin{center}\sf\setlength{\tabcolsep}{0pt} \begin{tabular}{cc... ...Light}{\makebox[12pt]{Y\vphantom{X}}} \end{tabular} \end{center} \end{figure}$

Exercise 6.14. Is selection sort stable? No. When placing a selected item into position, the item that was in that spot previously will be swapped to an arbitrary location in the unsorted portion of the file, possibly passing over other items with the same key. For example, look at the items S and S'X in the figure above.

Exercise 6.15. Show, in the style of Figure 6.3, how insertion sort sorts the sample file E A S Y Q U E S T I O N.

$\begin{figure} \begin{center}\sf\setlength{\tabcolsep}{0pt} \begin{tabular}{cc... ...mash Q\vphantom X}& S & S & T & U & Y \end{tabular} \end{center} \end{figure}$

Exercise 6.18. Is insertion sort stable? Yes. Since each item is moved to the left only as long as it passes items with strictly higher keys, the relative order of items with the same key will never change.

Exercise 6.22. Is bubble sort stable? Yes. As each item bubbles to the left, it stops when it sees an item whose key is less than or equal to its own; therefore, no item will pass another item with the same key.

Exercise 6.26. Which of the three elementary methods (selection sort, insertion sort, or bubble sort) runs fastest for a file with all keys identical? Insertion sort will be the fastest, because it only has to make N - 1 comparisons and no exchanges. Bubble sort (with the optimization that it quits after a pass in which no exchanges are performed) will be almost as fast, except it needs to do the extra work to check whether the file is sorted after making the pass. Bubble sort without that optimization will use about N²/2 comparisons, as will selection sort.

Exercise 6.27. Which of the three elementary methods runs fastest for a file in reverse order? Selection sort will be the fastest, because while all three methods perform about N²/2 comparisons in this case, selection sort will only do about N/2 exchanges; the other two will each do about N²/2 exchanges (every comparison results in an exchange).

Exercise 6.33. Is shellsort stable? No. When the file is k-sorted for a value of k > 1, it is possible for two items with the same key to switch positions (if they are not a multiple of k positions apart, they will not be compared with each other in a k-sort). For example, look at the items S and S'X in the next question.

Exercise 6.35. Give diagrams corresponding to Figures 6.8 and 6.9 for the keys E A S Y Q U E S T I O N. Using the increment sequence 1 4 13 ..., we only need to perform a 4-sort followed by a 1-sort. For the 4-sort, first here is the diagram corresponding to Figure 6.8:

$\begin{figure} \begin{center}\sf\setlength{\tabcolsep}{0pt} \begin{tabular}{cc... ...t}{\makebox[12pt]{S\vphantom{X}}} & Y \end{tabular} \end{center} \end{figure}$

Now the only part we need to show corresponding to Figure 6.9 is the 1-sort:

$\begin{figure} \begin{center}\sf\setlength{\tabcolsep}{0pt} \begin{tabular}{cc... ...t}{\makebox[12pt]{U\vphantom{X}}} & Y \end{tabular} \end{center} \end{figure}$

Exercise 7.1. Show, in the style of the example given [in Section 7.1], how quicksort sorts the file E A S Y Q U E S T I O N.

$\begin{figure} \begin{center}\sf\setlength{\tabcolsep}{0pt} \begin{tabular}{cc... ...ash Q\vphantom X}& S & S & T & U & Y \end{tabular} \end{center} \end{figure}$

Exercise 7.8. About how many comparisons will quicksort (Program 7.1) make when sorting a file of N equal elements? Examining the partitioning step in Program 7.1 reveals that when all the keys are equal it will arrange to put the pivot right in the middle for each subfile. Since the subfiles decrease in size by a factor of 2 on each recursive call, there will be log₂N levels of recursion with about N comparisons on each level, for a total of about N log₂N comparisons. This is the best case for quicksort, except for all of the needless exchanges done while partitioning--since every element is equal to the pivot, every element will be swapped to the other side.

Exercise 7.9. About how many comparisons will quicksort (Program 7.1) make when sorting a file consisting of N items that have just two different key values (k items with one value, N - k items with the other)? When I assigned this problem, I didn't realize what a proper solution would involve. Since this is not really a full-fledged course in algorithm analysis, we will not look at a complete solution to this problem. However, an approximate answer comes from the observation that after the first partitioning pass, one of the partitions will contain all equal elements, while the other may contain a mixture (because some of the elements equal to the pivot may have been swapped over to that side). Even the partition with a mixture of elements will probably be more homogeneous than the original, though, because it will contain all of the elements different from the pivot, plus only a few of the elements equal to the pivot. Therefore, after a few passes, each subfile will contain only one kind of element. According to the previous exercise, these will continue to be split evenly until subfiles with only one element are reached; since most of the passes will split the subfiles evenly, there will be about log₂N levels of recursion, so again we find about N log₂N comparisons.