挿入ソートとは？そうにゅうそーと
挿入ソートとは、整列済みの部分列に対して、未整列の要素を正しい位置へ挿入していく整列方法。トランプの手札を並べる操作に似る。最悪はO(n²)だが、ほぼ整列済みのデータでは挿入位置の探索がすぐ終わりO(n)に近づく。この「入力依存で速くなる」性質がFEの頻出ポイント。
最終更新：2026-10-07
高度試験の午前Iを最短で暗記する →具体例
[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²)に落ちるため、性質が正反対である点を混同しやすい。
関連用語
出典・参考
公式シラバスの1 基礎理論 ＞ 2. アルゴリズム ＞ (2) 代表的なアルゴリズムに掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。