Sorting Metrics and Sort Identification

Motivation:

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 seven sorting algorithms (five of which have been 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(NlogN) 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 include (in alphabetical order): bubbleSort, heapSort, insertionSort, mergeSort, quickSort, selectionSort, and shellSort. You must research the properties of heapSort and shellSort independently.

Methodology (In class activity):

1. Select a lab partner.
   • A note on group work: When working in a laboratory-based group the problem should be subdivided so that individuals can work independently. There is no benefit to having one member sitting at the computer while the rest of the group tells them what to do. It is much more productive if there is some planning beforehand and the group as a whole knows what they need to do and can then do it independently. Once each task is complete, the group can then get together and join the pieces together. However, you can learn a lot from sitting, talking, arguing and writing programs/reports together in this fashion.
2. Execute it using the command “java -jar SortDetective.jar” and play with it a bit.  Notice that the button names do not give any indication which sort they will execute.  Notice also, that if you create a small list, then that list is shown to you in the console window.  In the unlikely event that a sort fails (oops!), a message will appear there as well.
3. Devise a plan which will enable you to match the particular algorithms to the button names.
4. Execute your plan, taking careful notes as you go.
5. Describe the results of your experiment in a summary document.  Begin with a summary of the matching and then show the rationalization process that justifies it. List and cite any sources you used to investigate heapSort and shellSort.

A Note on Writing

There is no coding in this lab.  Thus, you should expect that a significant portion of the lab grade 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.  It is possible to match all seven sorts correctly and still receive a poor grade due to sloppy writing.

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!

Here is the rubric for the Lab 2 written report.

Source: This assignment is from David B. Levine at St. Bonaventure University as presented during the 2005 ACM Special Interest Group on Computer Science Education Symposium “Nifty Assignments” panel.

All work must be received by the due date (lab report, grade sheet, and individual summary)!

• Handin:
  • A lab #2 grade sheet
  • A printout of your lab report
  • An individual summary (from each group member) addressing the following points; How did you contribute to the lab? Was the group process useful in developing a solution? Was your strategy successful and efficient? Did your partner contribute to the lab