挿入ソートとは

挿入ソートとは、ソート済の部分に新たなデータを適正な位置に挿入していくことで、ソートを行います。

概ねソート済のデータに対しては、交換(挿入)回数が少なく済むため高速に動作します。この特性を活かすように改良されたアルゴリズムがシェルソートです。

ソート対象のデータ数が少ない場合も高速になります。これはクイックソートなどの高速なソートはオーバーヘッドが大きくなるためです。大体50件程度のデータ以下なら、クイックソートより平均して速くなりそうです。

挿入ソートは 安定 な 内部 ソートです。計算量は O(n2) でバブルソートと同じで低速なのですが、前述の通り、一定の条件下では高速に動作する可能性があります。

挿入ソートのシミュレーション

背景色が黄色のタイミングで比較が実行されています。緑色はソート済(確定ではない)の部分です。ここにデータを挿入します。ソート済のデータは水色になります。最終要素まで走査しなければ最小値(最大値)は確定しません。よって上位3件だけ取得する用途でも全データをソートする必要があります。この点は選択ソートなどと違います。

アルゴリズムの解説

  1. データ(array)の先頭要素をソート済のデータとして考えます。
  2. i=1 から n までループし、i番目の要素を挿入することを考えます。
  3. j=i から 0 までループし、i番目の要素の挿入位置(array[i] > array[j] となる j)を決定します。
    ※この際、交換処理を繰り返しながら挿入すると遅くなるので、i番目の要素を一時変数に退避し、配列の値を上書きしてずらすようにします。
  4. 決定した位置に 退避していたi番目の値を入れます。この時点で 0～i番目の値ソート済となっています。
  5. 2.のループが終われば末尾の要素までがソート済のデータとして得られます。

サンプルコード

C#

public static void SelectionSort<T>(T[] array) where T : IComparable<T>
{
    // array[0]をソート済部分として、以降のデータを挿入していく
    for (int i = 1; i < array.Length; i++)
    {
        var tmp = array[i]; // 挿入対象のデータを保持
        // ソート済の末尾の要素より大きければ挿入不要(そのままでよい)
        if (array[i - 1].CompareTo(tmp) > 0)
        {
            // 挿入が必要な場合、その位置(j)を決定する
            int j = i;
            do
            {
                // 挿入するために配列の値をずらしていく
                array[j] = array[j - 1];
                j--;
            } while (j > 0 && array[j - 1].CompareTo(tmp) > 0);
            // 決定した位置に、退避していた値を挿入
            array[j] = tmp;
        }
    }
}

Python

def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        tmp = array[i] # 挿入する値を退避
        if tmp < array[i-1]: # 挿入する必要があるか
            j = i # 挿入する位置
            while True:
                array[j] = array[j-1] # 一つ後ろにずらす
                j -= 1
                if j == 0 or tmp >= array[j-1]:
                    break
            array[j] = tmp # 空いた位置に退避していた値を挿入