Homework 5

A. Reimplement the selection sort algorithm so that it works with an Object[] array and a Comparator.

Provide a Homework5ATester program that uses an inner class CountingComparator, which increments a counter every time the compare method is called. Use your selection sort to sort an Integer[] array—specifically the one on pages 526 - 527 of your textbook. Then print the actual and expected counts.

...
System.out.println(comp.getCount());
System.out.println("Expected: ...")

Here is a tester, with a comparator that doesn't count. The netbrat tester is here. Submit files SelectionSorter.java and Homework5ATester.java.

Draft: Just get the SelectionSorter to work with a Comparator.

B. It's easy to sort an array of length 3. If a[0] and a[1] are out of order, swap them. If a[1] and a[2] are out of order, swap them. One more compare-and-swap (that you get to figure out), and you are done.

Implement the following algorithm:

While the array is not sorted
 For each adjacent triple of elements starting at 0, 2, 4, 6, ...
   Sort the triple

Complete this class. The netbrat tester is here. Submit file ThreeSorter.java

Draft: Just complete the sortThree method.

C. Complete P14.9. Also, print the ranges that you are merging, exactly in the following format:

Merging 0...1 and 2...3

For example, when sorting an array of length 16, the output is

Merging 0...0 and 1...1
Merging 2...2 and 3...3
Merging 4...4 and 5...5
Merging 6...6 and 7...7
Merging 8...8 and 9...9
Merging 10...10 and 11...11
Merging 12...12 and 13...13
Merging 14...14 and 15...15
Merging 0...1 and 2...3
Merging 4...5 and 6...7
Merging 8...9 and 10...11
Merging 12...13 and 14...15
Merging 0...3 and 4...7
Merging 8...11 and 12...15
Merging 0...7 and 8...15

Complete this file. The netbrat tester is here. Submit file MergeSorter.java

Draft: Just print the messages. Don't actually do any merging. You can do this part without knowing what merge sort does. In the test, the "Merging" lines should match up, but the last line, which prints the array after sorting, won't yet match. That's ok.