挿入ソートとは？
挿入ソートとは、整列済みの部分列に対して、未整列の要素を正しい位置へ挿入していく整列方法。トランプの手札を並べる操作に似る。最悪はO(n²)だが、ほぼ整列済みのデータでは挿入位置の探索がすぐ終わりO(n)に近づく。この「入力依存で速くなる」性質がFEの頻出ポイント。
そうにゅうそーと
挿入ソートの意味
整列済みの部分列に対して、未整列の要素を正しい位置へ挿入していく整列方法。トランプの手札を並べる操作に似る。最悪はO(n²)だが、ほぼ整列済みのデータでは挿入位置の探索がすぐ終わりO(n)に近づく。この「入力依存で速くなる」性質がFEの頻出ポイント。
挿入ソートの具体例
[3,1,4,2]では、まず[3]を整列済みとし、次の1を3の前へ挿入して[1,3]。4はそのまま末尾で[1,3,4]。最後の2を1と3の間へ挿入して[1,2,3,4]。既に[1,2,3,4]と並んでいれば各要素は1回比較するだけで済む。
挿入ソートは試験でどう引っ掛けられる？
「ほぼ整列済みで最速」なのは挿入ソート、「並びによらず一定」なのは選択ソート、という対比で問われる。またクイックソートは逆に整列済みデータで最悪O(n²)に落ちるため、性質が正反対である点を混同しやすい。
挿入ソートと関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。