出典：公益社団法人 日本技術士会「技術士第一次試験 過去問題」
データ数nの配列をソートするアルゴリズムで、時間計算量がO(n log n)となる場合を選ぶ問題。クイックソート、挿入ソート、マージソート、バブルソート、選択ソートの最悪・平均計算時間を整理する。
代表的なソートアルゴリズムの時間計算量を比較する問題。
① ソートの計算量: マージソート=最悪でも O(n log n)、クイックソート=平均 O(n log n)・最悪 O(n²)、挿入・バブル・選択=O(n²)
② 「最悪でも O(n log n)」を満たすのはマージソートだけ
③ ③
マージソートは、配列を2分割して再帰的にソートし、併合する。分割の深さがlog n、各段階の併合がO(n)なので、最悪の場合でもO(n log n)である。したがって③が最も適切である。
O(n log n)で安定なのはマージソート(最悪でも)。クイックソートは平均O(n log n)、最悪O(n^2)。単純な挿入・バブル・選択ソートは、いずれもO(n^2)。
キーワード: ソート、計算量、マージソート、クイックソート、挿入ソート、バブルソート、選択ソート、情報工学部門
同じ問題が計2回出題されています(令和3年度、令和6年度)。