CIT 594 Sorting Algorithms
Spring 2014, David Matuszek

Purposes of this assignment

General idea of the assignment

In more detail

Implementing the algorithms

Testing the algorithms

Timing the algorithms

Time each of your algorithms on sorting random arrays of size N, ½N, and ¼N, for some very large value of N.

Important note: Sorting algorithms behave differently on arrays that are already sorted, so be sure to do your timings on arrays in which the contents are in random order.

Here's the basic technique for timing code:

long startTime = System.nanoTime();
// Code to be timed goes here
long elapsedTime = System.nanoTime() - startTime;

The call System.nanoTime() requests the system to use the most accurate timer available, which is very likely to be accurate only to milliseconds, so don't be surprised if a single sort operation takes "zero" time.

Timing tips

Here are some tips for helping to get reasonable accuracy.

Writing up the results

Include a readme.txt file with your submission. This file should briefly describe the details of your tests (array sizes, timing strategy, anything else you think is relevant), and at least twelve timing averages (four sorting algorithms × three array sizes). Also include your estimate of how much time this assignment would take, and how much it actually took.

You don't need to write an essay! A few sentences, with some clearly labeled numbers, should be enough.

Supplied code

You can use the following code to randomize an array:

/**
  * Randomizes an array in place.
  * 
  * @param array The array to be randomized (shuffled).
  */
 public static void randomize(int[] array) {
    java.util.Random rand = new java.util.Random();
    for (int i = array.length; i > 1; i--) {
        int choice = rand.nextInt(i);
        int temp = array[choice];
        array[choice] = array[i - 1];
        array[i - 1] = temp;
    }
}

General requirements (read this!)

Grading

Programs are graded on the basis of 100 points each, and will constitute 50% of the course grade. The general requirements given above apply to all assignments; specific requirements are spelled out in each assignment. If I forget to specify something, you can (a) ask me what to do, or (b) do something "reasonable." I'll try to be liberal about what I think is reasonable. (Note: Letting the program crash is seldom reasonable).

Due date

Turn your assignment in to Canvas before 6 a.m. Thursday, January 30. Late programs, even if only a minute late, will be penalized 10 points for the first week. Programs later than a week may or may not be accepted for grading.