One surprise viral success for I Programmer was the amazing "Sorting Algorithms as Dances", a set of videos by Sapientia University that show how to sort things by dancing the various algorithms. If you missed them so far, or are ready for a re-run, here's a compilation of the entire set.

You may well have seen many simulations of sorting algorithms that aim to show in novel ways how an algorithm works, or perhaps doesn't work quite as well as it should. However, I guarantee that you have never seen anything quite in the same league as the videos made by Sapientia University, Romania and uploaded to You Tube by AlgoRythmics.

They are simply crazy but in the nicest possible way.

Take one Central European folk dancing team, a small folk band and an added overlay showing array locations and get them to dance the algorithms in time to "appropriate" folk music.

The result is slightly surreal and, for a time at least, slightly hypnotic.

What you have to do is just check that they are in fact implementing the algorithm correctly.

The dancers have numbers stuck on their front and they do seem to look down and examine the value on another dancer before performing the dance routine dictated by the algorithm

To see what I mean try the simplest of all sorts, the Bubble Sort:

All that happens is that adjacent partners swap if they are in the wrong slot until the algorithm is complete. Notice they have to do a final pass before they can decide that it really is "all sorted".

Recently others have joined in and used the bubble sort dance as a way of getting students to appreciate algorithms.  The actual benefits of learning a bubble sort by dancing are fairly debatable but perhaps it is better than nothing. In case you think that bubble sort isn't worth teaching because it is a bad sorting method you need to realize that it isn't obvious that the micro behaviour of swapping next door neighbors is actually going to result in a sorted array. So in a sense the bubble sort might not be a good algorithm but for some it will be their first exposure to the idea of a not quite obvious algorithm that does achieve its goal.  

If you think that was too simple, try the Shell Sort:

Shell Sort is just a Bubble Sort but with the swaps occurring over greater distances reducing each time.

And for something simpler, the Insert Sort:

Now for the Select Sort:

This was the end of the first batch of algorithms but, spurred on by its success, AlgoRythmics produced two more videos, completing the set of common sorting methods.

The first was a Merge Sort:

In a Merge sort the list is recursively divided into two lists until you reach a list consisting of one element (dancer) and then each list is merged to produce a list twice its size by taking the the elements from pairs of sub-lists in order. So if you have two lists [5] and [3] you take the 3 and then the 5 to give the list [3,5]. If you then have two lists [3,5] and {2,8] you take the 2 from the second list, then the 3 from the first list, then the 5 from the first and the 8 from the second to give [2,3,5,8] and so on.

The merge is much easier to see when you have two big partially sorted lists which is what happens near the end of the dance when the boys merge with the girls - how was that worked out! And more to the point how is it that in the final merge each boy ends up with a girl?

Ah such is the complexity and surrealism that is the sort of the dance.... but you knew that we would have to say something like this.

If you would like to find out the details of merge sort from a programmer's perspective then see: Magic of Merging.

Finally, although we expressed doubt that the only missing standard sort algorithm couldn't possibly be danced, we were proved very wrong.

The slightly insane dance group at Sapientia University put together a Hungarian folk dance with steps that follow the QuickSort algorithm.

It is worth noting that it takes just short of 7 minutes to sort ten dancers, which really isn't very quick; that only males take part, which proves that it is a very dangerous algorithm and, oh yes, two hats are used to mark the progress of the scan!

Clever stuff!

Now see if you are anywhere near as clever by verifying that they are in fact dancing the QuickSort:

If you need help, then all I can suggest is that you keep your eye on the hats, notice exactly what happens when they meet, and pay attention to the partitions that are produced.

If you are slightly vague about how QuickSort is supposed to work then read: QuickSort Exposed

After QuickSort the dancers added a Heap-sort:

And as a bonus we also have three search methods. Linear search isn't so difficult:

Does flamenco work as well as Hungarian folk dance? Try it out again with a look at a binary search:

If you like ballet and chess then you are bound to like the classic eight queens problem danced as an example of backtracking.

I have to admit that this is the best eight queens demonstration, even if it is only four queens, I have ever seen and it deserves to be much better known.

As I say, all delightful, amusing and slightly eccentric. I hope we can look forward to the Fast Fourier Waltz and the Depth First Tree Walk.... 

The original news stories:

Sorting algorithms as dances

Merge sort as folk dance

At last - Quicksort the dance

Further Reading:

Silverlight Sorting Lab

SilverSort

Magic of Merging

QuickSort exposed

Sequential storage

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info