テクノロジ系出題頻度 3/3
挿入ソート
そうにゅうそーと
定義
未整列要素を整列済み部分の適切な位置に挿入していくソート法。最良O(n)。
詳細解説
トランプの手札を整える要領で、左から順に各要素を整列済み部分の適切な位置に挿入する。平均・最悪O(n²)、最良O(n)（ほぼ整列済みの入力で高速）。安定ソートでその場実行可能。小規模データや、ほぼ整列済みのデータで高速。クイックソートやマージソートでは、再帰の末端で挿入ソートに切り替える「ハイブリッドソート」が実装される（Timsort、introsort等）。シェルソートは挿入ソートの拡張版で間隔を縮めながら整列する。
「挿入ソート」が出る問題
関連用語
よくある質問
Q. 挿入ソートとは何ですか？
A. 未整列要素を整列済み部分の適切な位置に挿入していくソート法。最良O(n)。
Q. 応用情報技術者試験での位置づけは？
A. テクノロジ系の重要用語です。出題頻度は 3/3 （★3）。 頻出のため確実に押さえておきましょう。