## CSci 2101 Lab 8: quicksort

### Due: Monday April 3 at 11:59pm

Work in pairs or groups of 3 on this lab.

#### Testing and implementing quicksort sort (30 points)

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
}

}
``````