クイックソート単語

クイックソート

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

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

原理

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

性能検討

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

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

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

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

関連項目

【スポンサーリンク】

スマホ版URL:
https://dic.nicovideo.jp/t/a/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88

この記事の掲示板に最近描かれたお絵カキコ

お絵カキコがありません

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

クイックソート

まだ掲示板に書き込みがありません…以下のようなことを書き込んでもらえると嬉しいでーす!

  • 記事を編集した人の応援(応援されると喜びます)
  • 記事に追加して欲しい動画・商品・記述についての情報提供(具体的だと嬉しいです)
  • クイックソートについての雑談(ダラダラとゆるい感じで)

書き込みを行うには、niconicoのアカウントが必要です!


急上昇ワード