The "Music" of the Quicksort Partitioning Step - an Initial Experiment

I have been experimenting with different ways to appreciate the simple but ubiquitous Quicksort algorithm. My first project dealt with visualizing how the "divide-and-conquer" process works, as described here. The one here delves a little into the partitioning process of the algorithm, in an experiment by which the web audio api is used to sound notes/chords at certain times in the partitioning process. It is a work-in-progress, and apparently sounds different on different browsers. Chrome on the desktop works OK, but Chrome on my Nexus 7 plays the C chord with an odd buzz, as does Safari on the desktop.

It is embedded below from this site on googledrive.

Using the Web Audio API to "Audibilize"
the Quicksort Algorithm Partitioning
Available Here

The Loop being "Audibilized"

The visualization/"audibilization" is basically one way to look at this little (very concise) loop from Algorithms by Sedgewick and Wayne, 4th edition, p.291:

private static int partition(Comparable[] a, int lo, int hi)
{
  int i=lo, j=hi+1;
  Comparable v = a[0];  //the pivot
  while (true)
  {   
    while(a[++i] < v) if (i == hi) break;
    while(v < a[--j]) if (j == lo) break;

    if (i >= j) break;
    swap(a,i,j);  //swap the values in the array
  }
  swap(a,lo,j);   //put v into its final position
  return j;
}

This little loop has been reworked in javascript so that it can be stepped through one step at a time, with visualizations, messages, and notes/chords along the way.

Making Music

The "music" consists of playing notes/chords at certain times in the process via the (somewhat awkward-to-use) web audio api. I also use Music.js by Greg Jopa to facilitate converting Latin note names to frequencies. The basic strategy is as follows:

• When the left scan index i hits a bar/value that is below the pivot, it will move over the bar and play a Bb4 note (this is the Bb below middle C)
• When the left scan index i hits a bar/value at or above the pivot, it will pause, and then play a sustained middle C as long as the right scan index j moves down. Each time the right scan index hits a bar/value above the pivot, it will play an E4 (E above middle C) and keep moving down. When it hits a value at or below the pivot, the the C major chord C-E-G will be played while the values are swapped, and then the left scan index will begin moving up again.
• When the scan indices meet, the C chord C3-C4-E4-G4-C5 is played.

Fancier Music

There are several more effective partitioning algorithms for Quicksort. In Sedgewick and Wayne, they mention the improvement by Bentley and McIlroy in the 90's for better handling the case when there are many duplicate values, and there is an even better one from 2009(!) by Vladimir Yaroslavskiy.

There is a little method in the choice of these notes: it is intended that you can tell what it is doing without looking at the screen.

Is This Useful?

This was a fun way to experiment trivially with the web audio api, and using sound seems like an interesting avenue to explore as a way to augment the learning process. I'm not sure of the efficacy of the current state of this project, however.

To finish this off for now, here's a (full) quicksort put to Hungarian music. I love that they include the array notation, too.

Quicksorting to Hungarian Music