The methods are to be called sortSelect, treeSelect,heapSelect, quickSelect, and stringSelect. The first of these is to sort the entire sequence, and then find the kth smallest element directly. The second method is to insert the data into an AVL tree and find the kth smallest as in Assignment 2. You needn't use message passing for the AVL methods. The third method is to implement the strategy of Section 6.4.1 of the text. In this case, you may assume that the heap size does not exceed 1000 as long as you document this constraint.

The fourth method is to use the algorithm of p. 251 of the text, with a CUTOFF value of 5. The fifth method should assume that its input sequence has Strings as elements. It is to work in a way analogous to bucketsort -- by assigning strings to buckets according to the first character of the string, determining which bucket contains the output string, and then finding the appropriate string in that bucket. To find the appropriate string with a bucket, you may use recursion, or you may simply sort the bucket.

For the first and last of these methods, you may use any sorting algorithm that you want, as long as your version of the algorithm works correctly with the CountingComparator argument as described below. Your sorting algorithms may use case-sensitive comparisons. Note that one of the Collections.sort methods is already set up to use Comparators.

Your selection methods may mutate the ArrayList argument only if they simply permute it. Note that a selection method should return the same value for the permuted sequence as for the original sequence.

You should write your selection methods under the assumption that only one selection will be done per data structure. In particular, you won't be judged on how well one invocation of a selection method improves the performance of later ones.

The CountingComparator argument is to compare the number of element comparisons used by each of the four selection methods, including any comparisons used by a separate sorting method. You needn't define this class, it is already defined for you. You will need to make sure that your selection methods compare elements by using the compare method of the Comparator interface, which the CountingComparator implements.

The compare method is only guaranteed to work when the compareTo method would work for its arguments (and thus not, for example, when comparing two objects of different classes). You may simply propagate any ClassCastExceptions thrown by your selection methods, but you should document this issue in those methods.

The tree and heap classes used by treeSelect and heapSelect need not provide a zero-argument constructor. All constructors for these classes may take a CountingComparator argument.

You may of course use the time complexity results known for the various algorithms to check whether your numbers of comparisons are reasonable. Note that these counts may be a little unfair to certain methods, since they don't include time to copy sequences or assign strings to buckets. An algorithm (that's not particularly practical) for this problem with O(n) worst-case time complexity is given in Section 10.2.3.

Use the test file A4.java (available on the class web site) to test your implementation. Also use the CountingComparator.java file provided on that web site. As always, you may define any additional classes or methods that you find useful, including portions of your solution (or my solution) to earlier assignments. Note that some of these methods will need to be rewritten to work with ArrayLists and CountingComparators.