Three-way quicksortをJavaScriptで書いた。

　普通Quick Sortっていうと、ピボットが1つなんだけど、ピボット2つで区間を3分割して考えるのが3-way quicksortです。
分割された区間は、ある値よりも小さいか、同じか、大きいか、で分けられているだけで、それ以外は普通のquicksortです。

　例によってJavascriptで書きました。本当に誰得。

　さらに例によってデモを作った。
整列の様子を視覚的に分かりやすくたデモを作りたかったのですが、タイムアップで単純にソート前とソート後しか表示されません。
これじゃあ中でバブルソートやっていてもわからない。何のためのデモか。

　これだけではうまみがあまり無いのですが、ソートの対象が数字ではなく文字列や配列である場合、3-wayをうまく使ったmultikey quicksortという手法を使うと高速な整列が可能になります。そのあたりはまあ、そのうち。

　追記

　Multikey-Quicksortは割合ベーシックな話なのでオワコンだと思っていたのですが、昨年、IBIS 2010で東大の鹿島先生のところの学生さんと話した際、だいぶ違う問題に転用していて、認識を改めたのを思い出した。