Programming and Computer Science in Java:
Homework #16:  Sorting Review and Analysis
    David Kosbie, 2002-2003
See Course Home Page

Due Date:  Tue, April 1, 2003

Question 1:  Check out the code in sortDemos.java (also available as sortDemos.htm) -- you are responsible for all of it!  This code contains a number of Java techniques which may be somewhat new to you.  Any and all of these may appear on the upcoming quiz.  Your assignment here is to make a list of all the new or confusing Java techniques you can find in this file.  You are to share this list with your classmates by posting it to the perry2 mailing list.  You are also to ask questions and, as much as you can, answer other students' questions.  Together, you will collectively uncover all the hidden pearls in this code and you will collectively come to understand how they work.

Question 2:  For each of the 5 sorts that we covered (bubblesort, insertionsort, selectionsort, mergesort, and quicksort), you are to create a hand-written graph where the x-axis contains the size of a random array, and the y-axis contains the time, in seconds, to sort that array.   Note that the code in sortDemos.java is instrumented to support this kind of timing.

Question 3:  Try to speed up quicksort by using more sophisticated techniques for selecting your pivot.  Come up with at least three different techniques, and write the code for each.  Compare the performance of each, and conclude which, if any, performs better than the others.

Question 4:  Study for a quiz tomorrow (that is, the quiz is on Tuesday, April 1st) on sorting.

Good luck!

DK


See Course Home Page