For this lab, you will work individually and submit your own solution. As usual, though, run update35 to get the initial files for this lab.

This lab consists of three parts:

1. Complete a templated implementation of quickSort and its helper function, partition.
2. Augment the Person class with comparison operators.
3. Play Agent Michael Scarn in the thrilling drama of "Sort Detective"

You should complete the implementation of two templated functions in quicksort.inl:

• void quickSort(T a[], int left, int right): Uses quick sort to sort a range (inclusive) within an array.
• int partition(T a[], int left, int right): Partitions a range in an array around a randomly-chosen pivot element. It first swaps a random element to the rightmost position in the range, and then partitions the range as described in lecture. This function must return the final position of the pivot element in the partitioned array.

To complete this work you do not need to edit any files except for quicksort.inl, and you only need to modify quicksort.inl in the locations marked with TODO. Once you are done, you can test your work using the provided testQuickSort program, which uses quick sort to lexicographically sort an array of Points by their x- and y-coordinates.

For your reference, the algorithms described in lecture were:

    quickSort(a, left, right):
        if (left < right):
            p = partition(a, left, right)
            quicksort(a, left, p-1)
            quicksort(a, p+1, right)


    partition(a, left, right):
        l = left
        r = right-1
        pivot = a[right]

        while (l <= r):
            if (a[l] <= pivot):
                l++
            else if (a[r] > pivot):
                r--
            else:
                swap(a, l, r)

        swap(a, l, right)
        return l

In C++, each class may implement its own comparison operators <   <=   >   >=   != and == to define how items of that class are compared. This is convenient because it allows generic algorithms, such as our templated quick sort algorithm, to compare items of arbitrary classes using the built-in comparison symbols.

As an example, we've augmented our earlier Point class (from week 2!) with (somewhat simpler than normal) comparison operators. Our implementation compares two Points by first comparing their x-coordinates (returning that a point p1 is less than a point p2 if p1.x < p2.x) and then breaking ties by comparing their y-coordinates. We've also demonstrated a second possible comparison function which compares two points by comparing their distance from the origin (0,0). See point.h and point.cpp for our implementation, and testPoint and testQuickSort for testing purposes.

Your task is to augment the Person class with comparison operators, comparing two Persons using whatever criteria you want. Once you have added the necessary operators to the person.h header file and person.cpp implementation file, you should be able to sort an array of people using the testPerson program. Be sure to indicate your criteria in the header comments of your function so it's obvious to a user of your class how you rank Person objects.

This portion of the lab is based on David Levine's Sort Detective lab developed at St. Bonaventure University

In the crime-ridden streets of Swarthmore, PA, agent Michael Scarn receives a knock on his door. In walks Prof. Soni with a stack of papers.

Soni: "There's been a horrible crime. The worst kind a CS professor can ever witness. A student has...submitted an ugly program. No meaningful variable names, no comments. They have goto statements. Look at the graphical interface! All the buttons are labeled as letters in the greek alphabet! It's so obscure, I don't even know who wrote it. *insert sobbing*"

Scarn: "Well, what do you expect. You should never let an undergrad program in Java."

Soni: "Enough chit chat. They are all sorting algorithms, but they are unlabeled. Find me the correct mapping of sort algorithm to label, and I'll give you a handsome reward of A on this lab."

Scarn: "Professors are so cheap..."
End Scene

For this lab, you will play agent Michael Scarn and 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 five sorting algorithms:

• bubble sort
• insertion sort
• merge sort
• quick sort
• selection sort

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. We have seen two of these algorithms in detail this week. The others were most likely seen in CS 21, but you can familiarize yourself with them by referring to the course textbook or looking at their wikipedia entries.

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

Instructions

1. In your cs35/labs/06/ directory there is a folder sorddetective. Within there, you will run a script:

   $ cd
   $ cd cs35/labs/06/sortdetective
   $ ./runDetective.sh
   

   This will load up execute the user inteface for sorting data. Execute it 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. You can use this interface to generate data of a range of sizes (using the slider) and with certain properies (e.g., random, in order, etc.).

2. Devise a plan which will enable you to match the particular algorithms to the button names. E.g., insertion sort to Alpha. Hint: It may make sense to try to divide the sorts into initial groups based on run-time performance (O(n^2) vs O(n log n)) and then to work on each group separately. Divide and conquer: a strategy for life and algorithms, too!

3. Execute your strategy. Be sure to keep notes to help you with your writeup.For example, "I was able to identify button Alpha because it's run time was..."

4. Produce a writeup describing your results and experimental methodology. You should employ general scientific writing skills to produce this paper. Your paper should include a description of your strategy with justifications. It should also include a summary table showing your mapping from button name to algorithm so it is easy for me to identify your conclusions. Your results section should justify your choices (i.e., what features of your experiments helped you identify the pairing).

A note on writing

Part of scientific writing is the ability to precise with your language. You should not submit a 20 page thesis. It should be feasible to describe your results in 1-2 pages.

There is no coding for this part of the 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. Getting a perfect match does not ensure a high grade.

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!

Run handin35 to submit your program. Be sure to complete all three parts of your program. Either place a PDF of your written solution to Sort Detective in your handin directory, or place a hard copy in my CS 35 mail slot outside my door.

Home Page