CIT 594 Sorting Algorithms
Spring 2011, 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 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 nine timing averages (three 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 sentence or two, with some clearly labeled numbers, should be enough.

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).

Last semester we were unable to grade programs as carefully as we would like, so program grades were artificially high. We expect to improve that this semester, yielding more accurate grades.

Late programs will be penalized 5 points per day, to a maximum of 35 points. Programs later than a week may or may not be accepted for grading.

Due date

Turn your assignment in to Blackboard before 6AM Thursday, January 20.