挿入ソート【insertion sort】基本挿入法 / インサーションソート / 単純挿入法

概要

挿入ソート（insertion sort）とは、与えられたデータ列を大小などの順序通りになるよう並べ替えるソート(整列)アルゴリズムの最も基本的な手法の一つで、未整列の要素を一つずつ、整列済みの列の適切な位置に挿入していくもの。

数値の列を先頭から小さい順（昇順）に並べる場合を考える。まず、先頭から2つの値を比較して小さい方を先頭に、大きい方を2番目に置く。次に3番目の値を取り出し、先頭・2番目と順に比較し、適切な位置に挿入する。

4番目以降も同様にして、n番目の値を取り出して先頭からn-1番目までと順番に比較し、適切な位置に挿入する操作を繰り返す。これを末尾の値まで繰り返せば、先頭が最も小さく末尾が最も大きい数値の列が得られる。

n番目の値を挿入する際、それが整列済みの列の中で最も小さければ先頭の値との1回の比較で挿入位置が決定できるが、最も大きければ整列済みの値の数（n-1回）だけ比較を繰り返さなければならない。

すなわち、要素が整列済みに近い状態ならば高速に整列を完了でき、最良計算時間はO（n）となるが、逆順に並んでいる場合は比較回数が爆発的に増大し、最悪計算時間は O（n²）となってしまう。この欠点をある程度緩和したアルゴリズムとして「シェルソート」（Shell sort）がある。

整列したいデータ列以外の記憶領域を用意しなくてよいインプレースソート（内部ソート）で、同じ大きさの要素の順序が維持される安定ソートである。アルゴリズムの理解や実装が容易なため、対象データ列が短いことが分かっている場合などに利用されることがある。人間に並べ替えを行わせると、多くの人がまっさきに自然に思いつく方法であるとも言われる。

(2024.3.7更新)