Laboratory: Sorting It Out
 CSC 207 Algorithms and Object Oriented Design Spring 2011

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.
Created: Jerod Weinman, 9 January 2009
Modified: Jerod Weinman, 19 March 2010
Modified: Jerod Weinman, 18 January 2011

Adapted from Mark Allen Weiss, Data Structures and Problem Solving Using Java 3/e Exercises 8.20 and 8.14.