Physical Quicksort.
So I’m grading some exams for the intro CS course. (Really just about a quarter of the exam, but even that took at least a couple of hours.) By the time I get to the end, I’m pretty annoyed that the exams aren’t sorted; I keep thinking, “wait, so-and-so had this same problem—how did I score it there?” Unfortunately, it’s a linear search every time (with some slight hints about how recently I’d graded that test, what color pen I used, etc).
Well, the next TA to look at these exams shouldn’t have to suffer this. “I’ll sort the tests,” I think. Simple, right? People alphabetize things all the time, right? No, I have to make it complicated.
I decide to implement physical quicksort.
[Quick refresher course: Quicksort is a fast sorting algorithm (as the name implies). It’s really fast: on the order of n log n operations (for n items). We can’t generally do better unless we know something about the data (e.g., it’s mostly sorted, or maybe it has a finite numeric representation).]
So, here we go. Starting at 10:45 pm:
Fig. 1. I lay out the tests in the hall in my apartment (sweeping first for a clean surface).
Fig. 2. After the first iteration, the pivot (chosen pretty much at random, last name starting with “F”) is in its final position in the list. Everything to the “left” of the pivot (closer to camera) is still unsorted, but they all come before “F”; everything to the right comes after “F”.
Fig. 3. A few iterations later (working with the sublist to the left of the first pivot), A-F are now in sorted order. (I fell back to insertion sort every time a part of the list got below about 5 items.)
 |
 |
 |
| Fig. 4. A new pivot (“R”) is chosen. | Fig. 5. F-R are sorted. | Fig. 6. The whole list is sorted. |
Total (human) time: 12 minutes. Number of swaps: Enh, I didn’t really keep count. I split/pivoted to a depth of (at most) 4 before hitting insertion sort, which is kinda sorta log n.
I’m already planning ahead for the final exam: In-place heap sort!