The CountingComparator class is similar to the Comparator interface except that it is a class, and it works with integers (and so cannot implement Comparator). In addition, it maintains a counter of the number of comparisons it has made. The class is to have a reset() method that resets the counter to 0, and a getCounter() method that returns the current (integer) value of the counter.

The QSort class should provide public methods quicksortNaive, quicksortWeiss, quicksortRandomNaive, and quicksortRandomWeiss. All four of these methods should implement the quicksort algorithm, and are to have a CountingComparator parameter as well as an integer array parameter. The output array is always to be the same as the input array. The length of the input array is always to be assumed to be equal to the length of the input sequence.

The quicksortWeiss method is to implement the tuned version of quicksort provided in the Weiss text. The quicksortNaive method is to use the last element of the input sequence or subsequence as a pivot element. The quicksortRandomWeiss and quicksortRandomNaive are to be the same as the two methods above, except that they apply a random permutation to the input sequence. Each possible permutation of the input should have an equal probability of being applied. The random portions of these algorithms should use a Random object constructed with an initial seed of 2.

All quicksort methods should use a CUTOFF value of 5, and use insertion sort for small arrays. If you give appropriate credit, you may use the insertion sort algorithm given in class A4, the insertion sort algorithm from Weiss's text, or Weiss's quicksort algorithm.

Note that since there are a number of different sorting algorithms used in this assignment, and a number of ways of implementing each, it is important to document the algorithm that you are using in each case. It should certainly be clear from your documentation how your algorithms differ, and how and why the code differs. You needn't document the behavior of any partition methods except to say that they implement partition algorithms, although you should carefully document the interpretation of the parameters, and any assumptions that these methods are making about the structure of the underlying array -- not every partition algorithm will work correctly with every version of quicksort.

If one of your quicksort algorithms isn't working, please comment out its definition so that the main function of class A4 won't crash. If you can't get CountingComparator to work, then you may rewrite test code to use the < operator. There will be a significant penalty if you do this, though. The penalty will be smaller if you use CountingComparator.compare but not the other methods of this class.

As always, you may define additional classes or methods that you find helpful or necessary.

For 10 points extra credit, augment your CountingComparator so that index comparisons for quicksorts may be counted only optionally. Assume that this option is disabled initially. You will need at least a method to enable the counting of these comparisons, and a new version of the compare method to identify those comparison which are to be counted only optionally. If you attempt this extra credit, then uncomment out the lines of A4.main. Don't forget to include the comparisons used in the cutoff check. Note that insertion sort always uses slightly more index comparisons than element comparisons.