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:

Why I like the SortDetective

If One Must...

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


Contact Info

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

David Levine
Department of Computer Science
St. Bonaventure University
St. Bonaventure, NY 14778