今注目のニュース
有村藍里“飛び出し坊や”のマネに絶賛
20円で買える幸せ。 チロル「いちごみるく」がレギュラーで仲間入りしたよ!
人からもらったものが食べられない… 警戒心が強すぎる人の特徴

クイックソート単語

クイックソート

掲示板をみる(0)
  • twitter
  • facebook
  • はてな
  • LINE

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

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

原理

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

性能検討

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

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

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

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

関連項目

掲示板

掲示板に書き込みがありません。

急上昇ワード

最終更新:2019/09/24(火) 17:00

ほめられた記事

最終更新:2019/09/24(火) 17:00

☆オススメの関連コンテンツ

動画

この記事名で動画を検索

静画(イラスト)

この記事名で静画を検索

ニュース

この記事名でニュースを検索

ウォッチリストに追加しました!

すでにウォッチリストに
入っています。

OK

追加に失敗しました。

OK

追加にはログインが必要です。

       

ほめた!

すでにほめています。

すでにほめています。

ほめるを取消しました。

OK

ほめるに失敗しました。

OK

ほめるの取消しに失敗しました。

OK

ほめるにはログインが必要です。

TOP