The SortDetective

This assignment requires students to recognize various sorting algorithms by their "signatures", i.e. their behavior on particular types of data sets.  It requires that students understand some set of sorting algorithms and that they develop an intuitive understanding of asymptotic running time.  It is unusual in that the students write no code.

Sorting Assignments in History

Once upon a time, studying sorting meant writing code to implement a sort.  Nowadays, this is bad not only because of the proliferation of code in textbooks and on the net, but also because it does not represent what we wish to teach.  Most damningly, it is boring.

More typically, an assignment on sorting now requires students to run various (pre-written?) sorts on particular sets of data and to draw particular conclusions from the results.  Labs such as these are sometimes praised as exemplifying the scientific method, but they are often subject to the criticism that they are very cookbookish.  They tend to require students to spend a lot of time waiting for results - time that their mind is not engaged.  (Some students sometimes cite this as a positive factor on course evaluations, but you may choose to disagree.)

The SortDetective turns this assignment on its head.  Students are presented with a complete suite containing various sorting algorithms, data input capabilities, and measurements that can be made.  Unfortunately, all of the algorithms are "anonymous".  Rather than being told what sorts to run, the students must design their own experiments so as to match the behaviors with the algorithms.  As a result, it would be very odd for any two independent groups to do the same thing!  The students must make the same measurements as in the more traditional lab, but then they must actively associate those measurements with a theory rather than seeing "if they fit".  They must exhibit more judgment about what constitutes "good enough".  Finally, they must write up their conclusions in a relatively "free" format.

The requirements are that the students know:

• Characteristics of asymptotic run-time behavior
• The general asymptotic behavior of the sorting algorithms being "detected"
• Some details of implementation (to break ties) for the sorting algorithms
• How to write an argumentative essay

Why I like the SortDetective

• The lack of structure forces the student to be an active learner.
• Some sorts are hard to distinguish (e.g. insertionSort vs. bubbleSort), so groups end up discussing the behavior.
• Computer science is not programming, but many of our lab exercises give this impression.  This one does not.
• It is easy to change the assignment from semester to semester by changing the mapping of the sorts and/or by reimplementing one of the algorithms to make it match the textbook's version. 
• It is easy to add or remove sorts from the suite - although radixSort is a bit problematic due to the comparison counting - allowing one to tailor the difficulty.
•  NO CODING!  This means that we can run this lab while students are working on larger projects without requiring them to work on two batches of code simultaneously.
• One can show the two classes (i.e. their source code) as an example of design in later courses.

If One Must...

It is still possible to use this for the "historical" sorting labs. 

• Sorts can be removed from the suite for the express purpose of having students add them back in.
• Traditional measurements can be made if one only puts the "proper" labels on the buttons.

Resources

• Lab write-up
• Technical info (how to change stuff)
• SortDetective.java and SortingExperiment.java (you need both)
• JavaPowerTools archive (I/O package)

Contact Info

    Feedback is always welcome.   Please report bugs, improvements, etc. to