問題
クイックソートに関する記述のうち、適切なものはどれか。
ア）クイックソートの平均計算時間は O(n²) であり、常に安定な整列を行う。
イ）クイックソートは、ピボットの選び方によっては最悪計算時間が O(n²) になることがある。
ウ）クイックソートはマージソートと異なり、追加のメモリ領域を一切必要としない。
エ）クイックソートの最悪計算時間は、常に O(n log n) に抑えられる。
解答・解説を見る
正解： イ）
解説：
- ア）クイックソートの平均計算時間は O(n log n) です。また安定ソートではありません（同じキー値の要素の順序が入れ替わることがある）。誤りです。
- イ）ピボットの選択が偏る（例えば常に最大・最小値を選んでしまう）と、分割が均等にならず最悪計算時間は O(n²) になります。正解です。
- ウ）クイックソートも再帰呼び出しのためのスタック領域を使用します。「一切必要としない」は誤りです。
- エ）上記の通り最悪計算時間は O(n²) になり得るため、常に O(n log n) に抑えられるという記述は誤りです。
重要キーワード
| 用語 | 説明 |
|---|---|
| ピボット | クイックソートで分割の基準に使う要素 |
| 平均計算時間 | O(n log n)。ランダムなデータでの期待性能 |
| 最悪計算時間 | O(n²)。ピボット選択が偏った場合に発生 |
| 安定ソート | 同じキー値の要素の相対順序が保たれる整列 |