Call me a nerd, but this is awesome

A team from Sapientia University, a Hungarian university located in Transylvania, Romania, has released some totally amazing videos on YouTube, in which a row of dancers demonstrate different sorting algorithms.

• Bubblesort
• Insertion sort
• Mergesort
• Quicksort
• Selection sort
• Shell sort

I’m in a bit of a rush right now, but I’ll put up descriptions of, and code for, the algorithms as soon as I find time. (Yes, I know Wikipedia already has excellent information on all these sorting algorithms—and others! But points for effort, no?) For what it’s worth, I sorted this list of algorithms into alphabetical order using manual bubblesort.

This actually reminds me of Neal Stephenson’s Anathem, where monks solve problems in differential geometry by using dances to represent raising and lowering indices, tensor contraction, and the like. (Yes, I am a nerd.)

Updated:
Here’s a little bit on quicksort and insertion sort, the first two that come to mind. I’ve written up the code in Haskell because (a) Haskell is great to code in if you’re lazy, and (b) Haskell code looks like pseudocode anyway. Granted, that means the code might not always be optimized for killer speed, but it is guaranteed to be functional (pun intended!) and will convey the basic insight of the algorithm. Most of the pseudocode for these algorithms available online is usually written with some sort of heavily imperative language like C in mind. That’s fine, because imperative languages give us much better performance and are far more common in the real world. However, such languages also usually force us to get our hands really dirty with all sorts of messy details. Functional languages like Haskell, on the other hand, make us really think about the purpose underlying the algorithm. (I have seen some people call Haskell descriptive, as opposed to the prescriptive way that imperative languages work.) In other words, functional languages force us to get away from implementation-level details and to think about the actual algorithm itself. This is ultimately why I decided to try to write this code in Haskell.


Quicksort
This is perhaps the easiest to code up (and is almost a poster-child for Haskell awesomeness). Quicksort is a recursive algorithm which works thus:

1. pick some element of the list to be your pivot.
2. put all the other elements of the list into two sublists: those less than (or equal to) the pivot, and those greater than the pivot.
3. quicksort these two sublists as well.

Unbelievably simple, but guaranteed to work. And in Haskell:

quicksort :: (Ord a) => [a] -> [a]
quicksort []     = []
quicksort (x:xs) = quicksort smallerList  ++ [x] ++ quicksort biggerList
                   where smallerList = filter (<= x) xs
                         biggerList  = filter (>  x) xs

This is surprisingly easy to read. 

1. The first line is just a “type signature” that tells us what sort of input quicksort expects and what sort of output it produces. Here, it expects a list containing elements that can be “ Ord”ered, i.e., for which there is a meaningful sense of greater-than or less-than or equal-to, and it produces a similar list.
2. The second line says that quicksort performed on an empty list returns the empty list. This is common sense: if there is nothing to sort, there is nothing to return.
3. The third line (written over three lines) is where the meat of the action is located. It picks as its pivot the first element of the list, then builds two sublists, smallerList and biggerList, and then quicksorts them. The two sublists are constructed by filtering all the other elements depending on their ordering relation with the pivot.

Insertion sort
Here too the key idea is pretty simple, but it’s not exactly recursive. Instead, we “build up” or “accumulate” a sorted list as we go through. How? We

1. pick the first element of the unsorted list
2. insert it into the correct position of the accumulated sorted list

This is also remarkably easy to code up in Haskell, using the standard-issue foldl function. The function foldl captures the general idea of traversing through a list, carrying out some procedure to every element of the list and storing the result of that in some “accumulating” value. In this particular case, the accumulated value we want at each step is the sublist of sorted elements, while the procedure we wish to carry out is the insertion of each element into the correct position in the accumulated list.


(Note: If I were actually coding this for a real-world task, I’d use foldl' instead of foldl, but that’s not relevant to the purpose of explaining the key behavior of the algorithm.)

insertsort :: (Ord a) => [a] -> [a]
insertsort = foldl insertInto [] 
             where insertInto [] x = [x]
                   insertInto xs x = smallerList ++ [x] ++ biggerList
                                     where smallerList = filter (<= x) xs
                                           biggerList  = filter (>  x) xs

What’s going on here? For starters, the first line is almost identical to the one for quicksort, which makes sense, since both functions are just supposed to do the same thing to a given list. The second line (which is broken up over five lines for clarity) says that insertsort is just foldl invoked with the procedure insertInto to be carried out on every element and with the initial accumulated value (i.e., the initially sorted list) being the empty list. 

The procedure insertInto turns out to be a very simple one: if you’re given an empty list and an element, you just insert the element into the list; if you’re given a proper list (presumably sorted) and an element, well, just filter out the elements smaller and bigger than the given element into two sublists, and join them appropriately.

For those who may be interested, some really good information on the family of fold functions is available on the Haskell wiki.


More on the other sorting algorithms once I figure out how to code them in Haskell!