挿入ソート アルゴリズム

ウィキペディア

挿入ソート

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/10/25 00:33 UTC 版)

アルゴリズム

まず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回必要だったが、挿入ソートはこれ以下で済むため、挿入ソートの方が高速である。また、ほとんど整列済みのデータに対しては高速という特徴を持っている。

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