挿入ソート

概要

　挿入ソート(Insertion sort) は、バブルソートと並び、アルゴリズムが単純で実装が容易なため、しばしば用いられます。
　処理時間はかかりますが、バブルソートよりも高速、殆ど整列済みのデータに対しては高速という特徴を持ち、安定な内部ソートを実現します。

アルゴリズム

　以下の配列 array に対する昇順ソートを行うとします。

題意より、常に [i] の値は [i + 1] の値以下となり、最小値は arrray[0] 、最大値はarray[9] に置かれます。

まず、[0]と[1]を比較し、順番が逆であれば位置を交換します。太字は交換または挿入箇所を示し、斜体は整列済みの範囲であることを示します。

次に、整列した[0]～[1]に対して、[2]を正しい順に並ぶ位置に挿入します。挿入する際、右側のデータは右方向に一つずつ移動します。

次に、整列した[0]～[2]に対して、同様の処理を行います。このあと、[3]以降の要素について、整列済みデータとの比較と適切な位置への挿入を繰り返します。

利点

　挿入位置が決まれば、それ以降比較を行う必要がないため、比較回数はバブルソートよりも少なくなり、結果「バブルソートよりも高速」となります。
　ほとんど整列された配列に対しては、比較を行う必要がないため、「殆ど整列済みのデータに対しては高速」となります。

　この利点を応用として、配列を細分することを考えます。このとき細分された配列のそれぞれは、細分前と比較して「殆ど整列された状態」にあります。また、整列が完了した配列を結合すると、結合された配列は「殆ど整列された状態」とみなすことができます。この考え方に基づいた、シェルソート、マージソートはより高速なソートを実現できます。

　改良例として、二分挿入ソートがあります。挿入箇所の前は整列済みであるという性質を利用して、挿入箇所を二分探索する手法です。

プログラムソース

　要素数 n の倍精度実数配列 array に対するソースを示します。ここで、配列の要素数は、配列の定義等によって既知であるとします。
　数値配列に対する汎用性を考慮しており、このまま使用する場合は、引数にあたる配列のデータ型をキャストしてください。

void inssort(double array, int n)
{
    int    i, j;    /*配列要素に対するカウンタ*/
    double temp;    /*退避用の変数*/

    for (i = 1; i < n; i++)
    {
        temp = array[i];    /*これから挿入を行う値を退避する*/

        /*array[i]より左側の整列済み配列に対して、右側から temp との比較を行う*/
        for (j = i - 1; j >= 0 && array[j] > temp; j--)
            array[j + 1] = array[j];    /*挿入する値が、比較した配列要素より小さければ、その配列要素は右に1つずらす*/

        /*挿入する値が比較した配列要素以上ならば、ループを抜けて、その要素の右側に退避した値を代入する（挿入）*/
        array[j + 1] = temp;
    }
}

関連項目

• ソートのアルゴリズム

更新履歴

2008/07/25: 作成

Back / Studying / Top