Musical Sorting Algorithms


Suppose you drop a set of drums and they land randomly ordered in a row on the floor. You want to put the drums back in order but can only pick up and swap two at a time. A good strategy to minimize the number of swaps you must make is to follow the Quicksort algorithim http://en.wikipedia.org/wiki/Quicksort .
If you order the drums by their general MIDI number and simultaneously strike any two which you swap then you will produce a sound similar to this:

To hear what's going on with quick sort a little better consider the case where you have dropped 12 guitar strings whose frequencies vary expoentially, ie
frequency of string i = 220.0*( 2.0^(i/12.0) )
for i=0,...,11 for more information http://en.wikipedia.org/wiki/Pitch_(music)

I could not hear what's going on all that well either.An aesthetically pleasing quadratic running time strategy you may follow is insertion sort http://en.wikipedia.org/wiki/Insertion_sort. Here's how insertion sort sounds in a scenario involving many more strings on the floor:

And if you were to sort drums with insertion sort you would get something like this:

The sounds were made using STK http://ccrma.stanford.edu/software/stk/ the videos were made using the python gnuplot module http://gnuplot-py.sourceforge.net/" and mencoder. The source is provided below.

quick_drum.tar.gz

quick_guitar.tar.gz

insertion_drum.tar.gz

insertion_guitar.tar.gz


This got written up: http://blog.makezine.com/archive/2009/08/musical_sorting_algorithms.html