CMPT 125/6 Assignment 2

In this assignment, you will explore the behaviour of various sorting algorithms. The goal is to have you experiment with the implementations of the algorithms and explore how they behave when given various types of input.

Creating Arrays for Testing

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 in this class 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:

public static float[] randomArray(int len) { … }

… 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 that last sentence is up to you, as are other details in how the arrays are generated, and what values they hold.

Implementing Sorting Algorithms

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 have been given pseudocode for these algorithms, but are expected to do the implementation yourself.

Tip: There are a couple of utility functions provided in the partial Sorts class. In particular, the isSorted function can be used to check your sorting function 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.

Measuring Running Time

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:

Timer t = new Timer();

// some operation that takes about 2 seconds;

System.out.println( t.time() );

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.

Timer t = new Timer();

int counter = 0;

for (int i=0; i<1000000; i++ ) {

    counter++;

    counter--;

}

System.out.println( counter );

System.out.println( t.time() );

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.

Experimenting

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.

Submitting

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 (no .class files) and submit it with the submission server.