【くいっくそーと】
クイックソート とは？
最終更新:
💡 基準で分け、各部分を繰り返し並べる
ピボットを基準にデータを分割し、各部分へ同じ処理を繰り返して並べるソート手法。平均または期待計算量はO(n log n)だが、基本的な方式では最悪O(n²)になる。
📌 このページのポイント
- ピボットを基準に分割する分割統治法
- 適切なランダム化などの条件で、期待計算量はO(n log n)
- 基本方式の最悪計算量O(n²)は、ピボットの工夫だけで消えるとは限らない
- 一般的な実装は不安定で、同じ値の順序を保証しない
ひよこ どうやって並べるの？
ペンギン先生 ピボットという基準値を選び、その前後に小さい側と大きい側の要素を分けるよ。それぞれの部分へ同じ処理を繰り返し、要素が0個や1個の部分まで小さくすると並ぶ。等しい値の扱いは分割方式によるんだ
ひよこ カードで例を見たい！
ペンギン先生 5、3、8、1、4、7、2を、基準値4で分ける例なら、小さい側は3、1、2、大きい側は5、8、7だよ。この時点では各側はまだ未整列。それぞれに同じ処理を繰り返すと、1、2、3、4、5、7、8になるんだ
ひよこ 最悪O(n²)は避けられるの？
ペンギン先生 整列済みの入力で毎回端の値を選ぶなど、分割が偏り続けると二乗の計算量になるよ。ランダム化は偏る確率を減らすけれど、基本方式の最悪計算量を消す保証ではない。平均・期待値と、最悪の保証は区別しよう
ひよこ 不安定ソートは困るの？
ペンギン先生 一般的なクイックソートでは、同じ値を持つ要素の元の順序が入れ替わる可能性があるよ。名前順の生徒一覧を点数順に並べても、同点の人の名前順を保つとは限らない。その順序も必要なら安定性が保証された方法などを選ぶんだ
ひよこ 標準のsortを呼ぶとクイックソートになる？
まとめ：ざっくりこれだけ覚えればOK！
「クイックソート」って出てきたら「基準値で分け、各部分へ同じ処理を繰り返すソート」と思えばだいたいOK！
📖 おまけ：英語の意味
「Quicksort」 ＝ 高速ソート
💬 1960年にC. A. R. Hoareが考案したソート手法だよ。名前にquickとあっても、全ての入力で最速という意味ではないんだ