基本情報技術者試験「整列アルゴリズムの特性」の問題
挿入ソートの計算量について最も適切に述べたものはどれか。
ア入力データの並びに依らず常にn log n回の比較を要し一定である
イほぼ整列済みなら最良でO(n)、最悪はO(n^2)になる
ウ最良でも最悪でも比較回数はO(log n)で一定である
エ安定ではないが平均O(n log n)を保証する
正解
イ．ほぼ整列済みなら最良でO(n)、最悪はO(n^2)になる
挿入ソートは各要素を整列済み部分の適切な位置に挿入する。既にほぼ整列済みなら各要素はほとんど移動せず比較もn-1回程度で最良O(n)、逆順では毎回先頭まで戻り最悪O(n^2)になるため正しい。
?選択肢ごとの解説
ア ×常にn log nとなるのはマージソートなど分割統治型の特性であり、挿入ソートは入力の整列度で計算量が変わる。
イ ○挿入ソートは各要素を整列済み部分の適切な位置に挿入する。既にほぼ整列済みなら各要素はほとんど移動せず比較もn-1回程度で最良O(n)、逆順では毎回先頭まで戻り最悪O(n^2)になるため正しい。
ウ ×O(log n)は探索で範囲を半減する量で、全要素を順に挿入する整列処理には当てはまらない。
エ ×挿入ソートは隣接要素の関係を保つ安定ソートであり『安定ではない』は誤り。平均はO(n^2)でn log nを保証しない。
✎くわしく
挿入ソートは安定で実装が簡単。入力依存性が大きく、整列済みデータに強い(最良O(n))。このため小規模データやほぼ整列済みデータの仕上げ、ハイブリッドソートの一部として利用される。
✓本番での押さえどころ
試験のコツ
『ほぼ整列済みに強い=挿入ソート、最良O(n)』を覚える。最良と最悪が異なるソートはバブル・挿入・クイックと押さえる。
覚え方
トランプを手札に挿し込む動作=既に並んでいれば一手で済む、と最良O(n)を直感化する。
よくある誤り
挿入ソートを常にO(n^2)と決めつけ最良O(n)を見落とす、または安定性を取り違える誤りが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0134