アルゴリズムとデータ構造編【整列】 第4章 挿入ソート

先頭へ戻る

この章の概要

この章の概要です。


挿入ソート

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

挿入ソートは、整列済みのデータ列に対して、新たな要素を適切な位置へ挿入していくことによってソートを行います。詳しい手順を見ていきましょう。

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

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

挿入ソートでは、先頭から m個までの部分が「整列済み」となるようにしなくてはなりません。そこでまず、array[0] は整列済みなつもりで開始します。

次に array[1] に注目します。array[1] には 2 がありますが、これを整列済みのデータ列(現在のところ array[0] だけしかない)に挿入します。array[0] の 7 よりは手前に来なければならないので、array[0] の手前に挿入するのが正しいということになります。配列なので array[0] にあった 7 を後方へずらして割り込ませることになります。その結果、次のようになります。

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

この時点で、array[0]~array[1] の部分が「整列済み」となります。次に、array[2] に注目します。array[2] は 4 なので、整列済みである {2, 7} の間に挿入します。

{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};

配列の末尾まで行き着いたので、これでソート完了です。

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

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

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

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

しかし、挿入位置を探した結果、結局、挿入の必要がない場合があります。例えば、{0, 2, 3, 5, 9, 7} のようになっており、array[0]~array[3] の部分が整列済みなとき、array[4] の 9 の挿入位置は、array[4] になりますから、移動させなくて良いということになります。

挿入しなくて済むのなら、配列の要素をずらしていく作業を丸ごと省略できますから、ソート作業全体が高速になります。これが挿入ソートの大きな特徴で、事前にソート済みになっている箇所が多ければ多いほど、ソート作業が高速に完了できます


プログラム例

では、先ほどの過程を元に、実際のプログラムを書いてみましょう。

#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)
{
    size_t i, j;
    int tmp;

    for( i = 1; i < size; ++i ){
        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)
{
    size_t i;

    for( 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; で開始します。

内側の for文では、適切な挿入位置を探しながら、要素を後方へずらしています。後方へずらす際に、array[i] が上書きされてしまうので、事前に変数tmp にコピーを取っており、挿入位置が決定したら(変数j が挿入位置を指した状態で、内側の for文を抜け出しています)、コピーを書き戻します。

改良版挿入ソート

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

一番の無駄は、要素の挿入が不要(現在位置のままで良い場合)でも、変数tmp を書き戻しているところです。変化していないのなら、書き戻す必要もない訳です。だからといって、こんな風に、if文で囲んで回避しろというのではありません。

void insertion_sort(int* array, size_t size)
{
    size_t i, j;
    int tmp;

    for( i = 1; i < size; ++i ){
        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文が1回繰り返されるごとに、必ず1回の if文を通過することになり逆効果です。うまく無駄を回避するには、もっと広く書き換える必要があります。

void insertion_sort_ex(int* array, size_t size)
{
    size_t i, j;
    int tmp;

    for( i = 1; i < size; ++i ){
        tmp = array[i];

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

            /* 初回の j > 0 は必ず真(i=1; であり j=i; をしたのだから) であるし、
               array[j-1] > tmp も先ほどチェックしたところなので、
               do-while文にして条件判定を後に回す方が効率的。
               for( j = i; j > 0 && array[j-1] > tmp; --j ); としていることはまったく同じで、
               単に do-while文に書き換えただけ。
            */
            do {
                array[j] = array[j-1];
                --j;
            } while( j > 0 && array[j-1] > tmp );

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

1つ目のポイントは、挿入が必要なのかどうかを、内側のループが登場する前に行ってしまうことです。昇順にソートしようとしているので、array[i-1] より array[i] の方が大きいのなら、そもそも挿入の必要はないのです。

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

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

2つの実装で、パフォーマンスを比較してみます。ここでは、それぞれのアルゴリズムは、コードライブラリの ppps_int_sort を使うようにしています。実装は解説通りのものになっていると考えて頂いて結構です。

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

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

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

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


    init_array( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    ppps_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);
    ppps_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)
{
    size_t i;

    srand(0);

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

実行結果:

insertion_sort: 2.354000 seconds
insertion_sort_ex: 2.352000 seconds

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

まとめ

挿入ソートの計算量は O(n2) で、遅い整列アルゴリズムだと言えます。しかし、選択ソート(第2章)やバブルソート(第3章)と比べると、挿入ソートの方が良い結果を示すことが多いです。

また、対象のデータ列が、事前にある程度ソート済みな状態になっていると、ソートが完了するまでの時間も短くすむという特徴があります。これは、挿入位置を探す処理は走るものの、実際に要素を動かす処理が削減できるためです。

挿入ソートは、一般的には安定なアルゴリズムです。 ただ、挿入位置を探す部分の実装次第では、安定性を失う可能性があります。

なお、挿入ソートを改良したアルゴリズムとして、シェルソート次章)があります。


練習問題

問題① 最初に紹介した改良版でない方の挿入ソートを、降順にソートするようにして下さい。

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

問題③ 挿入位置を探すとき、二分探索(【探索】第4章参照)の考え方を使えば高速化を図れる可能性があります。その方法で実装して下さい。


解答ページはこちら

参考リンク



更新履歴

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

'2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。

'2013/1/19 性能調査を、コードライブラリのソースを使って行うように変更。

'2012/6/23 コードライブラリのパス変更に伴い、リンクを修正。

'2012/6/8 パフォーマンス計測の方法を修正。

'2012/6/2 新規作成。



前の章へ(第3章 バブルソート)

次の章へ(第5章 シェルソート(挿入ソートの改良))

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

Programming Place Plus のトップページへ


はてなブックマーク Pocket に保存 Twitter でツイート Twitter をフォロー
Facebook でシェア Google+ で共有 LINE で送る rss1.0 取得ボタン RSS
管理者情報 プライバシーポリシー