挿入ソート

Copyright(C) 5July2010 coskx TNCT

ソートのアルゴリズムのうち高速ではないが，考え方は興味深いので挿入ソートについて解説する

１．挿入ソート

図は挿入ソートの途中を示している。
状態Aでは，要素5までが昇順にソート済であり，現在要素6をソート済領域に挿入しようとするところである。
状態Bでは，要素6を退避場所に移動したところである。
状態Bで，要素5と退避場所の値を比べ，要素5の方が大きいから右にずらす。
要素4と退避場所の値を比べ，要素5の方が大きいから右にずらす。
要素3と退避場所の値を比べ，要素5の方が大きいから右にずらす。
要素2と退避場所の値を比べ，要素5の方が大きいから右にずらす。
要素1と退避場所の値を比べ，要素5の方が小さいからずらす作業をやめる。
状態Cはずらす作業をやめたところである。
状態Dは退避場所の値を，隙間（要素2の位置）に移動したところである。
この作業により，ソート済の領域が1要素分広がった。

この後，要素7を挿入しようとすると，一度退避場所へ移動するが，右に移動する要素がないため，
元あった位置に戻ることになるであろう。
さらに要素8を挿入しようすると，すべての要素が右に移動して，要素8は先頭に挿入されることになるであろう。

２．挿入ソートのプログラミング

挿入ソートの骨組みを考えてみよう。
挿入作業を行うのは，先頭要素はする必要がないため，要素1から最後の要素までである。
移動させるかどうか考える要素としては，挿入作業要素のすぐ左から順に先頭に向かって作業する。
ただし，先頭より左側に対して作業しないように気をつけなければならない。

List 1 挿入ソート関数
x:挿入ソート対象の先頭アドレス
num:配列要素数

void insertionsort(int x[], int num)
{
    int i;     /*挿入要素の番号*/
    int j;     /*要素を退避したことによって生まれる空要素の要素番号*/
    int tmp;   /*退避場所*/
    for (i=1; i<num; i++) {
        tmp=x[i]; /*着目要素の退避*/
        j=i;
        /*tmpと比較して右移動させるかどうか検討する要素はx[j-1]*/
        while ( 0<j && tmp<x[j-1] ) {
            x[j]=x[j-1];
            j--;
        }
        x[j]=tmp;
    }
}


３．挿入ソートのプログラミング（番兵法 sentinel）

上のプログラムでは，whileの検証内容が tmp<x[j] と 0<=j の２つあった。１ループにつき２つの比較を1つに減らしたい。
whileの検証内容を tmp<x[j] １つにするために番兵法がよくつかわれる。
これは，些細なことであるが，高速化の手法としてよくつかわれている。
tmpとの比較対象の最後，すなわち配列の先頭にtmp自身を入れておけば， 0<=j の範囲で必ず tmp<x[j] を満たさないことが起こり，whileループから必ず脱出するので， 0<=j の条件が不要になる。

List 2 挿入ソート関数　番兵法
x:挿入ソート対象の先頭アドレス
num:配列要素数

void insertionsort_withSentinel(int x[], int num)
{
    int i;     /*挿入要素の番号*/
    int j;     /*要素を退避したことによって生まれる空要素の要素番号*/
    int tmp;   /*先頭要素の退避場所*/
    for (i=1; i<num; i++) {
        tmp=x[0];  /*先頭要素を退避*/
        x[0]=x[i]; /*挿入対象の値を第0要素にする*/
        j=i;
        /*x[0]と比較して右移動させるかどうか検討する要素はx[j-1]*/
        while (x[0]<x[j-1]) {
            x[j]=x[j-1];
            j--;
        }
        if (j==1) { /*whileループで先頭まで到達した*/
            if (tmp<x[0]) {
                x[1]=x[0];
                x[0]=tmp;
            } else {
                x[1]=tmp;
            }
        } else { /*途中でwhileを脱出した*/
            x[j]=x[0];
            x[0]=tmp;
        }
        //printData(data,SIZE);
    }
}


whileループを脱出した後の記述は，論理的同値変換で次のように短く記述できる。

List 2 の論理

 

j=1

1<j

tmp<x[0]

x[1]=x[0],x[0]=tmp

x[j]=x[0],x[0]=tmp

tmp=x[0]

x[1]=tmp

x[j]=x[0],x[0]=tmp *1

x[0]<tmp

x[1]=tmp

あり得ない

List3 の論理

 

j=1

1<j

tmp<x[0]

x[j]=x[0],x[0]=tmp

x[j]=x[0],x[0]=tmp

tmp=x[0]

