The CountingComparator class should implement the Comparator interface. Its compare method may assume that its arguments are Comparable objects, and it may throw a ClassCastException if its arguments cannot be compared by compareTo. The class should also maintain 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 Sorter class should provide public static methods quicksortNaive, quicksortWeiss, newQuicksortWeiss, and insertionSort. The first three of these methods should implement the quicksort algorithm. However, the parameters for these three methods should be

1. an ArrayList that contains the sequence to be sorted (and will contain the output sequence after the sorting is complete). You may assume that the sequence fills the entire ArrayList.
2. a cutoff value to be used by the algorithm. Sequences or subsequences with a length that is less than or equal to this value should be sorted by insertion sort.
3. a CountingComparator parameter that determines how pairs of elements are to be compared, and that maintains the count of element comparisons

The quicksortWeiss method is to implement the tuned version of quicksort provided in the Weiss text, with two modifications. First, the parameters above should be used as directed. In particular, no fixed CUTOFF value should be used. Secondly, the method should compute and return the maximum depth of recursion used in the computation.

The newQuicksortWeiss method is to behave like quicksortWeiss, except that it works first on the smaller of the two subproblems, and postpones the larger, in order to minimize the maximum depth of recursion (and thus the maximum stack size). The quicksortNaive method is to use the first element of the input sequence or subsequence as a pivot element. It is to use the parameters above as directed, but it need not compute the maximum recursion depth or return any value.

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 is crashing, please comment out its definition so that the main function of class A4 won't crash. If you can't get the quicksort methods that return integers to return the proper values, please have them return 0.

If you give appropriate credit, you may use the insertion sort and quicksort algorithms from Weiss's text. As always, you may define additional classes or methods that you find helpful or necessary.