クイックソートとは
基準値を選んで小さいグループと大きいグループに分け、それぞれを再帰的に整列する高速な整列法。
解説
クイックソートは、基準値（ピボット）を1つ選び、それより小さい要素と大きい要素に振り分けたうえで、それぞれの部分を同じ手順で整列していく「分割統治法」の一種です。平均計算量は O(n log n) で実用上高速ですが、基準値の選び方が悪く毎回極端に偏った分割になると最悪 O(n²) になります。これに対しヒープソートとマージソートは最悪でも O(n log n) です。
試験での出方
各整列法の平均・最悪計算量の比較や、「分割統治法」の説明として問われます。バブル・選択・挿入ソートは O(n²) と合わせて整理します。
あわせて読みたい用語
この用語が解説に出てくる問題
- 平成30年度 秋期 問6クイックソートの処理方法を説明したものはどれか。
- 平成27年度 秋期 問7整列アルゴリズムの一つであるクイックソートの記述として，適切なものはどれか。
- 平成27年度 春期 問6整列されたn個のデータの中から，求める要素を2分探索法で探索する。この処理の計算量のオーダを表す式はどれか。
- 平成23年度 特別 問8整列アルゴリズムの一つであるクイックソートの記述として，適切なものはどれか。
- 平成21年度 秋期 問6クイックソートの処理方法を説明したものはどれか。
この用語がよく出る分野：アルゴリズムの要点と過去問一覧