応用情報技術者 試験情報＆徹底解説

単純挿入整列法は、挿入ソートとも呼ばれ、整列済みの要素と追加する要素を比較しながら適切な場所に挿入するアルゴリズムです。

例として「1，3，5，7」という昇順に整列された数列を、改めて新しいデータ列に整列することを考えます。問題文の指示に従って比較はデータ列の末尾から行っていきます。

1. 1を新たなデータ列に加える
2. 3と末尾の要素1を比較し、3を1の後ろに加える
3. 5を末尾の要素3と比較し、5を3の後ろに加える
4. 7を末尾の要素5と比較し、7を5の後ろに加える

整列済みのデータの各要素を順番に挿入するため、挿入しようとしている要素は常に新たなデータ列の末尾の要素よりも大きくなります。各要素の挿入位置は1回の比較で確定し、これを要素の数だけ繰り返すため、計算量はデータ量に依拠します。オーダー記法では計算量がデータ量nに比例して増える場合、O(n)で表します。

したがって「ア」が正解です。