1. Create a class Pair which stores two variables: key and value. Both fields should be generic implementing Comparable. Pair should have constructors, setters, getters, and a toString() method which relies on the toString() methods of the fields. (Every class in Java inherits a toString() method from the Object class, if this is not overridden elsewhere!)

2. Create a MAL class extending AL of Pair. MAL should also have a toString() method, a qs() method implementing quicksort as in Figure 8.22, a stableQs() method implementing a stable adaptation of quicksort (if , and a binarySearch() method implementing binary search for a given value, returning the first matching Pair or null if no matching pair is found. Use the following for stableQs(): Create an auxilliary MAL of Pairs; each Pair is to contain the initial position in the old MAL as key and the old value as value. Then sort the array; if two Pairs have identical values, use the key to break the tie. After the new MAL has been sorted, rearrange the original MAL accordingly.

3. Fully unit test all the classes. You should have at least one test case demonstrating that stableQs() provides a stable sort of some input for which qs() does not. Have these tests display pre and post sorting lists.

/** * Quicksort algorithm (driver) public static > void quicksort Any Type [ ] a) quicksort( a, 0, a. length - 1); figure 8.22 Quicksort with median-of-three partitioning and cutoff for small arrays * Internal quicksort method that makes recursive calls. * Uses median-of-three partitioning and a cutoff. 13 - 14 private static > void quicksort Any Type [] a, int low, int high ) 15 16 if( low + CUTOFF > high ) insertionSort( a, low, high ); else { // Sort low, middle, high int middle = (low + high ) / 2; if( a[ middle ). compareTo( a low ] ) = j) break; swapReferences( a, i, j); // Restore pivot swapReferences( a, i, high - 1); quicksort( a, low, i -1); quicksort(a, i + 1, high ); // Sort small elements // Sort large elements 49 51