Using Comics to Demonstrate Quicksort
I hadn’t put away any comics for a month or more. When the backlog gets this big, sorting them can be an issue in and of itself. So I used my big pile of comics to give a quick demo of Quicksort.
(Appologies for practically whispering throughout the video. My wife and kid were already asleep when I started recording.)
Now, I’m not lying when I say that I didn’t understand Quicksort when I graduated college. I’d gone over it several times in class, but it never really made a whole lot of sense to me.
This method, with a literal physical stack you can look at, though, is much easier for helping you understand the basics of the algorithm.
In a real implementation, there’s a way to move the pivot around so that you don’t need such a large stack – you can sort items in-place without allocating additional memory. You just have to push the start & end of the part of the array you’re sorting.
Wikipedia has a great animation describing this process.
There are faster ways to sort comics, of course. Whereas computers can only compare 2 items at a time, people can usually handle 4-6 items at a time. When I’m not playing it out in front of a camera, I usually Quicksort down to about 5 in the working set, then just sort that intuitively.