Work in pairs or groups of 3 on this lab.
Your task is to write tests for, and then implement, quicksort sort. I recommend writing tests not for quicksort itself, but for the recursive helper function, as described below.
Write your code in the SortingMethods file that you used
for mergesort.
Quicksort should be a method declared similarly to mergeSort. It sorts an array in place, so the original array is sorted after the call to quicksort.
Because we would like to avoid extra memory use and
extra copying, we need to pass a portion of an array to a recursive
call. However, a portion of an array is not an array in
Java. Therefore we pass the original array and the beginning and
ending indices for the portion that we are sorting; let's call this
method quicksortPortion. The quicksort
method calls the recursive quicksortPortion, with the
indices 0 and arr.length - 1, to indicate that we are sorting the
entire array. The starting code is below:
There are two approaches to writing the partition function: one is described in the textbook and on the Quicksort wikipedia page (Lomuto scheme), the other one is the original Hoare scheme here (the second pseudocode example). We will go over both in class. You can implement either one.
public class SortingMethods {
/**
* The method sorts an array using quicksort sort
* @param <T> - the type of elements in the array (must extend Comparable<T>)
* @param arr - the array to be sorted
*/
public static <T extends Comparable<T>> void quicksort(T [] arr) {
quicksortPortion(arr, 0, arr.length - 1);
}
/**
* The method sorts a portion of the array between two given
* indices using quicksort algorithm. The method is recursive.
* @param <T> - the type of elements in the array (must extend Comparable<T>)
* @param arr - the array to be sorted
* @param begin - index of the first element of the portion to sort
* @param end - index of the last element of the portion to sort
*/
public static <T extends Comparable<T>> void quicksortPortion(T [] arr, int begin, int end) {
// fill in your code here
}
}
Send me your code, including all your testing code. CC your group partner(s).