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

この章の概要

この章の概要です。

• シェルソート
• 間隔の決め方
• シェルソートのプログラム例
• シェルソートの性能
• まとめ
• 練習問題
• 参考リンク
• 更新履歴

シェルソート

この章では、シェルソートを取り上げます。

「シェル」は考案者 Donald L. Shell の名前から来ています。

シェルソートは、改良挿入ソート（改良挿入法）と呼ばれることもあります。その呼び名のとおり、挿入ソート（第４章）をよりうまく使うことで、効率の向上を図ります。

シェルソートでは、挿入ソートを離れた要素どうしで挿入ソートを行うことを何度か繰り返します。これだけ聞くと、かえって遅くなるように思えますが、挿入ソートの適用の仕方に工夫があります。

まず、適当な間隔 h を決定し、この間隔だけ離れた要素同士で挿入ソートを行います。その後、h を少し狭めて、やはりその間隔だけ離れた要素同士で挿入ソートを行います。

この操作を繰り返していき、最終的には h = 1 の状態で挿入ソートを行います。h = 1 で挿入ソートを行うことは、データ列全体を普通に挿入ソートすることと同じです。

挿入ソートには、「すでに整列済みになっている部分が多いほど高速になる」という特性があるため、全体を荒くソートしていくことで、結果的に全体のソートはかなり高速に終えられるという理屈です。

(h > 1) で行う挿入ソートには、最終的にソートを終えたとき、データ列の手前側に来るべき要素を、早い段階で手前の方へと移動させる効果があります。単なる挿入ソートがそれほど速くない原因の１つは、挿入を行うときに、挿入位置よりも後ろにある要素を “１つ１つ” ずらさなくてはならないからです。(h > 1) で行う挿入ソートでは、“h個ずつ” ずらしていけます。

このように、要素をすばやく目的の位置へ移動できることと、最後に行う h = 1 のソートの際にほぼ整列済みの状態を作れることで、短時間でソートを終えられます。

シェルソートの詳しい手順を見ていきましょう。以下の配列を昇順にソートします。

int array[] = {7, 3, 11, 30, 6, 9, 16, 22, 10, 4};

まず、間隔 h を決めます。ここでは h = 4 とします（後述しますが、間隔の決め方として一般的によく使われているものがあります。ここではあくまで例として h = 4 とします）。

h の意味は、ソート処理の対象にする要素同士の距離です。h = 4 であれば、[0][4][8] の組、[1][5][9] の組、[2][6] の組、[3][7] の組の４組を作れます。それぞれ、次のようにソートされます。

• [0][4][8] の組 (7, 6, 10 –> 6, 7, 10)
• [1][5][9] の組 (3, 9, 4 –> 3, 4, 9)
• [2][6] の組 (11, 16 –> 11, 16)
• [3][7] の組 (30, 22 –> 22, 30)

（手順を割愛していますが、それぞれの組は挿入ソートの手順でソートします）。

この結果、データ列全体としては、次のような状態になります。

{6, 3, 11, 22, 7, 4, 16, 30, 10, 9};

これで、h = 4 によるソートは終わったので、h を縮めます。今度は、半分の 2 としてみましょう。２つの組ができ、次のようにソートされます。

• [0][2][4][6][8] の組 (6, 11, 7, 16, 10 –> 6, 7, 10, 11, 16)
• [1][3][5][7][9] の組 (3, 22, 4, 30, 9 –> 3, 4, 9, 22, 30)

結果、データ列全体は、次のような状態になります。

{6, 3, 7, 4, 10, 9, 11, 22, 16, 30};

これで、h = 2 によるソートは終わったので、h を縮めます。今度は h = 1 です。これはデータ列全体を普通に挿入ソートすることと同じです。結果、データ列全体は、次のような状態になります。

{3, 4, 6, 7, 9, 10, 11, 16, 22, 30};

これでシェルソートが完了します。

間隔の決め方

