データ構造とアルゴリズム
クイックソートの計算量が O(n²) になる典型的な場合はどれか。
- Aデータがばらばらに並んでいて、ピボット(基準値)を無作為に選ぶ場合
- Bデータの個数が2のべき乗の場合
- Cすでに整列済みのデータで、常に先頭の要素をピボットにする場合
答えと解説を見る
正解：C. すでに整列済みのデータで、常に先頭の要素をピボットにする場合
クイックソートは、ピボットより小さい要素と大きい要素に分け、それぞれをさらに分けていきます。整列済みのデータで常に先頭をピボットにすると、毎回ピボットが最小値になり、分割が「0個と残り全部」に偏るため、比較は n(n−1)/2 回(n = 100 なら4,950回)になります。ピボットを無作為に選んだり、3つの値の中央値にしたりすると、偏った分割が続く可能性は非常に小さくなります。データの個数は計算量に関係しません。
- A. 無作為に選べば分割が偏り続ける可能性は非常に小さく、平均 O(n log n) になります。
- B. 個数が2のべき乗かどうかは、分割の偏りとは関係ありません。
- C. 正しい。毎回ピボットが最小値になり、分割が極端に偏ります。