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

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

例として「1，3，5，7」という昇順に整列された数列(n=4)に対して要素2を追加する場合を考えてみます。問題文の指示に従って比較は数列の末尾から行っていきます。

1. 2と7を比較する。2のほうが小さいので数列の前の要素の比較に移る。
2. 2と5を比較する。2のほうが小さいので数列の前の要素の比較に移る。
3. 2と3を比較する。2のほうが小さいので数列の前の要素の比較に移る。
4. 2と1を比較する。2のほうが大きいので要素2の挿入位置は1と3の間に決定する。

このように比較回数は最小で1回、最大でn回となることがわかります。オーダー記法では定数を除外した処理件数(n)による計算量の増加率や計算量の上限値を示すため、比較回数のオーダーはO(n)になります。