JavaScript でソートアルゴリズムを可視化

2007年2月 4日

JavaScript でソートアルゴリズムを可視化

JavaScript でソートアルゴリズムを可視化するプログラムを書いてみました。元ネタは Jon Bentley によるソートアルゴリズムを可視化する Java アプレットです。

動作確認は Firefox 2, IE 7, Opera 9 で行いました。要素数は最大で200まで選べますが、かなり重くなるので遅いマシンで実行すると危険です。

解説

X軸が配列の添え字、Y軸が配列の要素の値を示しています。最初に要素がランダムに並んでいる配列 (値に重複なし) を作って、それを各種のソートアルゴリズムでソートする様子をアニメーションで表示します。

ただし、要素のあらゆる変更に対して毎回表示を更新しているわけではなく、基本的に要素数と同じ数だけアニメーションを更新しています (シェルソートとヒープソートはもう少し更新回数を多くしています)。アニメーションの速度とソートの速度は無関係です。

ソースコードには各種のソートアルゴリズムの実装がありますが、アニメーションのロジックを後述の setTimeout で入れているため、ソートアルゴリズムのサンプルコードとしてはあまり参考にならないと思います。ソートアルゴリズムの実装には定本 Cプログラマのためのアルゴリズムとデータ構造を主に参考にしました。

まとめ

JavaScript で各種のソートアルゴリズムを可視化するプログラムを作りました。ばらばらに散らばっていたドットが整然と並んでいく様子はなかなか愉快です。アルゴリズムを理解してからアニメーションを見ると、よりいっそう楽しめると思います。

余談

ところで、上のプログラムのクイックソートは再帰ではなくループで実装されています。これには次のような事情があります。

もともと、JavaScript でアニメーションを表示するのは簡単だろう、と思っていたのですが、いざやってみると、ソートの最中にウィンドウを再描画させるのはそう簡単ではないことが判明しました。調べてみると、 setTimeout を使ってループを作れば再描画できることがわかりました。が、クイックソートといえば再帰だろうと思い、ループに展開する方法は避けようと考えました。

調べてみると JavaScript 1.7 にはジェネレータという機能が追加されていることがわかりました。が、再帰する関数ではあまりシンプルに書けない (関数を再帰的に呼ぶところでループが必要になる) ようでした。結局、クイックソートの関数を自前のスタックとループに展開して、setTimeout でループを結んでお茶を濁す結果となりました。

お蔵入りとなったジェネレータ版のコードは以下のようなものです。

function quickSortInternal(data, offset, length) {
  if (length <= 1) {
    return;
  }
  var middlePos = partition(data, offset, length);
  yield;
  for (v in quickSortInternal(data, offset, middlePos - offset)) {
    yield;
  }
  for (v in quickSortInternal(data, middlePos + 1, offset + length
                              - middlePos - 1)) {
    yield;
  }
}

function quickSort(data) {
  generator = quickSortInternal(data, 0, data.length);
  var loop = function() {
    try {
      generator.next();
      showData(data);
      setTimeout(loop, 10);
    } catch (e if e instanceof StopIteration) {
    }
  }
  showData(data);
  setTimeout(loop, 10);
}

追記

継続渡しスタイルのテクニックを使えば再帰のままでクイックソートを可視化できるそうです。createElement() を最小限にした描画のコードも高速です。勉強になりました。

bkブログ

2007年2月 4日

JavaScript でソートアルゴリズムを可視化

解説

まとめ

余談

追記