CIT 594 Assignment 2: Sorting
Spring 2008, David Matuszek |

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

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.

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.

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.

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.

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.

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

Zip the complete NetBeans project, including your `readme.txt`

file, and submit
via Blackboard
before midnight Wednesday, January 30.