Due: Thursday 6/26/14 @5:30pm via users.cs.umb.edu:cs210/hw4

Purpose: To analyze an algorithm for computational cost with respect to input size. To determine the best and worst case performance of an algorithm.

1. Implement QuickSort and Insertion Sort in files QuickSort.java and InsertionSort.java with (at least) the following method:

public void sort(Comparable[] arr);

2. Write a class Eval that runs this method on three different types of inputs. Random input, Sorted input and Reversed input. Time how long each input takes on your Quicksort.sort, Arrays.sort, Insertion.sort (From slides) and output their runtime. Create your input arrays so that your code should run between 1 to 5 seconds total (To make it easy to grade).

3. Write a memo.txt describing what you observe about the algorithms.

You can use this timing code:

long startTime = System.currentTimeMillis();
// do something
long endTime = System.currentTimeMillis();
long duration = endTime - startTime;
System.out.println("Time taken: " + duration + "ms");

To generate some random input you can use Math.random() like this:

int N = 20;
Integer[] arr = new Integer[N];
for (int i = 0; i < arr.length; i++) {
	arr[i] = (int)(Math.random()*999);
}
System.out.println(Arrays.toString(arr));

Your code should output like this:

$ java -cp . Eval
Creating random input..
 Arrays.sort : __ ms
 Quicksort.sort : __ ms
 Insertion.sort : __ ms
Creating ascending sorted input..
 Arrays.sort : __ ms
 Quicksort.sort : __ ms
 Insertion.sort : __ ms
Creating descending sorted input..
 Arrays.sort : __ ms
 Quicksort.sort : __ ms
 Insertion.sort : __ ms

Grading (total 10 points):

Turn in the following files: Quicksort.java, Insertion.java, Eval.java, and memo.txt

2 points: QuickSort working

2 points: Insertion Sort working

3 points: Runtimes calculated correctly

3 points: memo.txt, easy to grade, and runs between 1 and 5 seconds.