整列アルゴリズムの特徴
整列アルゴリズムに関する記述として，適切なものはどれか。ここで，n は整列対象のデータ数とする。
- アクイックソートは，データの並びにかかわらず，最悪の場合でも計算量が O(n log n) である。
- イヒープソートは，同じキー値をもつデータの相対的な順序が整列後も必ず保たれる安定な整列法である。
- ウマージソートは，最悪の場合でも計算量が O(n log n) であり，安定な整列を実現できる。
- エ挿入ソートは，データがあらかじめ昇順に整列済みのときに，比較回数が最大となる。
正解と解説を見る
正解 ウ
この問題の基礎知識
- O 記法の計算量は，データ数 n が増えたときの処理時間の増え方を表し，同じ整列法でも平均の場合と最悪の場合とで異なることがある。
- 安定な整列とは，同じキー値をもつデータの整列前の相対的な順序が，整列後も保たれることをいう。
- 最悪計算量は，マージソートとヒープソートが O(n log n)，クイックソート，挿入ソート，バブルソート，選択ソートが O(n^2) である。
- マージソート，挿入ソート，バブルソートは安定な整列法であり，クイックソートとヒープソートは一般に不安定な整列法である。
アクイックソートは，データの並びにかかわらず，最悪の場合でも計算量が O(n log n) である。
クイックソートの平均計算量は O(n log n) だが，基準値（ピボット）の選び方によって分割が偏ると，最悪の場合は O(n^2) となる。
イヒープソートは，同じキー値をもつデータの相対的な順序が整列後も必ず保たれる安定な整列法である。
ヒープソートは，ヒープの構築や根の交換によって離れた位置の要素を入れ替えるため，同じキー値の相対順序が保たれない不安定な整列法である。
ウマージソートは，最悪の場合でも計算量が O(n log n) であり，安定な整列を実現できる。正解
マージソートはデータを半分ずつに分割して併合を繰り返すので，データの並びによらず O(n log n) で整列できる。併合時に等しいキーは前半側を先に取り出せば安定な整列となる。
エ挿入ソートは，データがあらかじめ昇順に整列済みのときに，比較回数が最大となる。
昇順に整列済みのデータを昇順に整列する場合，挿入ソートは各要素で 1 回の比較だけで済み，O(n) となる最良の場合である。比較回数が最大となるのは逆順に並んでいる場合である。
検証用の出典一部照合
IPA 応用情報技術者試験（レベル 3）シラバス ／ NIST Dictionary of Algorithms and Data Structures照合の根拠（3 件）
- ウ（正解）: マージソートの実行時間は Θ(n log n)（データの並びによらず n log n）
A sort algorithm that splits the items to be sorted into two groups, recursively sorts each group, and merges them into a final, sorted sequence. Run time is Θ (n log n).
NIST Dictionary of Algorithms and Data Structures · merge sort (Definition)（新しいタブで開きます） - ウ（正解）: 併合（merge）は安定に行える操作である
Many different operations, such as sort, merge, and select the minimum using a priority queue, can be stable.
NIST Dictionary of Algorithms and Data Structures · stable (Note)（新しいタブで開きます） - ア（誤り）: クイックソートは最悪時に Θ(n²)
Quicksort has running time Θ(n²) in the worst case, but it is typically O(n log n).
NIST Dictionary of Algorithms and Data Structures · quicksort (Note)（新しいタブで開きます）
NIST DADS でクイックソート最悪 Θ(n²)，マージソート Θ(n log n)，併合が安定にできることは確認できた。ヒープソートが不安定であること（イ）と，挿入ソートが整列済みデータで最良（比較回数最小）となること（エ）を明記した読める一次資料が見つからない。