## 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
}
}
```

#### How to submit:

Send me your code, including all your testing code. CC your group partner(s).

CSci 2101 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.