CSci 2101 Lab 10: quicksort

Work in pairs or groups of 3 on this lab.

Task 1: 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:


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.