How I visualized the sorting algorithms and brought them to life with sound

0 7

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.

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!

https://medium.com/media/f59d4f6c6ff09b201d45fd71bd7b60d8/href

I also wanted it to be very accessible. Putting it on the web was the most obvious choice, but that comes with a caveat. 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 problem with this approach though. It is not that it’s convoluted even though it is fairly tedious to write the algorithms this way. It is that it directly ties iteration to the main loop, so doing more than one step per interval 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.

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 I think there is a better way.

Cooperative Algorithms

Using coroutines, the algorithms can be partially evaluated on demand. It just so happens that 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 it is asynchronous and, since it is generated on demand, algorithms like “Bogo Sort” would work.

var array = new Array(100);
var algorithm = bubbleSort(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 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 also recommend checking out Introduction to Algorithms if you are looking for a book to on the subject to sit down with.


How I visualized the sorting algorithms and brought them to life with sound was originally published in freeCodeCamp on Medium, where people are continuing the conversation by highlighting and responding to this story.

First Appear on: freecodecamp.org


- Advertisement -

Leave A Reply

Your email address will not be published.

x

We use cookies to give you the best online experience. By agreeing you accept the use of cookies in accordance with our cookie policy.

I accept I decline