Sorting Algorithms as Dances
Written by Mike James   
Friday, 23 December 2011

The surprise viral success of I Programmer's year has to be 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 first time around, you can see them again in this compilation.

You may well have seen many simulations of sorting algorithms that aim to show in novel ways how the 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 - 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.

 

sortdance

 

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".

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 their success, they produced two more 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

 

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, subscribe to the RSS feed, follow us on Google+, Twitter, Linkedin or Facebook or sign up for our weekly newsletter.

 

Banner


Google Cayley Graph Database
02/07/2014

Google has released an open source graph database written in Go, making it available on GitHub.



DotPeek 1.2
22/07/2014

JetBrains has released the next version of dotPeek, its free .NET decompiler and assembly browser.


More News

 

Last Updated ( Friday, 23 December 2011 )
 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.