アルゴリズムとデータ構造編【整列】 第5章 シェルソート(挿入ソートの改良)

先頭へ戻る

この章の概要

この章の概要です。


シェルソート

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

改良挿入法と呼ぶこともあります。なお、「シェル」は考案者の名前から来ています。

シェルソートは、挿入ソート(前章)を何度か繰り返すことによって高速化を図ったアルゴリズムです。これだけ聞くと、かえって遅くなるように思えますが、挿入ソートの適用の仕方に工夫があります。

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

この操作を繰り返していくと、最終的には h = 1 になります。h = 1 で挿入ソートを行うことは、データ列全体を普通に挿入ソートすることと同じです。この段階まで来ると、データ列全体はかなりの割合で「整列済み」な状態になっているはずです。挿入ソートは「すでに整列済みになっている部分が多いほど高速になる」という特性があるため、最後の挿入ソートはかなり高速に終えられるはずです。

(h > 1) で行うソートには、最終的にソートを終えたとき、データ列の手前側に来るべき要素を、早い段階で手前の方へと移動させる効果があります。単なる挿入ソートが遅くなる原因の1つは、挿入を行う際に、挿入位置よりも後ろにある要素をずらさなくてはならないからです。特に、データ列の末尾に近いところにある要素を先頭付近に持ってくると、要素をずらすだけでも、相当な時間が掛かってしまう訳です。

このように、後ろの方の要素をすばやく手前へ移動できることと、最後に行われる 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] の組の4組を作れます。それぞれ、次のようにソートされます。

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

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

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

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

{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 になった時点で、「ほぼ整列済みになっている」という期待が、成り立ちにくくなってしまいます。

そこで、「hn+1 = 3hn + 1」という条件で選び出した数列「1, 4, 13, 40, 121, ...」を使うと良いとされています。証明はかなり難しいようですが、この数列の中から h を選ぶと、良い結果が得られることが分かっています。

この数列を使うと、例えば、要素数 100 の配列に対しては、h の値を 40, 13, 4, 1 の順番で狭めていけば良いという訳です。

ただ、要素数 100 に対して h = 40 というのは、あまりにも遠く離れた小数の要素同士のソートにしかならず、効果が薄い可能性があります。そのため、データ数に比べて間隔が広すぎるような h は、省いた方が良いと言われることもあります。

そこで、「要素数 / 9」を超えないように h を選ぶという方針を採ることがあります。「要素数 / 9」は、100 / 9 = 11 なので、h = 40, 13 では大きすぎます。従って、h = 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)
{
    size_t i, j;
    size_t h, h_tmp;
    int tmp;


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

    while( h > 0 ){
        for( i = h; i < size; ++i ){
            tmp = array[i];
            for( j = i; j >= h && array[j-h] > tmp; j -= h ){
                array[j] = array[j-h];
            }
            array[j] = tmp;
        }
        h /= 3;  /* 間隔を縮める */
    }
}

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

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

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

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

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

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

挿入ソートは、間隔 h が 1 であるときと同じになるはずなので、基本的には、挿入ソートのプログラムで 1 になっているところを h に置き換えていけば良いということになります。for文の条件式「j > 0」のところは「j >= h」に変更していますが、これも「j >= 1」だったと考えれば、やはり 0 を h に変えただけだと分かると思います。

シェルソートの性能

挿入ソートとシェルソートの性能を比較してみましょう。ここでは、それぞれのアルゴリズムは、コードライブラリの ppps_int_sort を使うようにしています。実装は解説通りになっていると考えて結構です。

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

#define ARRAY_SIZE              100000
#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_shell_sort( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("shell_sort");

    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: 11.564000 seconds
shell_sort: 0.038000 seconds

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

データ件数挿入ソートシェルソート
1000個0.002秒0秒 (計測不能)
10000個0.145秒0.003秒
100000個11.564秒0.038秒
1000000個1237秒0.606秒

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

一方、シェルソートの方は、データ件数が 10倍になっても、処理時間はせいぜい 16倍程度の増加に抑えられています。シェルソートの計算量は O(n1.25)~O(n1.5)程度なので、この程度の処理時間の増加で済みます。

今回の実験環境の場合、10000個程度のソートであれば明確に処理時間に差が出ています。ある程度、データ件数が多いのであれば、シンプルな挿入ソートよりもシェルソートを使った方が良いと言えます。

なお、前章でみたように、挿入ソートには少し改良の余地があります。同じ改良をシェルソート内の挿入ソート部分に適用すれば、同様に効率向上が図れる可能性があります。これについては、練習問題に残しておきます。

まとめ

シェルソートの計算量は O(n1.25)~O(n1.5) 程度に収まると言われています。この揺らぎは、間隔 h の選び方に左右されるということです。本章で取り上げた実装では、ほぼ O(n1.25) に近い性能になると言われています。挿入ソートが O(n2) ですから、より良い性能を示すことが分かります。

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

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

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


練習問題

問題① 間隔 h を、1,2,4,8,16,32... のような数列から選んだ場合の性能を調べてください。

問題② 前章の改良版挿入ソートと同じ改良を、シェルソートに適用し、性能差を調べてください。


解答ページはこちら

参考リンク



更新履歴

'2018/1/15 冒頭部分の解説が、サンプルプログラムの実装方法と一致していなかったので、解説文を大幅に修正。

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

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

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

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

'2012/6/9 新規作成。



前の章へ (第4章 挿入ソート)

次の章へ (第6章 クイックソート)

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

Programming Place Plus のトップページへ


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