CSci 2101 Lab 9. June 13th.

Work in pairs on this lab.

Due Wednesday, June 15th at 11:59pm

30 points

Quicksort

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.

How to submit

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.


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.