挿入ソート

挿入ソート（そうにゅうソート、英: insertion sort）あるいは基本挿入法は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。

挿入ソート

クラス	ソート
データ構造	配列
最悪計算時間	$O(n^{2})$
最良計算時間	$O(n)$
平均計算時間	$O(n^{2})$
最悪空間計算量	$O(n)$ total, $O(1)$ auxiliary

時間計算量は平均・最悪ケースでともに Ο(n²) であり、クイックソートやマージソートなどと比べれば遅い。しかし、

• アルゴリズムが単純で実装が容易
• 小さな配列に対しては高速
• 安定
• in-placeアルゴリズム
• オンラインアルゴリズム

などの特徴から利用されることがある。

挿入ソートを高速化したソート法として、シェルソートが知られている。

アルゴリズム

まず0番目と1番目の要素を比較し、順番が逆であれば入れ換える。次に、2番目の要素が1番目までの要素より小さい場合、正しい順に並ぶように「挿入」する（配列の場合、前の要素を後ろに一つずつずらす）。この操作で、2番目までのデータが整列済みとなる（ただし、さらにデータが挿入される可能性があるので確定ではない）。このあと、3番目以降の要素について、整列済みデータとの比較と適切な位置への挿入を繰り返す。

動作例

整列された部分（確定とは限らない）をアンダーライン、挿入する部分を太字で表す。

8	4	3	7	6	5	2	1	（初期データ）
4	8	3	7	6	5	2	1	（1回目のループ終了時）
3	4	8	7	6	5	2	1	（2回目のループ終了時）
3	4	7	8	6	5	2	1	（3回目のループ終了時）
3	4	6	7	8	5	2	1	（4回目のループ終了時）
3	4	5	6	7	8	2	1	（5回目のループ終了時）
2	3	4	5	6	7	8	1	（6回目のループ終了時）
1	2	3	4	5	6	7	8	（7回目のループ終了時。ソート完了）

実装

C言語

void 
insertion_sort(int data[], size_t n) {
    for (size_t i = 1; i < n; i++) {
        if (data[i - 1] > data[i]) {
            size_t j = i;
            int tmp = data[i];
            do {
                data[j] = data[j - 1];
                j--;
            } while (j > 0 && data[j - 1] > tmp);
            data[j] = tmp;
        }
    }
}

Scheme

(define (insertion-sort ls)
  (define (insert x ls)
    (let loop ((ls ls) (acc '()))
      (if (null? ls)
          (append acc (cons x ls))
          (let ((y (car ls)))
            (if (< x y)
                (append (reverse acc) (cons x ls))
                (loop (cdr ls) (cons y acc)))))))
  (let loop ((ls ls) (acc '()))
    (if (null? ls)
        acc
        (let ((x (car ls)))
          (loop (cdr ls) (insert x acc))))))

計算時間

バブルソートと比較すると、「交換回数」は等しくなる。しかし、「比較回数」は、バブルソートでは必ずn(n-1) / 2回必要だったが、挿入ソートはこれ以下で済むため、挿入ソートの方が高速である。また、ほとんど整列済みのデータに対しては高速という特徴を持っている。

なお交換回数に関しても、前記実装例のように一連の交換の途中の特定処理を省略することができるので交換一回が高速になる。また、特にデータが連結リストで格納されている場合には、バブルソートと比較して大幅な高速化が図れる。これは配列における「挿入」が一連の交換（の途中の特定処理を省略した処理）によって実現されるのに対し、連結リストでは文字通りの「挿入」が可能であるので、交換回数が大幅に減少するからである。

二分挿入ソート

挿入ソートの改良で、挿入するデータの前ではソートが済んでいるという性質を利用して、挿入する箇所を二分探索するというものである。データの量が少ないときにはあまり効果がないが、多いときには比較回数が少なくなる。探索アルゴリズムによっては不安定なソートになるが、工夫により安定させることが可能である。