シェルソートでは、間隔 h の決め方が重要になってきます。

先ほどの手順の説明では、h = 4, 2, 1 としましたが、あまり良い選び方ではありません。これが良くない理由は、ソートの対象として同じ位置の要素ばかりが選択されてしまい、データ列全体を満遍なくソートできていないからです。

たとえば、array[0] を含む組み合わせは、h = 4 のときには [0][4][8] で、h = 2 のときには [0][2][4][6][8] です。また、array[1] を含む組み合わせは、h = 4 のときには [1][5][9] で、h = 2 のときには [1][3][5][7][9] となります。

これをよく見ると分かるように、偶数番目の要素同士、奇数番目の要素同士で組を作っていることが分かります。これでは、互いが混ざり合ってソートされることが h = 1 になるまで起こりませんから、h = 1 になった時点で、「ほぼ整列済みになっている」という期待が、成り立ちにくくなってしまいます。

そこで、「h_n+1 = 3h_n + 1」という条件で選び出した数列「1, 4, 13, 40, 121, …」を使う例がよく示されます。この数列は、1 から始まり、それ以降は 3倍して +1 したものです。この数列に登場する値を h として選ぶと、それなりに良い結果が得られることが知られています。

実際には、h は大きい値から縮めていかないといけないので、逆順で使います。たとえば、要素数 200 の配列に対しては、h の値を 121, 40, 13, 4, 1 の順番で狭めていきます。

ここで、h の最初の値の決め方もポイントになり得ます。要素数に対して、h の値が大きすぎると、あまりにも遠く離れた、ごく少数の要素同士のソートにしかならず、効果が薄い可能性があります。そのため、要素数に比べて間隔が広すぎるような h は使わない方が良いとされることもあります。

そこで、「要素数 / 9」を超えないように h を選ぶという方針を採ることがあります。要素数が 200 であるとすると、「200 / 9 = 22」なので、h の値として 121 や 40 では大きすぎます。h = 13, 4, 1 でソートすると効率が良い（のではないか）ということになります。

シェルソートのプログラム例

ここまでの理論を元に、シェルソートのプログラムを書いてみましょう。

#include <stdio.h>

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

static void shell_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) );
    shell_sort( array, SIZE_OF_ARRAY(array) );
    print_array( array, SIZE_OF_ARRAY(array) );

    return 0;
}

/*
    シェルソート (昇順)
*/
void shell_sort(int* array, size_t size)
{
    // 最初の間隔 h を決める
    // 1,4,13,40,121... のように、1 から始めて h=h*3+1 を満たす値を使う。
    // これらの値の中で、size / 9 を超えない一番大きい値を最初の h とする。
    size_t h = 1;
    for( size_t h_tmp = 1; h_tmp < size / 9; h_tmp = h_tmp * 3 + 1 ){
        h = h_tmp;
    }

    while( h > 0 ){
        for( size_t i = h; i < size; ++i ){
            int tmp = array[i];

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

                do {
                    array[j] = array[j-h];
                    j -= h;
                } while( j >= h && array[j-h] > tmp );

                array[j] = tmp;
            }
        }
        h /= 3;  // 間隔を縮める
    }
}

/*
    配列の要素を出力
*/
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

shell_sort関数の中でシェルソートを行っています。

まず、間隔 h の初期値を決めます。「間隔の決め方」のところで見たように、1,4,13,40,121,… となる数列の中から、配列の要素数 / 9 を超えない最大の値を使います。

あとは、間隔 h を縮めながら、挿入ソートを繰り返すだけです。間隔 h は、h = h * 3 + 1 という条件で選ぶようにしているので、１段階縮めるには (h - 1) / 3 とすればいいのですが、Ｃ言語では整数除算の結果、小数点以下が切り捨てられるので、単に h /= 3 でも同じ結果になります。

