【くいっくそーと】
クイックソート とは？
公開:
💡 「まず基準を決めて、大きい・小さいに分ける」を繰り返すだけで整列完了！
📌 このページのポイント
- ピボット（基準値）を選び、それより小さい要素と大きい要素に分割する「分割統治法」
- 平均計算量O(n log n)で、多くの言語の標準ソートに採用されるほど実用的に高速
- 最悪計算量はO(n²)だが、ピボットの選び方を工夫すれば回避できる
- 不安定ソート（同じ値の要素の順序が保証されない）という特徴がある
ひよこ クイックソートって名前からして速そうだけど、どういう仕組みなの？
ペンギン先生 まず「ピボット」っていう基準値を1つ選んで、それより小さいグループと大きいグループに分けるんだ。で、それぞれのグループの中でもまた同じことを繰り返す。これが「分割統治法」だよ
ひよこ たとえばトランプのカードを並べるときみたいな感じ？
ペンギン先生 そうそう！まず「7」を基準にして、7より小さいカードを左、大きいカードを右に分ける。次に左のグループで「3」を基準にして…って繰り返していくと全部並ぶよね。それがクイックソートだよ
ひよこ 最悪の場合はO(n²)になるって聞いたけど、大丈夫なの？
ペンギン先生 たとえばすでにソート済みのデータで毎回端っこをピボットに選ぶと、分割が偏って最悪ケースになるんだ。でも「ランダムにピボットを選ぶ」「3つの中央値を使う」といった工夫で実質的に回避できるよ
ひよこ 不安定ソートってどういうこと？困る場面はある？
ペンギン先生 同じ値の要素、たとえば「点数が同じ2人の生徒」の並び順が入れ替わる可能性があるってこと。名前順で並べてから点数でソートしたいときに、名前順が崩れちゃうことがあるんだ
ひよこ じゃあ実際のプログラミング言語ではどう使われてるの？
まとめ：ざっくりこれだけ覚えればOK！
「クイックソート」って出てきたら「基準値で分けて再帰的に並べる高速ソート」と思えればだいたいOK！
📖 おまけ：英語の意味
「Quicksort」 ＝ 高速ソート
💬 1960年にイギリスの計算機科学者トニー・ホーアが考案したアルゴリズムだよ。名前のとおり「クイック（高速）」なのが最大の特徴だね