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