C言語アルゴリズム-シェルソート

シェルソート (shell sort:改良挿入法)とは

シェルソートとは、1959年にDonald.L.Shellによって発表された、複数回にわたって挿入ソートアルゴリズムを適用する整列アルゴリズムです。

まずは遠く離れた要素を整列の対象にして挿入ソートを行い、徐々に要素間を近づけて挿入ソートを繰り返して、最終的に隣り合った要素を整列（挿入ソート）します。挿入ソートでは、要素位置（配列の添え字）を1ずつ動かしながら順番に比較しますが、シェルソートでは動かす幅を可変にします。

シェルソートの整列過程

８つの要素を「4-ソート」→「2-ソート」→「1-ソート」します。


before  : 18 52 21 32 15  5 72 55
         ( A  B  C  D  A  B  C  D)
1 round : 15  5 21 32 18 52 72 55
         ( A  B  A  B  A  B  A  B)
2 round : 15  5 18 32 21 52 72 55
3 round :  5 15 18 21 32 52 55 72
after   :  5 15 18 21 32 52 55 72

※数値下のアルファベットは比較と交換を行う要素のグループとなります。

h-ソート (h-sort)について

h-ソートとは、hずつ離れた要素を整列することです。

hの初期値と減少幅は、「1から順番に3倍して1を足した値」にすると良いとKnuthの解析結果で報告されています。


h = 1, 4, 13, 40, 121, 364, ...
h(n+1) = 3h(n+1)

要素のとび幅「h」をどのような数にするかは処理性能に関わります。例えば要素に倍数の関係にあった場合、配列の奇数目と偶数目でグループ化されてしまい、グループが混ざるのが「最後の1-ソート」となってしまいます。

シェルソートの性能

平均計算時間は「O(n ^ 1.25)からO(n ^ 1.5)くらい」であり、最良計算時間は「O(n)」となります。

シェルソートは、クイックソートが考案されるまで最速の整列アルゴリズムとして知られていました。シェルソートは挿入ソートの「用意されているデータがある程度整列されているときは高速である」という長所を上手く利用しているアルゴリズムといえます。

シェルソートは安定ソートではない。

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

C言語によるシェルソートのプログラム


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

/*!
 * @brief       配列にランダムな数値を格納する。
 * @param[out]  array  数値格納先の配列
 * @param[in]   size   配列のサイズ
 */
static void
array_random_number(int *array, unsigned int size)
{
    int i;

    /* 起動毎に異なる乱数を発生させる */
    srand((unsigned int)time(NULL));
    for(i = 0; i < size; i++){
        array[i]=rand();
    }
}

/*!
 * @brief       配列内容を表示する
 * @param[in]   array  数値格納先の配列
 * @param[in]   size   配列のサイズ
 */
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   配列のサイズ
 * @param[in]      gap    交換のとび幅
 */
static void
gap_insertion_sort(int *array, unsigned int size, int gap)
{
    int i, j;
    int tmp;

    for(i = gap; i < size; i++){
        for(j = i - gap; j >= 0; j -= gap){
            if(array[j] > array[j + gap]){
                /* 要素の交換 */
                tmp = array[j];
                array[j] = array[j + gap];
                array[j + gap] = tmp;
            }else{
                break;
            }
        }
        array_print(array, size);
    }
}

/*!
 * @brief          シェルソートを行う。
 * @param[in/out]  array  整列する要素配列
 * @param[in]      size   配列のサイズ
 */
void
shell_sort(int *array, unsigned int size)
{
    int h = 1;

    /* hの初期値を計算する */
    while(h < size){
        h = h * 3 + 1;
    }

    for(; h > 0; h /= 3){
        printf("---------[h = %d]---------\n", h);
        gap_insertion_sort(array, size, h);
    }
}

int
main(void)
{
    //int data[] = {10,8,2,9,5,3,6,1,4,7};
    int data[32];
    array_random_number(data, sizeof(data)/4);

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

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

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

    return(0);
}