ソートアルゴリズムの視覚化って面白いですよね。 見るたびに一度書いてみたいと思っていました。

いきなり視覚化は難しそうですし、まずは書くだけ書いてみよう、ということで。主に他言語での実装を参考にして書いてみました。というか可能なものはロジックそのまま移植しています。再帰は苦手です。

実行できるサンプル

入力欄に数値を入れて実行すると、入力値を最大としてかぶりのない整数をランダムに並べた配列を作成し（10000と入力すれば0〜10000をシャッフルした配列を生成）、ソートを行います。それぞれのアルゴリズムで、実行時間の計測（単位はミリ秒[ms]）と確認のためArray#sortの実行結果との照合を行い、「黒い画面」風に表示します。

あまり大きな数値を入れるとブラウザに怒られます。Chromeとかは結構頑丈みたいですけど（Chromeは1,000,000、Firefoxは100,000で怒られました）。あと、なぜかFirebugのコンソールを開いていると1桁程度遅くなります。

ソースコードは以下 説明はごくごく簡単に

まず、添字を指定して配列の要素を入れ替える関数がぼちぼち出現するのでprototypeに定義しておきます。

if (!Array.prototype.swap) {
  Array.prototype.swap = function(a, b) {
    var tmp = this[a];
    this[a] = this[b];
    this[b] = tmp;
    return this;
  };
}

バブルソート

隣り合った要素を末尾から順に比較して小さい方を前に送っていく、という作業を繰り返します。一巡すると最小値が先頭になるので先頭を除いて再度、末尾から順に比較する作業を繰り返すと小さい方から順に並んでいきます。遅いアルゴリズムで、入力値が大きいとボトルネックになるのでバブルソートのないバージョンのサンプルも用意しました。

function bubbleSort(a) {
  var i = 0, j = 0;
  for (; i < a.length; i++) {
    for (j = a.length - 1; j > i; j--) {
      if (a[j] < a[j - 1]) {
        a.swap(j - 1, j);
      }
    }
  }
  return a;
}

参考：いろいろなソートアルゴリズム - バブルソート

基数ソート

10進数だったら0から9のバケツを用意して、小さい桁から順に注目して同じ数値のバケツに出し入れしていき、最後に0のバケツから順に取り出すときれいに並んでいる、というアルゴリズム。まあ、意味はわかります。

function radixSort10(a, k) { // k 桁の 10 進数
  var b = [], d = 0, i = 0, j, n, r = 1;
  for (; i < 10; i++) {
    b[i] = [];
  }
  for (; d < k; ++d) {
    for (i = 0; i < a.length; i++) {
      b[(a[i] / r) % 10 | 0].push(a[i]);
    }
    for (i = 0, j = 0; j < b.length; j++) {
      if (b[j] === undefined) {
        continue;
      }
      for (n = 0; n < b[j].length; n++) {
        a[i++] = b[j][n];
      }
    }
    for (i = 0; i < b.length; i++) {
      b[i] = [];
    }
    r *= 10;
  }
  return a;
}

参考：++C++;// 未確認飛行 C - 基数ソート

ヒープソート

「ヒープ構造とは、簡単に言うと、2分木の各節点にデータを保持し、親のデータが2つの子のデータよりも小さくなるように作られたデータ構造です」だそうです。ヒープ構造を作ると二分木の根が最大値になるので、それを最後の枝と交換して取り出し再度ヒープ構造を作る、という作業を繰り返します。書き終わった今ではなんとなくわかる気はしますが、なぜ二分木に突っ込もうとか考えつくのか。再帰を使ったものとそうでないものを試してみました。再帰の方が速いですね。

function heapSort(a) {
  var i = 0, len, heap = [],
    insert = function(n) {
      var i, j;
      heap.push(n);
      i = heap.length;
      j = i / 2 | 0;
      while (i > 1 && heap[i - 1] < heap[j - 1]) {
        heap.swap(i - 1, j - 1);
        i = j;
        j = i / 2 | 0;
      }
    },
    shift = function() {
      var i = 1, j = i * 2, r = heap[0];
      heap[0] = heap.pop();
      while (j <= len) {
        if (j + 1 <= len && heap[j - 1] > heap[j]) {
          j++;
        }
        if (heap[i - 1] > heap[j - 1]) {
          heap.swap(i - 1, j - 1);
        }
        i = j;
        j = i * 2;
      }
      return r;
    };
  for (i = 0; i < a.length; i++) {
    insert(a[i]);
  }
  for (i = 0, len = heap.length; i < len; i++) {
    a[i] = shift();
  }
  return a;
}

参考：いろいろなソートアルゴリズム - ヒープソート

ヒープソート（再帰）

