挿入ソートとは？そうにゅうそーと
挿入ソートとは、整列済みの部分列に対して、未整列の要素を正しい位置へ挿入していく整列方法。トランプの手札を並べる操作に似る。最悪はO(n²)（データが2倍になると手間がおよそ4倍に伸びる）だが、ほぼ整列済みのデータでは挿入位置の探索がすぐ終わり、O(n)（データ量に比例する伸び方）に近づく。この「入力の並びによって速くなる」性質が基本情報の頻出ポイント。
最終更新：2026-10-09
基本情報を最短で暗記・合格する →具体例
[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) 代表的なアルゴリズムに掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。