A while back I saw a post about visualizing sorting algorithms. But what do they sound like? I put together a quick Chuck script that does a bubble sort of a list of integers. Each time it compares two values it first converts the values from a MIDI note value to a frequency and then plays two tones with those frequencies.

// what does a bubble sort sound like?

10 => int noteCount;
if (me.args() == 1)
  me.arg(0) => Std.atoi => noteCount;

SqrOsc osc1 => ADSR adsr => Gain g => dac;
SqrOsc osc2 => adsr;

0.5 => g.gain;

// create the unsorted array of MIDI notes

int notes[noteCount];

for (int i; i < noteCount; i++) {
  Std.rand2(40, 90) => notes[i];
 }

fun void bubbleSort(int l[])
{
  for (int i; i < l.cap(); i++) {
    for (int j; j < l.cap() - i - 1; j++) {
      l[j] => Std.mtof => osc1.freq;
      l[j + 1] => Std.mtof => osc2.freq;

      adsr.keyOn();
      0.2::second => now;
      adsr.keyOff();
      if (l[j] > l[j + 1]) {
	l[j + 1] => int temp;
	l[j] => l[j + 1];
	temp => l[j];
      }
    }
  }
}

bubbleSort(notes);

The sound is kind of fun, and because of the way bubble sort works, you end up with some structures that repeat. You might almost call it musical.

Going a little further with the idea of playing the output of a sort, I began to wonder if I could maybe be lazy and just use sorting algorithms that have already been implemented. Most sorting algorithms work by comparing two elements and rearranging them depending on which one is larger. If you are comparing numbers, the criteria for “larger” is fairly well understood. But if you are trying to sort by, oh, let’s say an employee id, and the id is some collection of numbers and letters, and those numbers and letters may mean something special to the way they are sorted, then you want to be able to specify what “larger” actually means. The qsort() function in the C standard library takes a comparison function as an argument. This function knows how to compare two elements in the list that is passed as one of the other arguments to qsort(). That way qsort() doesn’t have to know anything about the elements it is sorting. In Java, there is an interface called Comparable. Objects that implement this interface must provide a method called compareTo() that knows how to compare itself to another object. Each time a sorting function needs to compare one item to another, it uses this compareTo() method.

Can we hijack compareTo()? You bet. Here’s a simple class that implements compareTo():

class Buzz implements Comparable {
    int val;
    public int compareTo(Buzz b) {
	return b.val - this.val;
    }
}

What if, in addition to returning the difference between the two values we also sent the values out of the program to another program that would do something with them? Well, thanks to an OSC library called JavaOSC we can do this fairly easily.

I put together a Groovy program that creates a list of objects that implement Comparable and then sorts the list. Their compareTo() method sends OSC messages to the local host (127.0.0.1) on port 6767. These OSC messages specify which numbers are being compared.

import com.illposed.osc.OSCPortOut;
import com.illposed.osc.OSCMessage;
import java.net.InetAddress;
import java.util.Random;

class Buzz implements Comparable {
    int val;
    OSCPortOut sender;
    public int compareTo(Buzz b) {
	Object[] args = [new Integer(b.val), new Integer(this.val)];
	OSCMessage msg = new OSCMessage("/comparing", args);
	this.sender.send(msg);
	sleep(200);
	return b.val - this.val;
    }
}

OSCPortOut sender = new OSCPortOut(InetAddress.getByName("127.0.0.1"), 6767);

list = [];
rand = new Random();
20.times {
    list << new Buzz(val: 40 + rand.nextInt(51), sender: sender);
}
list.sort();

And here's a Chuck program that listens for the messages and plays the notes

OscRecv recv;
6767 => recv.port;
recv.listen();

recv.event( "/comparing,ii" ) @=> OscEvent oe;

SqrOsc osc1 => ADSR adsr => Gain g => dac;
SqrOsc osc2 => adsr;

0.5 => g.gain;
0.1::second => adsr.attackTime;
0.1::second => adsr.decayTime;
0 => adsr.sustainLevel;

adsr.keyOff();

while ( oe => now ) {
  while ( oe.nextMsg() != 0 ) { 
    adsr.keyOn();
    oe.getInt() => int m1;
    oe.getInt() => int m2;
    <<<"comparing", m1, m2>>>;
    m1 => Std.mtof => osc1.freq;
    m2 => Std.mtof => osc2.freq;
  }
 }

I think the default list sorting algorithm in Java is a quicksort (edit: actually it looks like it is a mergesort, and it may be replaced in the future by timsort), but you can probably find others. And if you can't find anything, you can always write your own. Once you have a sorting algorithm that accepts a collection of Comparable objects, you can use the code I've provided to listen to it.

Update:

Ryan Compton did something similar at UCLA, and he also has graphs to show you what's going on.