挿入ソート | Programming Place Plus　アルゴリズムとデータ構造編【整列アルゴリズム】　第４章

トップページ – アルゴリズムとデータ構造編

この章の概要

この章の概要です。


挿入ソート

この章では、挿入ソート（基本挿入法）を取り上げます。

挿入ソートでは、データ列の先頭付近に整列済みになった部分を形作りながら、全体のソートを行います。まだ整列済みになっていない要素１つに注目し、整列済みになっている部分の適切な位置に挿入することを繰り返します。

たとえば、対象のデータ列が次のような配列だとします。

int array[] = {7, 2, 4, 5, 1, 6};

この配列を昇順にソートします。

挿入ソートでは、先頭から m個までの部分が整列された状態になるように制御します。まず、array[0] を（要素が１つしかありませんが）整列済みなつもりで開始します。

続いて、array[1] に注目します。array[1] には 2 がありますが、これを整列済みのデータ列（現在のところ array[0] だけしかない）の中で適切な位置を探して挿入します。「適切な位置」というのは、挿入後に array[0]～array[1] がきちんと昇順に並ぶような位置ということです。

すると、2 は 7 より小さいですから、array[0] の手前に挿入するのが正しいということになります。配列なので array[0] にあった 7 を後方へずらして割り込ませ、その結果は、次のようになります。

{2, 7, 4, 5, 1, 6};

この時点で、array[0]～array[1] の部分は整列されています。ただし、最終的な位置として確定したという意味ではありません。array[0]～array[1] までの要素を調べ終えた現時点で、この２つの要素に限って、整列済みであるということです。

次は、array[2] に注目します。array[2] は 4 です。今回は、整列済みである {2, 7} のどこに挿入すべきかを判断します。{2, 4, 7} となるのが正しいですから、2 の後ろに挿入します。

{2, 4, 7, 5, 1, 6};

次は、array[3] の 5 です。{2, 4, 7} の中で適切な位置に挿入します。

{2, 4, 5, 7, 1, 6};

次は、array[4] の 1 を {2, 4, 5, 7} の中で適切な位置に挿入します。

{1, 2, 4, 5, 7, 6};

次は、array[5] の 6 を {1, 2, 4, 5, 7} の中で適切な位置に挿入します。

{1, 2, 4, 5, 6, 7};

配列の末尾まで行き着いたので、これで挿入ソートの全工程が終了しました。


ここまでの手順の説明では「整列済みの部分の適切な位置に挿入する」という感じで簡単に表現していますが、実際には、どうにかして適切な位置を探しだす必要があります。

一般的な実装では、整列済みの部分に対して線形探索（【探索】第１章参照）の手法を使って、適切な位置を探します。つまり、整列済みの部分の要素を順番に調べていき、ここに挿入すれば整列済みの状態を保てるという位置を探します。

ここに工夫の余地があります。挿入位置は「整列済み」になっている範囲内にあるのですから、二分探索（【探索】第４章参照）で探すことが可能です。データ件数が多ければ、高速化できる可能性があります。このような実装による挿入ソートは、二分挿入ソートと呼ばれます。この実装は、この章の練習問題で扱っています。

ところで、配列に対する挿入処理は、残念ながら非効率なものになります。これは既存の要素を後方へずらしていく作業が必要になるからです（【データ構造】第１章参照）。

しかし、挿入位置を探した結果、結局、挿入の必要がない場合があります。たとえば、挿入ソートの過程のどこかで、データ列が {0, 2, 3, 5, 9, 7} のようになっていたとします。array[0]～array[3] の部分が整列済みです。

この状態で、array[4] の 9 の挿入位置を探すと、array[4] が適切な位置ということになります。array[4] というのは、現在の位置と変わりませんから、移動（挿入）する必要がありません。

このように、挿入を行わなくて済む場合、その周回では、配列の要素をずらす作業を丸ごと省略できますから、非常に少ない処理時間でその周回は終わらせることができます。これが挿入ソートの大きな特徴で、事前にソート済みになっている部分が多ければ多いほど、ソート作業が高速に完了できます。

