Lab Sorting Out Sorting Algorithms

Learning Goals

• Get to know how to run timing experiments
• Have a basic understanding on how the following algorithms work: RadixSort, InsertionSort, SelectionSort, MergeSort, QuickSort
• Get a sense on how the Big-Oh notation captures the essence of time complexity

Task 1: Run your experiments

Download the lab13 folder from the download directory. Notice that it contains a javafoundations folder with a Queue implementation. It also contains the Sorting.java file that implements several famous sorting algorithms: RadixSort, InsertionSort, SelectionSort, MergeSort, QuickSort.

We will generate data of various sizes randomly and have each algorithm run on the same unsorted set of data, so that the comparison makes sense. We will use an array to hold and sort the data.

You should be able to compile the Sorting.java file and see how it reports its results. Examine carefully the main() method because you will need to use a more involved version in the next step to run and record your experiments.

Task 2: Create a histogram of your results

In this task you will create a new class the class SortingComparison.java, that will produce a table of values as shown below:

Sorting integers: Time in seconds
#ints   RadixSort   Selection   Insertion   MergeSort   QuickSort
10000
20000
30000
...
90000
100000

1. Run your program looping through a set of experiments, creating random arrays of various sizes ranging from 10K to 100K and then sorting them, recording their running times.
2. Next, open a spreadsheet and enter the values you got from the experiments.
3. With those values create a histogram that shows the performance of the algorithms over arrays of various sizes. What do you observe of the trends of each algorithm?

Task 3: Getting to know the famous Sorting Algorithms

Take a look at some Visualizations of Sorting Algorithms to get a sense on how these algorithms manage to sort their input!

Task 4: Answer these questions

With the members of your team try to answer the following questions as best as you can:

• Which was the fastest algorithm? By how much?
• Which was the slowest algorithm? By how much?
• What is the Big O running time of each of the algorithms you measured?
• Does the difference in Big O notation maches your sense of running speed?
• If you run the algorithms on a new set of random data, will you get the exact running time? If you did not, why?
• Would you ever use the slowest algorithm?

Beware that you cannot really answer all of these questions with just experiments. You will need some deeper understanding on how they work and why. Take CS231 to learn more!

Task 5: Was Obama right?

Obama is known primarily for his opinion regarding BubbleSort. Was he right?

Task 6: How about HeapSort? (optional)

If you still have time, run similar experiments with the HeapSort algorithm that we encountered at a previous lab and see how its running times compare with the ones we run here.