再帰クイックソートの可視化
2007-02-06


再帰的なクイックソートの可視化です。継続渡しとは関係ありませんが、元記事のものと比べると描画がかなり軽快になっていると思います。

なお、Shibuya.js Technical Talk #2 で「ActionScript でクロージャ、継続渡し」を発表なさったとおる。さんが、「まるごとJavaScript & Ajax! Vol.1」で「FlashのActionScriptで関数型風プログラミング」という記事を書いています。継続渡しについてもいろいろと解説してくださるようで、読むのを楽しみにしています。と自分の宣伝もかねて :-)

おまけで非破壊的なクイックソートとその継続渡しスタイル版。「maoeのブログ - 末尾再帰のクイックソート」で見た Haskell のクイックソートを基にしたものです。短いけど何かごちゃっとしてしまいました。

function quickSortND(data) {
  if (!data.length) return [];
  var pivot = data[0], lt = [], gte = [];
  for (var i = 1; i < data.length; i++)
    ((data[i] < pivot) ? lt : gte).push(data[i]);
  return quickSortND(lt).concat([pivot], quickSortND(gte));
}

function quickSortND_CPS(data, cont) {
  if (!data.length) return cont([]);
  var pivot = data[0], lt = [], gte = [];
  for (var i = 1; i < data.length; i++)
    ((data[i] < pivot) ? lt : gte).push(data[i]);
  return quickSortND_CPS(lt, function (sortedLt) {
    return quickSortND_CPS(gte, function (sortedGte) {
      return cont(sortedLt.concat([pivot], sortedGte));
    });
  });
}

quickSortND_CPS(array, print);
// 0,1,2,3,4,5,6,7,8,9

元記事にトラックバックを送ろうとしたら 403 Throttled エラーなるものではじかれました。この場合、時間をおいてもう一度送りなおせばいいのかな? 時間をおいたらうまくいった。


戻る
[JavaScript]

コメント(全0件)
コメントをする


記事を書く
powered by ASAHIネット