BUILD YOUR UNDERSTANDING
情報処理技術者試験の用語集
言葉の意味を確かめて、問題への理解を一歩深めましょう。
挿入ソート
整列済みの部分へ差し込む
挿入ソートは、既に整列している部分へ、次の要素を適切な位置に挿入することを繰り返す方法です。手札を一枚ずつ受け取り、順番に並べる様子に似ています。先頭から整列済みの範囲を広げていきます。未処理の全体から最小値を探す選択ソートとは、次に扱う要素の選び方が異なります。
Pythonによる例
def insertion_sort(values):
result = list(values)
for index in range(1, len(result)):
current = result[index]
position = index - 1
while position >= 0 and result[position] > current:
result[position + 1] = result[position]
position -= 1
result[position + 1] = current
return result
挿入する値を一時的に保存し、それより大きい値を右へずらして場所を空けています。
手順の理解
2、5、8まで整列済みで、次に3を扱うなら、8と5を右へずらし、2の後ろへ3を入れます。この時点で2、3、5、8が整列済みになります。元の値を保存せずに上書きすると、挿入したかった値を失う可能性があります。代入の順序が重要な例です。
データの状態による違い
逆順に近いデータでは多くの移動が必要になり、最悪時の時間計算量はO(n²)です。一方、既に整列している場合やほぼ整列している場合は、移動が少なく済むため有利なことがあります。小さな部分配列の整列として、他のアルゴリズムと組み合わせられる場合もあります。
比較と移動を分ける
挿入位置を二分探索で探せば比較回数を減らせることがありますが、配列の要素をずらす費用まで消えるわけではありません。比較が高価か、移動が高価かによって効果を考えます。試験では、整列済みの範囲、取り出した値、移動した要素を分けて追います。等しい値を追い越さない実装なら安定性を保てるため、比較条件が大なりか以上かにも注目しましょう。
参考資料
内容確認日:2026-11-13