クイックソート VS 挿入ソート、ファイッ!

コードとライブデモはこちら。

アルゴリズムの王道ソートアルゴリズムでコードバトリングをしてみたかったので作った。左(赤)のコードが昇順に、右(青)のコードが降順に同一の配列をソートしようとして戦う。昇順に揃ったら左の勝ち、降順に揃ったら右の勝ち。

コードは普通のJavaScriptとして書く。以下の2つの特殊な関数がある。

  • get(i): 配列からi番目の要素を取得する
  • swap(i, j): 配列のi番目とj番目の要素を交換する

setはできない。setを許すとコード内のメモリに配列を逃しておいてソート、一気に書き込むというインチキができるから。右の降順側のgetは要素のマイナスの値が帰ってくるので、右のコードもアルゴリズム自体は昇順にするものを書けば良い。

コードは左と右で交互に実行する。実行はJS-Interpreterのstep()で行う。

コードはなるべく実行速度が速く、頻繁にswapして配列をかきまわせる方が強い。速度はJS-Interpreterのstep()の解釈粒度に依存するが、コードがコンパクトな方がもちろん速い。

クイックソートと挿入ソートだと挿入ソートの方が圧倒的にコンパクトで、配列の長さが10くらいだとその実行速度でクイックソートを圧倒して勝つことが多い。配列が長くなると多分勝敗は変わってくるんだろうけど、試していない。

ソートアルゴリズムは別のアルゴリズムが配列をいじるなんてことは想定していないので、実行が終わった時点でちゃんとソートされている保証は無い。なので実行が終わったあとは実行状態をリセットして再度実行される。クイックソートは実装によっては外部から配列をいじられると配列のバウンダリを超えた操作が発生してエラーになることもある。その場合も再実行。

で、これがちゃんとしたゲームとして成り立つかというと、どうだろう。このアルゴリズムがこのアルゴリズムに強い、みたいな三すくみ的な面白さがあるかというと、微妙だ。あとは相手方向に揃いそうだったら積極的に崩す、とかいう防御的仕組みを入れたバトリング向け特殊ソートアルゴリズムが強かったりするなら面白そうなんだけど、そういった工夫をする余地があるかなあ。