クイックソート

クイックソートはソートアルゴリズムの一つ。一般的なソートアルゴリズムとしては最速のものとして知られている。安定ソートではない。

平均してO(n log n)だが、運が悪いとO(n^2)。

原理

1. 適当な値を基準に選んでそれより大きいグループと小さいグループに分ける
2. それぞれのグループを再帰で並び替える
3. 小さいグループ、基準値、大きいグループの順で並べる

性能検討

一番効率が良いのは基準値が丁度真ん中になって、両グループでデータが半々になることである。こうなると無駄な比較を極力減らせるので非常に速い。逆に運悪く基準値が一番大きい値だったり小さい値だったりすると、次のグループの大きさが一つしか減らずチンタラした動きになる。まあ普通はずっと端の値ばかり出続けるということは滅多にないので、大抵は速いソートということである。

この理屈で分かるように基準値の出目の良さで速度が決まるので、できるだけ真ん中の値が出るよう乱択したり候補を３つほど選んだりといった工夫をする。

小グループに分けてからは再帰にかぎらず他のアルゴリズムで並び替えても問題ないので、ある程度規模が下がったところで他のアルゴリズムに切り替えるような実装もある。

余談だが、最近は「クイックソートなんて危なくて使えねーよ!」という処理系が結構増えている。理由は言うまでもなくO(n^2)になってしまう爆弾の存在であって、これがDOS攻撃の元になったりするのでセキュリティ的にダメなんだそうだ。ヒープソートと組み合わせたイントロソートならなんとか・・・みたいなところもあって、ソート業界も色々うるさくなっている。

関連項目

• ソート
• アルゴリズム