CSci 2101 Lab 8. June 10th.

Due Monday, June 14th at 11:59pm

30 points

The lab is done in pairs.

Use Eclipse in this lab. If you run into any problems or would like to know more about it, please ask.

Please do not use the mergesort and quicksort code in the book for this lab.

Task 1

Finish implementing Mergesort started here. You may use the general description of mergesort on pp. 485-487, but not the code that follows. Test it thoroughly.

Task 2

Write your own implementation of quicksort. You may use pseudcode and examples on pp. 491-497 in the textbook, but don't look at the implementation that starts on p. 498. 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 with all your testing code by e-mail to me. The subject of the message must be 2101 Lab 8. 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.