The Sounds of Sorting Algorithms

来源:互联网 时间:1970-01-01

Options

Pitch Set:

Pentatonic Pentatonic (Extended) Chromatic Octatonic 12-tone "Open" "Bright" "Dark" "Mysterious" "Shifting"

Performance:

Loading...

Misc.:

What do the sounds mean?

This javascript program runs each sorting algoritm on the given array of pitches (as MIDI values). Each time a pitch is read from the array, the pitch is played softly, and each time a pitch is written to the array, the pitch is played loudly. Swaps and comparisons are played as intervals (with both pitches sounding simultaneously.)

Why did you make this?

I built this for an electronic composition calledSorted Affairs. The entire composition process took many hours spread over several months.

How does it work?

This program was written in Javascript using the jQuery, Raphaël, and MIDI.jslibraries for animation and sound. In order to accomodate the timing necessary for animation and sound, each algoritm had to be altered extensively using 'setTimout' to allow for delays between reads and writes to the array.

Here is an example with one of the simplest algorithms, Bubble sort. This is the original Bubble sort algorithm:

function bubbleSort( array ) { var swapped; do { swapped = false; for ( var i=0; i < array.length-1; i++ ) { if ( compare( array, i, i + 1 ) > 0 ) { swap( array, i, i+1 ); swapped = true; } } } while ( swapped );}

...and this is the function rewritten to allow delays for animation and sound:

function bubbleSortWithSound ( array, callback ) { ( function bubbleSortWhileLoop() { swapped = false; ( function bubbleSortForLoop( i ) { setTimeout( function() { var test = compare( array, i, i + 1 ) > 0; setTimeout( function() { if( test ){ swap( array, i, i+1 ); swapped = true; } if ( ++i < array.length - 1 ) bubbleSortForLoop( i ); else { if ( swapped ) bubbleSortWhileLoop(); else if ( callback ) callback(); } }, test ? delay : 0 ); }, delay ); } )( 0 ); } )();}

This isn't too bad with something like Bubble sort, as there are only two loops and no complex recursion. However, this process can become pretty tedious with a more complicated algorithm. Take Merge sort for example, which I found easiest to implement with a sort of make-shift call stack. This is what the time-delayed Merge sort algoritm ended up looking like:

function mergeSortWithSound ( array, callback ) {var stack = [];function executeFromStack() {if ( stack.length > 0 ) {var func = stack.pop();func[0].apply( null, func[1] );} else {if ( callback ) callback();}}function mergeSortRecursive( left, right ){if ( left < right ) {var middle = Math.floor( ( left + right ) / 2);stack.push( [ merge, [ left, middle, right ] ] );stack.push( [ mergeSortRecursive, [ middle + 1, right ] ] );stack.push( [ mergeSortRecursive, [ left, middle ] ] );}executeFromStack();}function merge( left, middle, right ) {var l = left;var r = middle + 1;( function mergeWhileLoop() {setTimeout( function () {if ( compare( array, l , r) <= 0 ) {l++;if ( l <= middle && r <= right ) mergeWhileLoop();else executeFromStack();} else {setTimeout( function () {var tmp = read( array, r );( function mergeForLoop( j ) {setTimeout( function() {var tmp2 = read( array, j-1 );setTimeout( function() {write( array, j, tmp2 );if ( --j > l ) { mergeForLoop( j );} else {setTimeout( function() {write( array, j, tmp );middle++;r++if ( l <= middle && r <= right )mergeWhileLoop();else executeFromStack();}, delay);}}, delay );}, delay );} )( r );}, delay );}}, delay );} )();}mergeSortRecursive( 0 , array.length - 1 );}

...but enough technical stuff. Just have fun with it! I would personally recommend Quicksort on the "Dark" pitch set, or, if you've got some time, Stooge sort on the "Shifting" pitch set.



相关阅读:
Top