ももの知恵の樹

C言語アルゴリズム-挿入ソート

挿入ソート(insertion sort)とは

挿入ソートとは、整列済みのデータ列に対して、新たな要素を適切な位置へ挿入していく整列アルゴリズムです。配列の前部から順番に整列データを作成していくことで整列を行います。「挿入」の操作そのものは、バブルソートと同じ要領です。


挿入ソートはアルゴリズムが単純で実装が容易であり、ほぼ整列済みのデータならば離れた所まで挿入する事が少なくなるので、かなり高速な処理が可能であるため、しばしば用いられます。（挿入ソートを高速化したソート法として、シェルソートがあります。）

最悪計算時間 O(n ^ 2)
最良計算時間 O(n)
平均計算時間 0(n ^ 2)

挿入ソートは安定ソートである。

安定ソート（stable sort）とは、同等なデータのソート前の順序が、ソート後も保存される整列方法です。つまり、ソート途中の各状態において、常に既存順位の位置関係を保ちます。


挿入ソートの整列過程

配列の先頭から末尾の順で、内部的な整列済み配列を作成していきます。

挿入処理はバブルソートと同様です。 


[before]:6 2 1 5 3 4 
---------[1 round]---------
[2 6] 1 5 3 4 
---------[2 round]---------
[2 1 6] 5 3 4 
[1 2 6] 5 3 4 
---------[3 round]---------
[1 2 5 6] 3 4 
---------[4 round]---------
[1 2 5 3 6] 4 
[1 2 3 5 6] 4 
---------[5 round]---------
[1 2 3 5 4 6] 
[1 2 3 4 5 6] 
[after]:1 2 3 4 5 6

C言語による挿入ソートのプログラム


#include <stdio.h>

static void
array_print(int *array, unsigned int size)
{
    int i = 0;

    for(i = 0; i < size; i++){
        printf("%d ", array[i] );
    }
    putchar('\n');
}

/*!
 * @brief          挿入ソートを行う
 * @param[in/out]  array  整列する要素配列
 * @param[in]      size   配列のサイズ
 */

void
insertion_sort( int *array, unsigned int size )
{
    int i, j, temp;

    for(i = 1; i < size; i++){
        printf("---------[%d round]---------\n", i);
        j = i;

        /* 整列済み配列に挿入する */
        while((j > 0) && (array[j - 1] > array[j])){
            temp = array[j];
            array[j] = array[j - 1];
            array[j - 1] = temp;
            j--;
        }

        array_print(array, size);
    }
}

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

    printf("[before]:");
    array_print(data, sizeof(data)/4);

    insertion_sort(data, sizeof(data)/4);

    printf("[after]:");
    array_print(data, sizeof(data)/4);

    return(0);
}

関連ページ