挿入ソート [Insertion Sort]

挿入ソートはリストの整列済みの部分に対して新たな要素を適切な位置に挿入することで整列を行うアルゴリズムです。

整列済みのリストの後ろにいくつかの要素を追加して再び整列させるという場合や、一方の整列済みリストに整列されていない他方のリストを追加しながら整列させたい時に威力を発揮します。

アルゴリズム分析

配列を昇順に整列させる場合のアルゴリズムを示します。

1. 整列済みのインデックス'A'を決定する
2. 'A'の次の要素'B'を整列されていない部分とする
3. 'B'を'A'に挿入する
   • 'A'と'B'の値を比較して'B'の値が小さければ'A'と交換する
4. 'A'と'B'が整列された部分になる
5. 'B'の次の要素'C'を整列されていない部分とする
6. 整列済みの部分'A','B'に'C'を挿入する
   • 'C'と'B'の値を比較して'C'の値が小さければ'B'と交換する
   • 'C'と'A'の値を比較して'C'の値が小さければ'A'と交換する

挿入ソートは常に隣り合う要素で比較、交換を行います。交換が発生した場合には比較元となる整列されていなかった要素はリストの先頭へ移動(挿入)されます。

特徴

挿入ソートは整列されている部分が多ければ多いほど計算量が減り、処理速度は向上します。
反対に、「昇順に整列されたものを降順に並び替える」というように、逆順のリストを対象とした場合にもっとも遅くなります。

サンプルコード

C言語

void insertionSort() が配列を昇順に並び替える挿入ソートの実装です。ソート開始時の整列済みの部分は「配列の先頭のみ」という条件になっています。

また、swap() という値を交換するための関数を作って insertionSort() の見通しを良くしています。

void insertionSort(int numbers[], int array_size)
{
    int i, j;

    for (i=1; i < array_size; i++) { //整列されていない部分の先頭を指す

        j = i; //交換要素のためのインデックス

        //条件(昇順)に一致しない場合は整列済みであるのでスキップして良い
        while ((j > 0) && (numbers[j-1] > numbers[j])) {
            swap(&numbers[j-1], &numbers[j]);
            j--;  //インデックスの更新。隣り合う要素との比較なので-1で良い。
        }
    }
}

void swap(int *p_from, int *p_to) {
    int tmp;
    tmp = *p_from;
    *p_from = *p_to;
    *p_to = tmp;
}