while文の内側は、前章の改良版挿入ソートのサンプルコードを、間隔 h でのソートになるように修正したもので、形は変わっていません。挿入ソートのコードは次のようになっていました。

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

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

        do {
            array[j] = array[j-1];
            --j;
        } while( j > 0 && array[j-1] > tmp );

        array[j] = tmp;
    }
}

挿入ソートは、間隔 h が 1 であるときと同じになるはずなので、基本的には、挿入ソートのプログラムで 1 になっているところを h に置き換えていけば良いということになります。

for文の条件式の j > 0 のところは、j >= h に変更していますが、j > 0 と j >= 1 は同じなので、やはり 0 を h に変えているだけです。

シェルソートの性能

挿入ソートとシェルソートの性能を比較してみましょう。挿入ソートの実装は、第４章でみた、改良版挿入ソートを使います。

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

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

static void init_array(int* array, size_t size);
static void insertion_sort_ex(int* array, size_t size);
static void shell_sort(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");

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

    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_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;

            do {
                array[j] = array[j-1];
                --j;
            } while( j > 0 && array[j-1] > tmp );

            array[j] = tmp;
        }
    }
}

/*
    シェルソート (昇順)
*/
void shell_sort(int* array, size_t size)
{
    // 最初の間隔 h を決める
    // 1,4,13,40,121... のように、1 から始めて h=h*3+1 を満たす値を使う。
    // これらの値の中で、size / 9 を超えない一番大きい値を最初の h とする。
    size_t h = 1;
    for( size_t h_tmp = 1; h_tmp < size / 9; h_tmp = h_tmp * 3 + 1 ){
        h = h_tmp;
    }

    while( h > 0 ){
        for( size_t i = h; i < size; ++i ){
            int tmp = array[i];

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

                do {
                    array[j] = array[j-h];
                    j -= h;
                } while( j >= h && array[j-h] > tmp );

                array[j] = tmp;
            }
        }
        h /= 3;  // 間隔を縮める
    }
}

実行結果：

insertion_sort_ex: 9.329000 seconds
shell_sort: 0.027000 seconds

10万個の要素のソートで比較すると、実行結果にあるように、圧倒的にシェルソートの方が高速になりました。ここで同じ環境で、データ件数を変えた結果を掲載します。

データ件数が 10倍になったとき、挿入ソートの処理時間は 10²倍 (＝100倍) 程度に増加しています。挿入ソートの計算量は O(n²) なので、これは妥当な結果です。

一方、シェルソートの計算量は O(n^1.25)～O(n^1.5)程度といわれているので、データ件数 10倍に対して、処理時間は 17～32倍程度になります。実測値では、14倍程度の増加に抑えられています。

【上級】シェルソートの計算量に範囲があるのは、h の選び方に左右されることと、数学的な解析が非常に困難であるためです。

今回の実験環境の場合、10000個程度のソートであれば明確に処理時間に差が出ています。100万個にもなると、挿入ソートでは実用的でないほど遅いですが、シェルソートなら（問題領域次第ですが）実用十分でしょう。

ある程度、データ件数が多いのであれば、シンプルな挿入ソートよりもシェルソートを使った方が良いといえます。

まとめ

シェルソートの計算量は O(n^1.25)～O(n^1.5) 程度に収まると言われています。この揺らぎは、間隔 h の選び方に左右されるということです。本章で取り上げた方法では、ほぼ O(n^1.25) に近い性能になると言われています。挿入ソートが O(n²) ですから、より良い性能であることが分かります。

データ件数が多いのなら、挿入ソートよりもシェルソートを選ぶと良いといえますが、シェルソートは安定でないことに注意してください。挿入ソートは安定なので、安定であることが必要ならばシェルソートに置き換えることはできません。

シェルソートが安定でないのは、最初に行われる間隔 h が 1 より大きいソートのときに、元のデータの順序が崩されてしまうからです。

シェルソートは、実装が比較的容易な割には、十分に実用に耐える性能を発揮してくれる良いソートアルゴリズムです。