function heapSortRecursive(a) {
  var i = a.length / 2 - 1 | 0,
    heapify = function(array, i, size) {
      var l = 2 * i + 1, r = 2 * i + 2, largest = 0;
      if (l < size && array[l] > array[i]) {
        largest = l;
      } else {
        largest = i;
      }
      if (r < size && array[r] > array[largest]) {
        largest = r;
      }
      if (largest !== i) {
        array.swap(i, largest);
        heapify(array, largest, size);
      }
    };
  for (; i >= 0; i--) {
    heapify(a, i, a.length);
  }
  for (i = a.length - 1; i > 0; i--) {
    a.swap(0, i);
    heapify(a, 0, i);
  }
  return a;
}

参考：@blog.justoneplanet.info - JavaScriptでヒープソート

マージソート #1

約半分ずつに再帰的に分解していき、ばらばらになった要素を再構成するときに小さい方から取り出して結合する、というアルゴリズムです。これも、まあ、意味はわかります。

2種類試してみました。一目、#2の方が速そうにみえるのですが、そうでもなく。Firefoxでは配列の数が少ない時は#1、100,000ぐらいになると#2の方が速くなりました。Chromeでは一貫して#1が、IEでは一貫して#2が速いようです。iPhoneで見るとなぜか#2が一番遅いです（バブルソートより遅い）。

function margeSort(a) {
  var split = function(array) {
      //console.log('original: ' + array.toString());
      if (array.length < 2) {
        return array;
      }
      var a, b, mid = array.length / 2 | 0;
      a = split(array.slice(0, mid));
      b = split(array.slice(mid, array.length));
      return marge(array, a, b);
    },
    marge = function(array, a, b) {
      if (b === undefined) {
        return array;
      }
      var c = [], i, j;
      while (a.length > 0 && b.length > 0) {
        i = a[0], j = b[0];
        //console.log('marge: ' + a.toString() + ' <==> ' + b.toString());
        if (i < j) {
          c.push(a.shift())
        } else {
          c.push(b.shift())
        }
      }
      if (a.length === 0) {
        c = c.concat(b);
      } else if (b.length === 0) {
        c = c.concat(a);
      }
      return c;
    }
  return split(a);
}

参考：いろいろなソートアルゴリズム - マージソート、ソートと探索（マージソート）

マージソート #2

function margeSort2(a) {
  var marge = function(a, left, right) {
    if (left >= right) {
      return a;
    }
    var b = [], i, j, k, mid;
    mid = (left + right) / 2 | 0;
    marge(a, left, mid);
    marge(a, mid + 1, right);
    for (i = left; i <= mid; i++) {
      b[i] = a[i];
    }
    for (i = mid + 1, j = right; i <= right; i++, j--) {
      b[i] = a[j];
    }
    i = left, j = right;
    for (k = left; k <= right; k++) {
      a[k] = b[i] <= b[j] ? b[i++] : b[j--];
    }
    return a;
  };
  return marge(a, 0, a.length - 1);
}

参考：tomoemonの日記 - 不安定なマージソート、Ｃ言語講座：初級から中級まで - マージソート

クイックソート

適当に軸要素を決めて、「データの先頭から軸要素以上のデータを検索し、データの末尾から軸要素未満のデータを検索し、見つかった場合、それぞれを交換」「検索ラインが交差するまで続けて、交差した場所でデータを2つに分割」、一体何を食ったらこんなことを思いつくのか。ぶっちぎりで速いです。しかしFirefoxではわずかにビルトインの方が速いようです。

function quickSort(a) {
  var recurse = function(a, i, j) {
      var k, p = pivot(a, i, j);
      if (p !== -1) {
        k = partition(a, i, j, a[p]);
        //console.log('左: (#' + i + ')' + a[i] + ' 軸: (#' + p + ')' + a[p] + ' 右: (#' + j + ')' + a[j]);
        recurse(a, i, k - 1);
        recurse(a, k, j);
      }
      return a;
    },
    pivot = function(a, i, j) {
      var k = i + 1;
      while (k <= j && a[i] === a[k]) {
        k++;
      }
      if (k > j) {
        return -1;
      }
      if (a[i] >= a[k]) {
        return i;
      }
      return k;
    },
    partition = function(a, i, j, p) {
      var l = i, r = j;
      while (l <= r) {
        while (l <= j && a[l] < p) {
          l++;
        }
        while (r >= i && a[r] >= p) {
          r--;
        }
        if (l > r) {
          break;
        }
        //console.log('' + a[l] + ' と ' + a[r] + ' を交換します');
        a.swap(l++, r--);
      }
      //console.log('走査が終了しました: ' + l);
      return l;
    };
  return recurse(a, 0, a.length - 1);
}

参考：いろいろなソートアルゴリズム - クイックソート

サンプルの実行例

Chrome

Firefox

IE10

実行できるサンプル

バブルソートのないバージョンのサンプル