平成28年度 III-5

解説

この問題で問われていること

代表的なソートアルゴリズムの、最良・平均・最悪の時間計算量を比較する問題。

解き方

① 計算量: マージソート=最悪でもO(n log n)、クイックソート=平均O(n log n)・最悪O(n²)、挿入ソート=最良O(n)、選択ソート=常にO(n²)
② 「最悪でもO(n log n)」はマージソート
③ ②

正解が正しい理由

マージソートは、配列を2分割して再帰的にソートし、併合する。分割の深さがlog n、各段階の併合がO(n)なので、最悪の場合でもO(n log n)である。したがって②が最も適切である。

各選択肢について

• ① クイックソートは、平均ではO(n log n)だが、最悪(基準値が常に最大・最小になる場合など)はO(n^2)となる。
• ② マージソートは、最悪でもO(n log n)で、これが正答。
• ③ 単純挿入ソートの最良計算時間(すでに整列済みの場合)は、O(n)である。
• ④ シェルソートの平均計算時間は、間隔の取り方によるが、一般にO(n^1.25)程度など、O(n log n)ではない。
• ⑤ 選択ソートは、最悪でも平均でもO(n^2)である。

覚えるべきポイント

O(n log n)で安定なのはマージソート(最悪でも)。クイックソートは平均O(n log n)、最悪O(n^2)。単純な挿入(最悪)・バブル・選択ソートは、O(n^2)。