Thanks to David B. Levine of the Computer Science Department at St. Bonaventure University for this nifty assignment.

Objective

The primary objective of this lab is for you to apply your theoretical knowledge of sorting algorithms to solve a problem of poor user interface design. More specifically, you will be given a program which is designed to measure comparisons, data movements, and execution time for the seven sorting algorithms discussed in class. Unfortunately, the designer of the program did not label the buttons properly. You must apply your understanding of the general properties of the algorithms (and in some cases of the code used to implement them) to determine the proper labeling of the buttons.

The secondary objective of this lab is for you to gain experience writing a concise, but complete analysis of a system.

Background

As you know from class, if you double the size of the data set that you give to a quadratic algorithm, it will do four times the work; by contrast, an O(n log n) algorithm will do a bit more than twice as much; and, a linear algorithm will do only twice as much work. As you also know, the characteristics of the input data set can affect the expected performance of many of our sorting algorithms. Before you begin the lab, you should review the expected performance of the algorithms on various data sets.

The sorting algorithms under study this week include (in alphabetical order): bubbleSort, insertionSort, mergeSort, quickSort, selectionSort, and unknownSort.

Note: Quicksort uses median-of-three partitioning. That is, the pivot will be the median of the first, middle, and last elements of the partition each time.

Instructions - Warning: read all of the instructions before beginning!

1. Begin by playing around with the SortDetective applet.   Execute it and play with it a bit.  Notice that the button names do not give any indication which sort they will execute. 

2. Devise a plan which will enable you to match the particular algorithms to the button names.  Hint:  It may make sense to try to divide the sorts into initial groups and then to work on each group separately.  Divide and conquer: it works for algorithms and it can work here, too!




3. Execute your plan, taking careful notes as you go.




A Note on Writing

There is no coding in this lab. Thus, you should expect that a significant portion of the lab grade for this lab will be determined by the quality of the writing of the report. This includes the completeness of the report, the clarity (and grammar) of the writing, and general presentation.

Some of the sorts are very difficult to distinguish. A carefully outlined experiment may compensate for an error in these cases if the writing makes it clear that your conclusions/guesses are substantiated by the data.

What to turn in:

Turn in a written report explaining which sort is which, including supporting data to back up your claims. The following supporting data is required, for each sorting algorithm (except the unknown one):
1. A table and graph of the runtime of each algorithm, with the input in each order, for several (at least four) nontrivial input sizes.
   • Each algorithm should have its own table and graph. Your graphs should show input size on the x-axis and runtime on the y-axis. You can draw the graphs by hand or on the computer.
   • The three input orders (random, in order, reverse order) can be on the same graph or on different graphs if you like.
   • A nontrivial input size means one where the runtime is more than just a few milliseconds.
   • To reduce margin of error, run the algorithm a few times on each input size and choose the median of the three times.
   • You need not use the same input sizes for every algorithm, since this might not produce the most useful data; but if you intend to compare two algorithms directly by how fast they run, you should use the same input size for that comparison.
2. Your estimation of the Big-Oh for each algorithm, based on the data you gathered. You must gather appropriate data that clearly shows the relevant patterns of the algorithm's runtime. This likely means measuring different algorithms at different input sizes, since some algorithms are much faster than others.
3. Your statement of which sorting algorithm it is, along with your reasoning. You should base your reasoning on the following:
   • growth rate (Big-Oh) of the algorithm's runtime as input size changes
   • speed of the algorithm compared to the other algorithms
   • changes in behavior of the algorithm, if any, for different input orderings If all of your claims are based only on relative speeds of the algorithms ("Algorithm 5 was the fastest, so therefore it's X-Sort"), you will not receive full credit.

Grading

Turn in your written report in lecture, at the start of class. This program must be completed individually.