A Visualization of Sorting Algorithms


Sorting...

0 Accesses
0 Writes
0% Complete
 
Playback Speed
Input Specs
Instructions
Select your algorithm from the dropdown and hit play!
Visualization
The visualization represents an array with the white vertical bars representing integer elements of the array. The height of the bars are indicative of their value. During then visualization, the green flashes indicate an access (a value was read) and a red flash indicates an array write.
Playback Speed
At 1x playback speed, you'll see all the operations in real time. At 2x the speed, 2 operations will be bunched up and rendered together. At Nx, the visualization will update for every N operations.
Additional Options
Presorted Input ensures that all the elements in the array will be sorted in ascending order before the sort commences.
Equal Input ensures that all the elements in the array have the same value.

What’s happening under the hood

What follows is a quick explanation of how the above visualization is created. There are basically three steps:

  1. Modify the Array class - this will let us record any reads and writes that happen.
  2. Prepare and then apply a sort algorithm on an array and record the operations (read/write) that took place.
  3. Replay those operations on to a canvas.

Modifying the Array class

Since JS doesn’t allow overriding of the indexer ( à la C# ), I thought it best to tack on additional methods to the array prototype. This is what the Array#get looks like

Array.prototype.get = function (index) {
  var event = new CustomEvent('array.read', { detail: { index: indexOffset + index, value: this[index] } });
  document.dispatchEvent(event);
  return this[index];
};

Externally it’ll work like a simple getter method, but every time it is called, it’ll raise a CustomEvent with details about which value was accessed and at what index. An Array#set was created along the same lines. And since most algorithms swap elements around, I created an Array#swap as well.

Array.prototype.set = function (index, value) {
  var event = new CustomEvent('array.write', { detail: { index: indexOffset + index, value: value } });
  document.dispatchEvent(event);
  this[index] = value;
  return value;
};

Array.prototype.swap = function (index1, index2) {
  var temp = this.get(index2);
  this.set(index2, this.get(index1));
  this.set(index1, temp);
}

Preparing and Sorting the Array

Preparing the array is easy: just fill it up with values ranging from 0 to Array#length and then shuffle them around. This is the snippet is use to shuffle the array:

Array.prototype.shuffle = function () {
  var array = this, currentIndex = array.length,
    temporaryValue, randomIndex;
  while (0 !== currentIndex) {
    randomIndex = Math.floor(Math.random() * currentIndex);
    currentIndex -= 1;
    temporaryValue = array[currentIndex];
    array[currentIndex] = array[randomIndex];
    array[randomIndex] = temporaryValue;
  }
};

Pick any sorting algorithm you like and then modify it to use Array#get and Array#set to read and write values respectively. This is what Insertion Sort looks like

(function(lib){
  "use strict";
  var sort = function (arr) {
    for (var i = 0, len = arr.length; i < len; i++) {
      var j = i, item = arr.get(j);
      for(; j > 0 && arr.get(j - 1) > item; j--) {
        arr.set(j, arr.get(j - 1));
      }
      arr.set(j, item);
    }
    return arr;
  };
  lib.insertionSort = sort;
})(algorithms);

Now while the array is getting sorted, we will be building up a list of operations by listening to the array.read and the array.write operations. ex.

document.addEventListener('array.write', function (event) {
  var detail = event.detail,
    operation = new Operation(Operation.Types.WRITE, detail.value, detail.index);

  return this.playbackController.recordOperation(operation);
});

Playing Operations on a Canvas

The basic render loop is simple. By now we have an array which contains all the operations that have taken place on the array. Start Array#shifting the operations. For each operation, render an array read or an array write based on its type. The core function that renders the frames is

klass4.prototype.renderNextFrames = function () {
  var operation, type,
    delegate, framesPlayed = [],
    sound = this.options.sound,
    numAccess = 0, numWrites = 0,
    operations = this.operations,
    setPercentage = this.options.setPercentage,
    incrementWrites = this.options.incrementWrites,
    incrementAccesses = this.options.incrementAccesses,
    OPS_PER_SECOND = i = this.options.OPS_PER_SECOND;

  while (i--) {
    operation = operations.shift();
    if (!operation) return;
    type = operation.type;
    switch (type) {
      case Operation.Types.READ:
        this.graphicsController.plotValueBeingAccessed(operation.value, operation.index);
        numAccess += 1;
        break;
      case Operation.Types.WRITE:
        this.graphicsController.plotValueBeingWritten(operation.value, operation.index);
        numWrites += 1;
        break;
      break;
    }
    framesPlayed.push(operation);
  }

  setPercentage(Number((this.totalOperations - this.operations.length) * 100 / this.totalOperations).toFixed(3));
  incrementWrites(numWrites);
  incrementAccesses(numAccess);
  sound ? beep(300 * operation.value/this.options.canvasHeight) : undefined;

  return framesPlayed;
};

And the render loop is simply:

klass4.prototype.playNextFrame = function (callback) {
  var operations = this.operations;
  if (this.paused) return;
  if (operations.length > 0) {
    this.resetFrames(this.framesDrawn);
    this.framesDrawn = this.renderNextFrames();
    requestAnimationFrame(function () {
      this.playNextFrame(callback);
    }.bind(this));
  } else callback();
};

Contributions

Feel free to send in suggestions/improvements/bug reports. Sorting algorithms will also be appreciated. :)

Inspired by 15 Sorting Algorithms in 6 Minutes.