I. Introduction

Because of your recent success discerning between Shakespeare and Bacon texts, you have been commissioned once again for your detective prowess. If all goes well with this assignment, there is a good chance you will be offered your dream role in the new television detective drama, Cold Hard Cache. The lead character is a robotic chimpanzee named Banana Cache, and you will be playing Banana's sidekick as the two of you solve one zany computer mystery after another. Before the director gives you an audition, however, she wants to ensure that you have sufficient data structures and algorithms skills (so that there's plenty of "chemistry" between you and Banana), so she tests you with the following bit of sorting sleuthing...

II. Learning Objectives

For this assignment, you will:

• Hone your understanding of a range of sorting algorithms.
• Gain proficiency in analyzing the run times of these algorithms.
• Investigate the empirical performance of different sorting algorithms on different types of input.
• You will not do any coding in this assignment!

III. Sorting Analysis

In this assignment, you will be investigating a Java program which runs 7 different sorting algorithms: BubbleSort, HeapSort, InsertionSort, MergeSort, QuickSort, RandomizedQuickSort, and SelectionSort. The program has 7 different buttons, one for each of the sorting algorithms, but the problem is that nobody knows which button runs which sorting algorithm. It is your job to determine which button runs which sorting algorithm (and impress Banana Cache in the process)!

First, the program allows you to create a list of numbers which need to be sorted. You can select how many numbers you want in your list to be sorted. Also, you can select whether you want the list of numbers to be in random order to start with, or else in sorted order, or in reverse sorted order, or in nearly sorted order.

When you sort the list of numbers, the program indicates how many comparisons the sorting algorithm required, how many movements the sorting algorithm required, and how much time the algorithm took. The number of movements is the number of times an element in the list is a part of an assignment statement. For instance, list[0] = temp; and temp = list[0]; and list[0] = list[1]; each count as one movement. You can assume that when 2 elements in the list are swapped, it counts as 3 movements.

IV. Program Availability

You can download the files here or you can get them from the course directory /projects/cse/courses/cse326/02su/assignment3/. This is a tar archive, so named because of the program used to create it (Tape ARchive). This is a common way to distribute groups of files in Unix. Unpack the archive with
    tar xvf sortingSleuth.tar
If you like, see man tar for details on what you just did. Now to run the program, make sure the current directory contains the file SortDetective.class and type
    java SortDetective

V. What to Turn In

• Devise a plan which will enable you to match each of the 7 buttons to one of the 7 sorting algorithms: BubbleSort, HeapSort, InsertionSort, MergeSort, QuickSort, RandomizedQuickSort, and SelectionSort.
• Execute your plan, taking careful notes as you go.
• Describe the results of your experiment in a summary report. Begin with a summary of the matching, and then show the rationalization process that justifies it. Your justification for your answers should be thorough and convincing, but not necessarily long! A sample from a similar (but much simpler) assignment on searching can be seen here.

  A note on the write-up: There is no coding in this assignment. Thus, you should expect that a significant portion of the grade will be determined by the quality of the writing of the report. This includes the completeness of the report, the clarity 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.
  Finally, remember that your report needn't detail every experiment you ran. Rather, it should give sufficient information to justify your conclusions. It is possible to write a very short report that is completely correct if your experiments are well-chosen. After you learn the matching, you might consider whether there was a shorter way to arrive at your conclusion!
  
  

• Your summary report should be turned in at the beginning of class on Wednesday, August 7^th.

VI. Credits

The original inspiration for this assignment comes from David Levine, of the Computer Science department at St. Bonaventure University. The idea for this assignment comes from the "Nifty Assignments " session at the annual ACM SIGCSE meeting.