CIT 594 Sorting Algorithms
Spring 2011, David Matuszek

Purposes of this assignment

• To begin the study of analysis of algorithms
• To learn something about sorting algorithms

General idea of the assignment

• Implement three sorting algorithms: Bubble sort, insertion sort, and quicksort.
• Provide JUnit 4 tests for each algorithm.
• Time each algorithm for different sizes of arrays.
• Write up your results.

In more detail

Implementing the algorithms

• Name your project SortingAlgorithms.
• Name your package sortingAlgorithms.
• Name your main class Sorts.
• In the Sorts class, implement the three sorting algorithms: Bubble sort, insertion sort, and quicksort.
  • You do not need to write these from scratch; you can find and adapt code from a textbook or from the web.
  • In the comments for each method, reference your source for the code (tell where you found it).
  • Adapt the sort methods to have exactly the following signatures (captialization matters; parameter name is irrelevant):
    • public static void bubbleSort(int[] numbers)
    • public static void insertionSort(int[] numbers)
    • public static void quicksort(int[] numbers)

Testing the algorithms

• Provide JUnit 4 tests for each of the sorting methods. Be sure to test extreme cases (arrays of length 0 and length 1).
• Generate the Javadoc files, and look them over (you will probably find things you forgot to document).

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.

• Close all other applications, so you don't have the computer doing too many other things during the timings.
  • Reason: System.nanoTime() gives "wall clock" time, not just time spent in your program.
• "Warm up" your program by executing all your methods at least once before you start timing.
  • Reason: The compiler may delay actually compiling your code until it is needed, so the first execution may be much slower.
• Call System.gc() before you begin timing.
  • Reason: So garbage collection doesn't happen during your timing runs.
• Run the code multiple times, and take the average.
  • For best accuracy, throw out the best and worst times, and take the average of the remaining times.
• As much as possible, try to include in your timing only the code you want to time.
  • A few assignments, comparisons, etc., aren't worth worrying about.
  • Filling the array with random numbers does take enough time to skew your results. Here are two possible strategies:
    1. repeat X times { randomize; start timing; sort; stop timing }
    • This strategy results in a lot of less accurate individual timings.
  2. start timing; repeat X times { randomize; sort } stop timing
     • With this strategy, you need to time the randomization method separately, and subtract it from the results.

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

• Use Eclipse (I recommend the "Classic" version) and Java 6. If you have not already done so, modify the Eclipse settings to replace tabs with spaces.
• Use good programming style
  • Don't mix input/output and significant computation in the same method.
  • Remember the KISS principle and the DRY principle.
  • Use good variable names, etc. etc. All the routine stuff.
  • Use Java formatting conventions, not C/C++ formatting conventions.
• Write Javadoc comments for all non-private classes, interfaces, constructors, and methods.
  • Use an @author tag (or tags, if working with a partner) in each class and interface.
  • Use @param, @return, and @throws tags in each class where they are applicable.
• Before you begin programming, estimate how long this assignment will take you.
  • Try to keep reasonably accurate account of your time.
• Except by special arrangement in very unusual circumstances, all projects are to be turned in via Blackboard.
  • Zip the entire project to turn it in. Do not use Microsoft's proprietary .rar format, which cannot be decoded on all systems.
  • Assignments submitted by email will be ignored.

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