ニコニコ大百科モバイル

7/2(月)よりスマホまたはPCでアクセスした場合、各デバイス向けのサイトへ自動で転送致します


クイックソート


ヨミ: クイックソート

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

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


原理


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

性能検討


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

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

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

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


関連項目



最終更新日: 16/09/25 02:06
タグ検索 パソコン版を見る


[0]TOP
ニコニコ動画モバイル
運営元:ドワンゴ