Visualizing Sorting Algorithms with Web Audio for the Heck of It

The making of “Tone of Sorting”

Once a week, usually on Sundays I try to set aside time to make something random, usually it is the result of a “what if” shower thought in the form of a game mechanic or web toy.

A few weeks ago I started wondering what sorting algorithms would sound like, and if auralizing an algorithm would aid in visualizing it. I am still not sure if it helps but it sure sounds neat!

Tone of Sorting — Quick Sort with 100 Elements

I also wanted it to be very accessible so putting it on the web was the most obvious choice. That choice however comes with a pretty big caveat that we cannot write sorting algorithms as synchronous code. Even if we were to block and just record the actions taken most browsers would already suggest that the page is not responding and kill it.

Asynchronous Algorithms

So the immediate solution that came to mind was to make them asynchronous. For example, bubble sort could be implemented as something like the following snippet

function test(array, i, j) {
  return array[i] - array[j];
}
function swap(array, i, j) {
  var a = array[i];
  var b = array[j];
  array[i] = b;
  array[j] = a;
}
function bubbleSort(callback, array) {
  setTimeout(function step(i, j, length) {
    if (test(array, j, j + 1) > 0) {
      swap(array, j, j + 1);
    }
    if (j > length) {
      window.setTimeout(step, 0, ++i, 0, n);
    } else if (i < length) {
      window.setTimeout(step, 0, i, ++j, n);  
    } else {
      callback(array);
    }
  }, 0, 0, 0, array.length);
}

There is a big problem with this approach though. It’s not that it’s convoluted even though it is fairly tedious to write the algorithms this way. It’s that it directly ties iteration to the main loop, so it’s fixed in time to the refresh rate and doing more than one step per tick gets even more tedious.

Synchronous Algorithms

A much more manageable solution is to have the algorithms be synchronous. The main thread cannot be blocked. However, we can get around this by moving the sorting algorithms to a worker thread and posting messages back to the main thread.

function test(array, i, j) {
  self.postMessage(['test', i, j]);
  return array[i] - array[j];
}
function swap(array, i, j) {
  self.postMessage(['swap', i, j]);
  var temp = array[i];
  array[i] = array[j];
  array[j] = temp;
}
function bubbleSort(array) {
  var length = array.length;
  for (var i = 0; i < length; i++) {
    var sorted = true;
    for (var j = 0; j < (length - i) - 1; j++) {
      if (test(a, j + 1, j) < 0) {
        sorted = false;
        swap(a, j, j + 1);
      }
    }
    if (sorted) {
      return;
    }
  }
}
self.onmessage = function(event) {
  var fn = eval(event.data[0]);
  fn(event.data[1], event.data[2]);
};

Then by having the main thread queue the messages, they can easily be read in any order or rate desired. Playing tones, animating the document and so on becomes straight forward in a request Animation Frame callback.

var queue = [];
var worker = new Worker('quicksort.js');
worker.postMessage(['quickSort', /* ... */]);
worker.onmessage = function(event) {
  queue.push(event.data);
};
var then = null;
requestAnimationFrame(function tick(now) {
  var delta = now - then;
  if (delta < 1000) {
    return window.requestAnimationFrame(tick, now);
  }
  
  // ...
  
  then = now;
  requestAnimationFrame(tick, now);
}, window);

This is the way Tone of Sorting currently does its computations but there is still a problem with it, with heavy workloads it will still freeze the tab since all the work is essentially done up front on the worker thread.

Additionally, there is a somewhat special algorithm called “Bogo Sort”, otherwise known as Stupid Sort or Monkey Sort, it is unlikely to ever solve. If we need to wait for the worker thread to finish then we cannot visualize it.

Now the worker approach could be improved upon, batching messages together et cetera but there is a better way.

Cooperative Algorithms

Using coroutines, the algorithms can be partially evaluated on demand. It just so happens that “modern JavaScript” does support coroutines, called generators.

Defining the algorithm as a generator means it can yield steps for the renderer to take. For example, bubble sort becomes a generator that looks something like the following

function test(array, i, j) {
  return array[i] - array[j];
}
function swap(array, i, j) {
  var temp = array[i];
  array[i] = array[j];
  array[j] = temp;
}
function* bubbleSort(array) {
  var length = array.length;
  for (var i = 0; i < length; i++) {
    var sorted = true;
    for (var j = 0; j < (length - i) - 1; j++) {
      yield ['test', j + 1, j];
      if (test(a, j + 1, j) > 0) {
        sorted = false;
        swap(a, j, j + 1);
        yield ['swap', j, j + 1];
      }
    }
    if (sorted) {
      return;
    }
  }
}

This is still blocking. However, calling it only a few steps at a time from an asynchronous callback like requestAnimationFrame means we consume it asynchronously and since the work is done on request instead of ahead of time, algorithms like “Bogo Sort” will work just fine.

var array = new Array(100);
var algorithm = bogoSort(array);
requestAnimationFrame(function tick(now) {
  // ...
  var step = algorithm.next();
  // ...
}, window);

Try It For Yourself

You can try out Tone of Sorting here, the animations are really only visible with around 20 elements or so. There is also a GitHub Repository with terrible commits but the source is more or less as-is if you inspect the source in your web browser.

But more importantly, I want to encourage you to try to visualize other types algorithms as it is loads of fun!

I recommend checking out Introduction to Algorithms if you are looking for a book on the subject to sit down with.