CIT 594 Sorting Algorithms
Spring 2014, 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 four sorting algorithms: Bubble sort, insertion sort, selection 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 four sorting algorithms: Bubble sort, insertion sort, selection sort, and quicksort.
  • Do not write these methods from scratch; find and adapt code from my lectures, or 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 selectionSort(int[] numbers)
    • public static void quicksort(int[] numbers) // note capitalization!

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

• 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 twice before you start timing.
  • Reason: The compiler may delay optimizing your code until it is needed, so the first few executions 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 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!)

• Use Eclipse (I recommend the "Classic" version) and Java 7.
• 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.
    • If you have not already done so, tell Eclipse to replace tabs with spaces.
• Write Javadoc comments for all non-private classes, interfaces, constructors, and methods.
  • In this assignment, the comments for each sorting method should specify where you got it from.
  • Use an @author tag in each class and interface.
  • Use @param, @return, and @throws tags for each method 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 Canvas.
  • Zip the entire project to turn it in.
  • 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).

Due date