挿入ソートの計算量は [O(n2)] であり、これまでに取り上げてきた、単純ソート、選択ソート、バブルソートと同じです。しかし、ソート済みになっている部分が多ければ、挿入ソートは圧倒的に速くなります。

また、データ列が連結リスト（【データ構造】第３章）のように、要素の挿入が効率的に行えるものであれば、挿入が毎回行われたとしても、それほど処理速度が落ちることはありません。


プログラム例

それでは、冒頭で確認した実行過程を踏まえて、挿入ソートのプログラムを書いてみましょう。

#include <stdio.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

static void insertion_sort(int* array, size_t size);
static void print_array(const int* array, size_t size);

int main(void)
{
    int array[] = {7, 2, 4, 5, 1, 6};

    print_array( array, SIZE_OF_ARRAY(array) );
    insertion_sort( array, SIZE_OF_ARRAY(array) );
    print_array( array, SIZE_OF_ARRAY(array) );

    return 0;
}

/*
    挿入ソート (昇順)
*/
void insertion_sort(int* array, size_t size)
{
    for( size_t i = 1; i < size; ++i ){
        size_t j;

        // array[i] を、array[0]～array[i] の適切な位置に挿入する。
        // 挿入位置を空けるために、後続の要素をずらす際、array[i] が上書きされてしまうので、
        // array[i] の値を tmp に保存してから始める。

        int tmp = array[i];
        for( j = i; j > 0 && array[j-1] > tmp; --j ){
            array[j] = array[j-1];
        }
        array[j] = tmp;
    }
}

/*
    配列の要素を出力
*/
void print_array(const int* array, size_t size)
{
    for( size_t i = 0; i < size; ++i ){
        printf( "%d ", array[i] );
    }
    printf( "\n" );
}

実行結果：

7 2 4 5 1 6
1 2 4 5 6 7

insertion_sort関数の中で、挿入ソートを行っています。

まず、外側の for文によって制御される変数i は、整列済みの部分へ挿入する要素を指す添字です。この章の冒頭で示した手順で見たように、初回は array[0] ではなく array[1] から開始できるので、i = 0; ではなく i = 1; で開始します。

ここからが少し複雑です。

array[i] の値を、array[0]～array[i] の範囲内の適切な位置に挿入したいのです。外側の for文が１周するたび、変数 i の値は増えていき、array[0]～array[i - 1] の範囲は整列済みになることを忘れないようにしてください。また、array[i] の適切な位置は、array[i] のままであることもあり得ることにも注意してください。

まず、int tmp = array[i]; として、array[i] の値を変数tmp に保存しています。このあと、整列済み範囲のどこかに挿入することになった場合、まず挿入位置以降の要素を後ろにずらして、挿入位置を空けなくてはなりません。そのときに、array[i] の元の値が上書きされてしまうので、変数tmp に退避させています。

そして、内側の for文が始まります。

この for文は、挿入位置を探すのと同時に、要素を後ろへずらす処理も行っています。挿入位置として適切かどうかを、for文の条件式がみています（array[j-1] > tmp）。後ろへずらす処理は、for文の内側で行っています（array[j] = array[j-1];）。

array[i] の挿入位置を探すとき、整列済み範囲は array[0]～array[i - 1] ですから、変数 j を i から始めて、整列済み範囲を後ろから先頭へ向かって調べています。

挿入位置が見つかった時点で for文を抜けます。この時点で、変数 j が適切な挿入位置を指しているので、array[j] に tmp（本来の array[i] の値）を代入して、挿入が完了します。

改良版挿入ソート

先ほどのサンプルプログラムは、昔から広く知られたオーソドックスな実装方法ですが、無駄な部分があります。

一番の無駄は、要素の挿入が不要（現在位置のままで良い場合）でも、変数tmp を書き戻すところです。変化しないのなら、書き戻す必要もないはずです。

int tmp = array[i];
for( j = i; array[j-1] > tmp; --j ){  // array[i] の位置が最初から適切だったら、
    array[j] = array[j-1];            // ここは１回も実行されず、要素はずらされない
}
array[j] = tmp;                       // そして、この書き戻しも不要である

だからといって、if文で囲んで回避しろというのではありません。

