Summary: In this lab, you will gain greater exposure to the theoretical and practical finer points of sorting.

Preparation

1. Create a directory for this lab:

     mkdir somewhere/sorting

2. Go to your new directory:

     cd somewhere/sorting

3. Copy the files for this lab to your new directory:

     cp ~weinman/public_html/courses/CSC207/2011S/labs/code/sorting/TrackingComparable.java .
     cp ~weinman/public_html/courses/CSC207/2011S/labs/code/sorting/Sort4.java .
     cp ~weinman/public_html/courses/CSC207/2011S/labs/code/sorting/TestSort4.java .
       

Exercises

Exercise 1

We started with a discussion of the lower bound for comparison-based sorting. Here we'll try to reinforce that.

1. Say we have 4 elements to sort using only comparison operations. How many possible permutations of these four elements are there? (Remember, only one of them is sorted!)
2. If we make a comparison so that we know the ordering of two of these elements, what proportion of the possible permutations have we eliminated?
3. Ok, now apply the previous two questions in succession (or use the closed form you should know): How many comparisons must it take to sort four items?

   (You may wish to verify this with others near you.)

Exercise 2

1. Find an algorithm for sorting four elements A,B,C, and D with this minimum number of comparisons.

   Hint, you may want to start by putting the first two items in order and the last two items in order. ... that takes two comparisons. Then try to get the max and min items in place (two more comparisons). Then just one step left ...

2. The class Sort4 contains an ArrayList of Comparable objects called items. Fill in the body of the doSort() routine with your algorithm. You should use the get method of ArrayList on items, the objects' compareTo methods, and the Sort4 object's swap(i,j) routine provided.
3. Implement isSorted() using either a for loop or three comparisons.

Exercise 3

A TrackingComparable object HAS-A Comparable object, but also implements the Comparable interface, so that it can add functionality to the compareTo call (in order to count the number of times it has been used). What design pattern is this?

Exercise 4

The file TestSort4 iterates through all the permutations of 4 non-equal integers, creates a Sort4 object and verifies the number of comparisons and (trustingly) whether the objects are sorted.

Use this class to test and verify your implementations from Exercise 2. If they are all in the same directory, you should be able to run

  java TestSort4

after compiling it of course. If it reports no errors, then your code is presumably correct. If it does report errors, be sure fix them!

Exercise 5

1. Download the book's implementation of the various sort routines here.
2. Find the full implementation of quick sort (Line 190). Notice that, in lines 211-216 (inclusive), i is initialized to low but is immediately incremented. Similarly, j is initialized to high-1 and is immediately decremented. What would happen if we changed lines 211-216 (inclusive) to the following, modifying the initialization and moving the increment/decrement to inside the while loops.

     for ( i = low+1, j = high-2 ; ; )
     {
       while ( a[i].compareTo( pivot ) < 0 )
         i++;
       while ( pivot.compareTo( a[j] ) < 0 )
         j--;

   Is the result equivalent to the original routine? You might trace through some examples by hand to determine whether it is.
3. Change your copy of Sort.java to reflect the changes given above.
4. Run the following code using your modified sort:
   Driver.java

   public class Driver {
     public static void main(String[] args) {
       Sort.quicksort( new Integer[] {5,3,3,2,1,3,2,1,4,7,2});
     }
   }

5. What happens?
6. Use a debugger to step through the code and inspect variables or add println statements to determine why.