CIT 594 Assignment 2: Sorting
Spring 2008, David Matuszek

Purposes:

To teach some basic sorting algorithms
To get you familiar with the idea of profiling
To demonstrate a basic simulation technique

General Idea:

Implement and profile three simple sorting techniques (bubble sort, selection sort, and insertion sort). These should each sort the array into ascending order (smallest to largest).

Test two shuffling (randomization) techniques, and see whether they behave as expected.

Details:

Sorting

Implement the three named sort methods for integer arrays. (You can copy the code from my slides or from a textbook.) Fill an array of 1000 locations with the numbers 0 through 999. That is, array location i should contain the number i, for each 0<=i<=999.

For each of the three sorting techniques,

Sort an already sorted array, and observe how long it takes.
Sort an array that is in reverse (descending) order, and observe how long it takes
Sort an array that has been shuffled by one of the following randomization algorithms, and observe how long it takes.

This is a total of nine tests (three sorting techniques times three initial conditions). Use NetBeans's profiling capabilities to find the relative execution times of each of the nine situations. (Remember the DRY principle, and avoid duplicating code.) Write up your results.

Shuffling

Here are two methods for shuffling an array:

    private static void shuffle1(int[] array) {
        int length = array.length;
        for (int i = 0; i < array.length; i++) {
            int index = rand.nextInt(length);
            int temp = array[i];
            array[i] = array[index];
            array[index] = temp;
        }
    }    

    private static void shuffle2(int[] array) {
        int length = array.length;
        for (int i = array.length; i > 0; i--) {
            int index = rand.nextInt(i);
            int temp = array[i - 1];
            array[i - 1] = array[index];
            array[index] = temp;
        }
    }

Are these two shuffle methods equally good? With a "perfect" shuffle, every element would have an exactly equal chance of ending up in any given location. So, for instance, if we shuffled a ten-element array ten thousand times, each number in the array should end up in the first location about a thousand times. (Of course, if it really is random, we wouldn't expect this to happen exactly a thousand times!)

Try this out. Set up a ten-element array containing the numbers 0 through 9, shuffle the array ~~one hundred thousand (100000)~~ ten thousand times, and see how often each element ends up in each location. You can keep track of the results in a ten by ten array: array[i][j] keeps count of how many times number i ends up in location j. Do this for each of the two shuffle methods, and print the results. Look at the results to see whether one shuffle method looks better than the other. Also find and print the largest and smallest number in each of the two arrays, to see how close to 1000 they are.

Other stuff

Javadoc

You should provide high-quality javadoc for your class or classes, for all methods, public and private, and for all static and instance variables. And, of course, you should use internal comments to describe any non-obvious code.

Exception: JUnit @Test methods do not need to be javadoc'd. However, you should still comment any helper test methods and any non-obvious JUnit code.

JUnit

You should provide JUnit 4 tests for your sorting and shuffling methods, and for all other methods you might write (except for methods whose only purpose is to print results). Running the JUnit tests should not produce any printed output.

For both sorting and shuffling, you should test that the resultant array has the same numbers in it as the original array (for example, [3,1,4,1,6] should not be sorted as [1,3,4,6,6]). An easy way to do this is to add the numbers in the array and see whether the sum is unchanged by sorting; this is obviously not perfect, but we'll call it good enough, because a perfect test is a lot more complicated to write.

For sorting, test whether the numbers are in nondecreasing order, which is not the same as ascending order, because an array may have duplicate numbers in it. Make sure your test cases have some duplicate numbers.

A good test of a shuffle method is much trickier, because the numbers could end up sorted by chance (the odds are 1 in N!). And it's extremely hard to test the quality of the shuffle. So settle for the following: (1) Use a large enough array (say, 100) that it's highly unlikely to end up in sorted order by chance, and (2) count the number of times that an element is larger than the preceding element (should happen about half the time), and test that that number is reasonable.

Writeup

Write up your results on a file named readme.txt. This should include:

The relative speeds of each of the nine sorting situations, and your conclusions about which sorting methods are fastest under which circumstances.
Your results from testing the two shuffle methods (include copies of the 10x10 tables), and your conclusions about which method, if either, is better.

Due date:

Zip the complete NetBeans project, including your readme.txt file, and submit via Blackboard before midnight Wednesday, January 30.