void insertion_sort(int* array, size_t size)
{
    for( size_t i = 1; i < size; ++i ){
        size_t j;

        int tmp = array[i];
        for( j = i; j > 0 && array[j-1] > tmp; --j ){
            array[j] = array[j-1];
        }
        if( array[j] != tmp ){  // ？
            array[j] = tmp;
        }
    }
}

こうしてしまうと、外側の for文が１回繰り返されるごとに、必ず１回の if文を通過することになり逆効果です。うまく無駄を回避するには、もっと広く書き換える必要があります。

void insertion_sort(int* array, size_t size)
{
    for( size_t i = 1; i < size; ++i ){
        int tmp = array[i];

        if( array[i-1] > tmp ){  // 挿入が必要か先に調べる
            size_t j = i;

            // 初回の j > 0 は必ず真であるし、
            // array[j-1] > tmp も先ほどチェックしたところなので、
            // do-while文にして条件判定を後に回す方が効率的。
            do {
                array[j] = array[j-1];
                --j;
            } while( j > 0 && array[j-1] > tmp );

            array[j] = tmp;  // ここで行えば、挿入が不要ならば通過しなくて済む
        }
    }
}

１つ目のポイントは、挿入が必要かどうかを、内側のループを始めるよりも前に行ってしまうことです。array[i-1] より array[i] の方が大きいのなら、そもそも挿入の必要はないので、その周回での処理は何もしなくていいのです。

２つ目のポイントは、内側の for文の条件式「j > 0」が初回は必ず真になるので、これを通さないように、do-while文に変形することです。コードが大きく変わったように見えますが、実のところ、していることは for文のときとまったく同じです。初期設定式の「j = i;」は手前に移動していますし、条件式は後ろへ移動されただけ、ループの中身と「–j」が do-while文の内側にそのままの形で残っています。

３つ目のポイントは、変数tmp を array へ書き戻す処理も、挿入が必要なときにだけ実行される位置に移動させたことです。


２つの実装の処理速度を比較してみます。

#include <stdio.h>
#include <stdlib.h>
#include "ppp_perform.h"

#define ARRAY_SIZE              50000
#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

static void init_array(int* array, size_t size);
static void insertion_sort(int* array, size_t size);
static void insertion_sort_ex(int* array, size_t size);

