In a class CreateArray, create some function that will generate arrays that can be used to test the various sorting algorithms. Since different sorting algorithms have different behaviour when given different inputs, you need to create several different types of arrays for any tests you do to be meaningful.

All of the methods to create arrays will take a single integer argument: the length of the new array. Each method should return an array of float values. So, for example, the first method listed below will be defined like this:

and should return an array of length len.

randomArray

Create an array filled with unsorted random float values. As in lab 4, the Random class will help here (but you are generating floats here, not ints).

sortedArray

Create an array filled with random float values that are in increasing order.

reverseSortedArray

Create an array filled with random float values that are in decreasing order.

almostSortedArray

Create an array filled with random float values that are almost in increasing order.

Exactly what almost means in almostSortedArray is up to you, as are other details in how the arrays are generated and what values they hold. Informally an almost-sorted array should be one that doesn't have to be changed "a lot" to get a sorted array.

The class Sorts will hold functions that implement various sorting algorithms. A partial Sorts class has been provided. It contains an implementation of selection sort and quick sort.

There is also a function there that wraps the built-in sorting function. The built-in sorting function is a well-optimized implementation of quick sort.

Add an implementation of insertion sort and merge sort, as discussed in lecture. You actually have already been given an implementation of insertion sort in class, but only pseudocode for merge sort. You are expected to do the implementation of merge sort yourself.

You also need to add a support method isSorted that takes an array of floats and returns true if the array is sorted.

Tip: The utility function isSorted can be used to check your sorting functions when completed, to make sure they're actually working: run the sorting function, then call Sorts.isSorted(array) to make sure it worked.

Tip: when working on merge sort, you might find it useful to use the built-in sorting algorithm for recursive sorting calls. You can then be sure that much is working while you're testing your merge implementation. Remove this call and replace with real recursive calls to the merge sort function once you're sure the merge is working. You don't always have a luxury of a working algorithm to call when debugging a recursive function, but you might as well use it when it's available.

The last thing you'll need to experiment with the running times is some way to actually measure the time it takes for the function to run.

Create a class Timer that describes an object that allows this. (Note: we're creating an object class here: no static methods.)

When a Timer object is instantiated, it should record the current time. When its time() method is called, it should return the number of milliseconds that have passed since the instantiation. For example, this should print out a number around 2000:

You'll need to use the System.currentTimeMillis() function. This function returns the number of milliseconds since some arbitrary starting point (the epoch). So, if you record the value returned by System.currentTimeMillis() in the constructor and again in the time() method, the difference is the number that you should return.

For example, this code takes between about 6 and 60 milliseconds (the second value printed) on my machine, depending on the Java implementation I tried.

Note that the length of time it takes to run particular code will vary from run to run. The exact value depends on what else the computer is doing, whether or not the Java VM does garbage collection, disk and memory cache contents, etc. You should always do several tests to be sure you didn't get an outlying value.

For this section, you will have to use the code created in the above sections. The goal here is to test the sorting algorithms on various inputs to determine how they behave. You should be able to correlate the behaviour you see when testing with the design of the algorithm.

Test the various algorithms in Sorts (including the built-in sorting method from Arrays) with the different types of arrays generated by CreateArray. What trends do you see? Some things you might want to look for:

• Which sorting functions are faster? Do you think the differences are in the big-O or in the constant factor?
• Do some of the algorithms behave significantly differently based on the input they are given? Some do; some will take about the same amount of time no matter what they are given.
• If there are problems highlighted by the above, could they be fixed in the implementation, or are the inherent to the algorithm?

Write a brief report (around one page, definitely not more than two) summarizing your results. Valid formats for the file: plain text (summary.txt), HTML (summary.html), Acrobat PDF (summary.pdf). No other formats will be opened or marked.

Tip: Make sure you test with arrays that are large enough to get meaningful results. Times less than a second are going to be too sensitive to variation in running conditions. This will probably mean that you'll end up testing the O(n²) algorithms and O(n log n) algorithms separately.

Tip: Do several runs of each test, to make sure you don't have results that are skewed by something your computer was doing at that moment (receiving an email, writing data to disk, getting a virus, etc.)

Tip: be careful to only count the time taken to do the sorting, not the time taken to create the array, check the results, etc.

All of your assignments in this class will have some marks allocated for style. This will include easy to understand and modify code. In particular, you should use comments where appropriate, use good variable names, split your code into methods/functions logically, and indent consistently.

When you're done, create a ZIP file containing all of the files you created for this assignment and submit it with the submission server before midnight on October 20th.