データ構造とアルゴリズム
要素数10の配列を挿入ソートで昇順に並べる。2番目以降の要素を順に取り出し、左隣から順に比べて、取り出した値以下の要素が見つかるか先頭に達するまで比べる。最初から昇順に並んでいる場合と、降順に並んでいる場合の比較の回数の組はどれか。
- Aどちらも45回
- B10回と100回
- C9回と45回
答えと解説を見る
正解：C. 9回と45回
昇順に並んでいれば、取り出した値は左隣と1回比べるだけで位置が決まるので、9個の要素で合計9回です。降順なら、i 番目に取り出す値は左にある i 個すべてと比べるので、1 + 2 + … + 9 = 45回になります。このように挿入ソートは、最良 O(n)、最悪 O(n²) と入力によって大きく変わり、ほぼ整列済みのデータには非常に速いという特徴があります。この性質を活かし、間隔を空けた要素どうしで先に挿入ソートを行うのがシェルソートで、Timsort なども短い区間に挿入ソートを使います。
- A. 比較が常に45回になるのは選択ソートです。挿入ソートは入力の並びで回数が変わります。
- B. 要素数の10や、10² の100はそのまま比較の回数にはなりません。
- C. 正しい。昇順なら各要素1回ずつで9回、降順なら 1 + 2 + … + 9 = 45回です。