Project 0

Assignment Due 18 April

Intro
This homework is to allow you to refamiliarize yourself with Java and to understand asymptotic analyis a bit better. For this homework you will need to submit three things: A library file that contains 4 sorting algortithms, a graph indicating the runtime performance on a given task, and a modified coord object Each item is detailed below.

Sorting Library
I want to see a single .java file that contains 4 sorting algoritms: bubble sort, selection sort, merge sort, and partition sort. You may use our class code as a starting point. Your sorting functions should sort arrays of Comparable objects as we finally ended up doing in class. The idea is to have a library of sorting functions that are generic across all objects.

Graph
You will need to sort arrays of coord ojbects . You will be using both the methods in the above library and Java's built in sort. To this end, you will need to have the coord object implement the Comparable interface. In this case we wish to sort based off of the distance from the origin (0,0). Modify this object and submit it along with your home work.

You will test all four sorting algorithms, plus the standard java sorting algorithm, on sizes of the array between 100 and 20,000 in increments of 100 (ie: so, test it on arrays of size 100,200,300,....20,000). For each algorithm, for each size of the array, generate a random array of coord objects and sort them 10 times. So, run bubble sort ten times on arrays of size 100, then ten times on arrays of size 200, then ten times on arrays of size 300, etc. Do the same for selection sort, partition sort, merge sort, and java's built in array sorting. Provide a line chart that has the array size as the x asix and the average time in miliseconds on the y axis.

Please answer the following questions in the email you use to turn this in. What sorting algorithm has an average run time closest to the java built in sorting algorithm? Is the java sorting algorithm better than all the other sorting algorithms? Which algorithm is the best for all sizes of the array? If there is no best, for what sizes of the array would you use which sorting algorithm.

Java has built in timing mechancishms. Please observe the following program.