Work in pairs on this lab.
Write your own implementation of quicksort. You may use pseudcode and examples on pp. 533-540 in the textbook, but don't look at the implementation that starts on p. 540. Note that our types are somewhat different from what's given in the book.
Because quicksort is recursive you need a recursive helper method that indicates what portion of the array you are working on:
/**
* Sorts the portion of the given array arr[first..last]
* using a recursive quicksort algorithm
* @param <T> - the type of array elements (must be Comparable<T>)
* @param arr - the array to sort
* @param first - the index of the first element in the portion to be sorted
* @param last - the index of the last element in the portion to be sorted
*/
private static <T extends Comparable<T>> void quickSortRecursive(T [] arr, int first, int last)
This method should be called from a public method that doesn't take indices and make the first call to the recursive method:
public static <T extends Comparable<T>> void quickSort(T [] arr) {
quickSortRecursive(arr, 0, arr.length-1);
}
Make sure to test your code extensively and summarize your testing results.
Submit the java file(s) with your testing code by e-mail to me. The subject of the message must be 2101 Lab 9. Make sure to CC your group partner.