シェルソート

http://www.geocities.jp/ky_webid/algorithm/005.html

シェルソートのお時間です。

シェルソートは、ある一定距離だけ離れた要素同士で交換処理を行い、この距離を少しずつ縮めていき、最後には普通に挿入ソートを実行することでソートを行います。

なるほど。組み合わせてソート処理を行うわけですね。

基本的な部分は、挿入ソートと同じである。挿入ソートは「ほとんど整列されたデータに対しては高速」という特長があるものの、「隣り合った要素同士しか交換しない」ため、あまり整列されていないデータに対しては低速であった。

そのため、適当な間隔をあけた飛び飛びのデータ列に対してあらかじめソートしておき、挿入ソートを適用すれば高速になると考えられる。この考え方を適用したのがシェルソートである。

1. 適当な間隔hを決める
2. 間隔hをあけて取り出したデータ列に挿入ソートを適用する
3. 間隔hを狭めて、2.を適用する操作を繰り返す
4. h=1になったら、最後に挿入ソートを適用して終了

シェルソート - Wikipedia

ふーむ。

この間隔hを配列の大きさから考えてどの程度にするのが妥当なのか、また間隔hをどの程度狭めていくのが妥当なのかがいまいちピンときませんね。

これは適当に割る２した値とかでいいのでしょうか？

間隔hとして、h=1, 4, 13, 40, 121,...という、hn+1=3hn+1を満たす整数列を用いて、hを大きい方から適用すると、計算時間O(n1.25)程度になる。

でやると良いのかな？とりあえず今回はこれでやってみます。

が・・・しかしこの式の解き方がわからん。

色々調べてたら数式の漸化式であることまで分かった。

これは数学の勉強の時に別途取り上げる予定なんだけど今回はとりあえず解く事だけを考えることにします。

http://shigihara.hp.infoseek.co.jp/zk11.htm

ここを参考にという解を求めました。

さっそく実装してみます。

#include <stdio.h>
#include <math.h>
#define ARRAY_NUM(a) (sizeof(a)/sizeof(a[0]))

void swap (int *a, int *b) {
    int work = *a;
    *a = *b;
    *b = work;
}

void shell_sort (int *data, int array_size) {
    int n=0;
    int h=1;
    int th;
    int i,j;
    
    if ( array_size <= 1 ) {
        return;
    }
    
    // 最大間隔ｈを求める
    while (++n) {
        th = ((int)pow(3,n) - 1) / 2;
        if ( th > array_size / 2 ) {
            n--;
            break;
        }
        h = th;
    }
    
    while(n--){
        for(i=0;i<array_size-h;++i){
            for(j=i+h;j-h>=0;j-=h){
                if ( data[j] < data[j-h] ) {
                    swap(&data[j],&data[j-h]);
                }
            }
        }
        h = ((int)pow(3,n) - 1) / 2;
    }
}

int main (void) {
    int num[] = { 8,3,1,2,7,5,6,4 };
    int i;
    int count = 1000;
    
    shell_sort(num,ARRAY_NUM(num));
    
    for(i=0;i<ARRAY_NUM(num);i++){
        printf("%d ",num[i]);
    }
    
    return 0;
}

できたにはできたのですが・・・。かなり微妙です。というかアルゴリズムって難しい・・・。

自分で捻り出すのは限界があるのかな？それとも僕がヒヨッコ過ぎるのだろうか。自信なくすよ。

というわけで一応仕様は満たせたはずです。

ただ挿入ソートよりも早いソートのはずなのに、前回作った自作ベンチマークコードで速度を量ってみたところ

// 配列の要素10個×1000000ループの場合
shell  0.891000 sec
insert 0.375000 sec

// 配列の要素540個×1000ループの場合
shell  1.110000 sec
insert 1.484000 sec

とまあ配列の要素数に関係なく挿入ソートの方が早かったのですorz

僕の書いたシェルソートは仕様を満たしているだけでアルゴリズムとしてはダメダメなんでしょうね。くやしー。

ということで解答例を確認したいと思います。

解答例との比較

/* 交換処理の間隔を決めるループ */
for(h=1; h<ARRAY_SIZE; h=h*3+1)
    ;

for( ;h>0; h/=3)  /* hは交換処理の間隔を表す */
{
    for(i=h; i<ARRAY_SIZE; ++i)  /* iは今回の交換処理で対象となる最後尾の添字 */
    {
        j = i;  /* jは交換対象となる要素の若い方の添字 */
        while(j >= h && array[j-h] > array[j])
        {
            /* 大小関係が逆なら交換処理 */
            work = array[j];
            array[j] = array[j-h];
            array[j-h] = work;
            /* 交換処理の間隔分だけ添字を後退させる */
            j -= h;
        }
    }
}

あー色々ミスったな・・・・。

クソまじめに漸化式から計算したのは大失敗ですね。

一から順に足しこんでいけば良かったんだ。そもそも漸化式使うのはある項の値を一回の計算だけで求めるための式だったので今回のようなプログラムでループ処理できるケースではまったく不必要ですね。

そして肝心の交換処理の部分は無駄が無いですね。

ただこのwhileの部分はforでも書けそうな気はしますね。

とにもかくにもコレを良く読んで勉強したいです。