x[j]=tmp

x[j]=tmp  *2

x[0]<tmp

x[j]=tmp

あり得ない


*1では，tmp=x[0]なので，1<jで抜け出した場合は，抜け出した時点で，空の要素より若い番号の要素はすべてtmpおよびx[0]と同じ値のはずである。
そのため，*2の記述でも同じ結果になる。

List 3 挿入ソート関数　番兵法
x:挿入ソート対象の先頭アドレス
num:配列要素数

void insertionsort_withSentinel2(int x[], int num)
{
    int i;     /*挿入要素の番号*/
    int j;     /*要素を退避したことによって生まれる空要素の要素番号*/
    int tmp;   /*先頭要素の退避場所*/
    for (i=1; i<num; i++) {
        tmp=x[0];  /*先頭要素を退避*/
        x[0]=x[i]; /*挿入対象の値を第0要素にする*/
        j=i;
        /*x[0]と比較して右移動させるかどうか検討する要素はx[j-1]*/
        while (x[0]<x[j-1]) {
            x[j]=x[j-1];
            j--;
        }
        if (x[0]<=tmp) {
            x[j]=tmp;
        } else {
            x[j]=x[0];
            x[0]=tmp;
        }
        //printData(data,SIZE);
    }
}


 

４．挿入ソートのプログラミング例

挿入ソート関数を用いたプログラミング例を次に示す。

List 4 挿入ソートプログラミング例

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 100

int data[SIZE];

void printData(int x[], int num)
{
    int i;
    for (i=0; i<num; i++) {
        printf("%6d",x[i]);
        if (i%10==9) printf("\n");
    }
}

void generateData(int x[], int num)
{
    int i;
    for (i=0; i<num; i++) x[i]=rand();
}

void insertionsort(int x[], int num)
{
    int i;     /*挿入要素の番号*/
    int j;     /*要素を退避したことによって生まれる空要素の要素番号*/
    int tmp;   /*退避場所*/
    for (i=1; i<num; i++) {
        tmp=x[i]; /*着目要素の退避*/
        j=i;
        /*tmpと比較して右移動させるかどうか検討する要素はx[j-1]*/
        while ( 0<j && tmp<x[j-1] ) {
            x[j]=x[j-1];
            j--;
        }
        x[j]=tmp;
    }
}

void insertionsort_withSentinel(int x[], int num)
{
    int i;     /*挿入要素の番号*/
    int j;     /*要素を退避したことによって生まれる空要素の要素番号*/
    int tmp;   /*先頭要素の退避場所*/
    for (i=1; i<num; i++) {
        tmp=x[0];  /*先頭要素を退避*/
        x[0]=x[i]; /*挿入対象の値を第0要素にする*/
        j=i;
        /*x[0]と比較して右移動させるかどうか検討する要素はx[j-1]*/
        while (x[0]<x[j-1]) {
            x[j]=x[j-1];
            j--;
        }
        if (j==1) { /*whileループで先頭まで到達した*/
            if (tmp<x[0]) {
                x[1]=x[0];
                x[0]=tmp;
            } else {
                x[1]=tmp;
            }
        } else { /*途中でwhileを脱出した*/
            x[j]=x[0];
            x[0]=tmp;
        }
    }
}

void insertionsort_withSentinel2(int x[], int num)
{
    int i;     /*挿入要素の番号*/
    int j;     /*要素を退避したことによって生まれる空要素の要素番号*/
    int tmp;   /*先頭要素の退避場所*/
    for (i=1; i<num; i++) {
        tmp=x[0];  /*先頭要素を退避*/
        x[0]=x[i]; /*挿入対象の値を第0要素にする*/
        j=i;
        /*x[0]と比較して右移動させるかどうか検討する要素はx[j-1]*/
        while (x[0]<x[j-1]) {
            x[j]=x[j-1];
            j--;
        }
        if (x[0]<=tmp) {
            x[j]=tmp;
        } else {
            x[j]=x[0];
            x[0]=tmp;
        }
    }
}

int main()
{
    srand((unsigned) time(NULL)); /*乱数列生成の初期化*/
    generateData(data,SIZE);
    printf("befor sort\n");
    printData(data,SIZE);
    //insertionsort(data,SIZE);                /*この3つのうちどれか1つを有効にする*/
    //insertionsort_withSentinel(data,SIZE);   /*この3つのうちどれか1つを有効にする*/
    insertionsort_withSentinel2(data,SIZE);    /*この3つのうちどれか1つを有効にする*/
    printf("\nafter sort\n");
    printData(data,SIZE);
}