Assignment #5

Due November 27.

This assignment is to implement and compare four sorting algorithms,

  • Insertion Sort

  • Heapsort or Shellsort

  • Quicksort using as an arbitrary pivot the rightmost element in the range to be sorted (bad)

  • Quicksort using a median of three pivot (pretty good)

You should write your code to sort only integers (which means you will have to modify any code taken from the text to use type int instead of a generic type). Use a single class that contains the four algorithms as static methods. The class should also include a single static array large enough to hold your largest sort. 
		public static final int DIMENSION = 260000;
		public static int[] A = new int[DIMENSION];
		...
You should pass this array to each of your sort methods as a parameter, along with a second parameter which indicates how much of the array needs to be sorted. In addition your class should contain a randomFill(int[] A, int size) method which fills the array with random numbers, and a printSample(int[] A) method which prints out a small portion of an array so that you can tell whether it has been correctly sorted. Finally, the class needs a driver which calls the different sorts passing different size arrays, times the sorting, and produces output.

Sorting Algorithms

The Insertion Sort should not include a binary search for inserting.

Heapsort should use a linear buildHeap method. ShellSort should use good increment sequence.

You should write the Quicksorts to use a cutoff (10 is used in the text -- but you may want to experiment with different values between 4 and 100 to see what the most effective cutoff is). You should also write Quicksort so that it cleans up using Insertion Sort--but only after the Quicksort is entirely finished (by making one complete pass through the entire array not, as in the text, by cleaning up each small segment left after the cutoff). This means that your timing for Quicksort should continue until the Insertion Sort has finished cleaning up. Finally, you should either provide a switch in your Quicksort method to allow you to choose between using an arbitrary pivot and a median-of-three pivot or write two different versions of Quicksort. For the arbitrary pivot choose the rightmost element in the array, A[right],and be aware that this choice might have repercussions for the remainder of Weiss's code. Your driver should print out the results for both versions of Quicksort.

Driver

Write a driver which will call each of the sort methods for the following sizes of input: 1000, 2000, 4000, 8000, 16000, 32000, 64000, 128000 and 256000. Your driver should time each sort method for each size. Sizes can be conveniently iterated by a loop: 

    	for (int i = 0; i <= 8; i++) {
		size = 1000 * Math.pow(2,i);
You will also need to test each sort on both random and previously sorted input. (You can get previously sorted input by simply sorting the array before you start the timer--pick an efficient sort for the first sort.)

Output

Output should include first a small section showing that each sort method works. This can simply be a listing of a portion of the array both before and after it has been sorted (once for each routine--using a single size).

The second section should show the elapsed time for each sort. Altogether there are 72 sorts to be measured: 4 sorts (including 2 versions of Quicksort) * 9 sizes * 2 variations of input (random and previously sorted). So this section should provide 72 lines of output. Each line should identify the sort, the number of items being sorted, and the elapsed time. You may organize this output in any reasonable fashion, but just output the timing information--do not include a listing of array values in this second section.

Submit both the source and a hard copy of the output.

EXTRA CREDIT: Add whichever of HeapSort or ShellSort you left out.