int main(void)
{
    int array[ARRAY_SIZE];


    init_array( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    insertion_sort( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("insertion_sort");

    init_array( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    insertion_sort_ex( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("insertion_sort_ex");

    return 0;
}

/*
    配列を初期化
*/
void init_array(int* array, size_t size)
{
    srand(0);

    for( size_t i = 0; i < size; ++i ){
        array[i] = rand() % size;
    }
}

/*
    挿入ソート (昇順)
*/
void insertion_sort(int* array, size_t size)
{
    for( size_t i = 1; i < size; ++i ){
        size_t j;

        // array[i] を、array[0]～array[i] の適切な位置に挿入する。
        // 挿入位置を空けるために、後続の要素をずらす際、array[i] が上書きされてしまうので、
        // array[i] の値を tmp に保存してから始める。

        int tmp = array[i];
        for( j = i; j > 0 && array[j-1] > tmp; --j ){
            array[j] = array[j-1];
        }
        array[j] = tmp;
    }
}

/*
    改良版挿入ソート (昇順)
*/
void insertion_sort_ex(int* array, size_t size)
{
    for( size_t i = 1; i < size; ++i ){
        int tmp = array[i];

        if( array[i-1] > tmp ){  // 挿入が必要か先に調べる
            size_t j = i;

            // 初回の j > 0 は必ず真であるし、
            // array[j-1] > tmp も先ほどチェックしたところなので、
            // do-while文にして条件判定を後に回す方が効率的。
            do {
                array[j] = array[j-1];
                --j;
            } while( j > 0 && array[j-1] > tmp );

            array[j] = tmp;  // ここで行えば、挿入が不要ならば通過しなくて済む
        }
    }
}

実行結果：

insertion_sort: 2.282000 seconds
insertion_sort_ex: 2.190000 seconds

わずかですが、改良版挿入ソートの方が高速になりました。

計算量については、改良版であっても特に変わらず O(n2) のままですが、ループ１回ごとの細かい無駄が減った効果が出ています。挿入ソートを使うのであれば、つねに改良版挿入ソートのほうを使えばいいです。


性能

挿入ソートは、整列済みな部分が多いほど高速になります。この特性を確認しておきましょう。

挿入ソートの実装には、改良版を使います。

#include <stdio.h>
#include <stdlib.h>
#include "ppp_perform.h"

#define ARRAY_SIZE              50000
#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

static void init_array(int* array, size_t size);
static void init_array2(int* array, size_t size);
static void insertion_sort_ex(int* array, size_t size);

int main(void)
{
    int array[ARRAY_SIZE];


    init_array( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    insertion_sort_ex( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("insertion_sort_ex (1)");

    init_array2( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    insertion_sort_ex( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("insertion_sort_ex (2)");
    
    return 0;
}

/*
    配列を初期化
*/
void init_array(int* array, size_t size)
{
    srand(0);

    for( size_t i = 0; i < size; ++i ){
        array[i] = rand() % size;
    }
}

/*
    配列を初期化
*/
void init_array2(int* array, size_t size)
{
    srand(0);

    size_t i;

    // 先頭から 90% 部分は整列済みにしておく
    for( i = 0; i < size / 10 * 9; ++i ){
        array[i] = (int)i;
    }

    // 残り 10% はランダム
    for( ; i < size; ++i ){
        array[i] = rand() % size;
    }
}

/*
    改良版挿入ソート (昇順)
*/
void insertion_sort_ex(int* array, size_t size)
{
    for( size_t i = 1; i < size; ++i ){
        int tmp = array[i];

        if( array[i-1] > tmp ){  // 挿入が必要か先に調べる
            size_t j = i;

            // 初回の j > 0 は必ず真であるし、
            // array[j-1] > tmp も先ほどチェックしたところなので、
            // do-while文にして条件判定を後に回す方が効率的。
            do {
                array[j] = array[j-1];
                --j;
            } while( j > 0 && array[j-1] > tmp );

            array[j] = tmp;  // ここで行えば、挿入が不要ならば通過しなくて済む
        }
    }
}

実行結果：

insertion_sort_ex (1): 2.244000 seconds
insertion_sort_ex (2): 0.519000 seconds

init_array関数は、配列の要素すべてをランダムな値で初期化しています。init_array2関数のほうは、先頭の 90% 部分までは昇順になるように値を入れ、残り 10% はランダムに初期化しています。

結果、前者の配列は 2.244秒、後者の配列は 0.519秒でソートすることができました。

まとめ

挿入ソートの計算量は O(n2) で、整列アルゴリズムとしては遅い部類に入ります。

挿入ソートは、一般的には安定なアルゴリズムです。

対象のデータ列が、事前にある程度ソート済みな状態になっていると、ソートが完了するまでの時間も短くすむという重要な特徴があります。もしほとんどソートされていなかったとしても、選択ソートやバブルソートなどの同程度の性能をもつアルゴリズムよりも、良い結果になることが多いので、簡単なソートアルゴリズムを使うのなら、挿入ソートを選択するのが適切です。

なお、挿入ソートを改良したアルゴリズムとして、シェルソート（次章）があります。安定でなくなってしまうことが欠点になり得ますが、少しの改造で効率を向上できます。


練習問題

問題①　元のデータ列が事前にソートされている範囲を変えると、実行時間はどのくらい増減しますか？　ご自分の実行環境で確認してみてください。

問題②　改良版挿入ソートを、降順にソートするようにしてください。

問題③　挿入位置を探すとき、二分探索（【探索】第４章参照）の考え方を使えば高速化を図れる可能性があります。改良版挿入ソートをこの方法で実装してください。


解答ページはこちら。

参考リンク


更新履歴

’2015/12/27　SIZE_OF_ARRAYマクロの定義を修正。

≪さらに古い更新履歴を展開する≫


前の章へ　（第３章　バブルソート）

次の章へ　（第５章　シェルソート（挿入ソートの改良））

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ

はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポスト／フォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る