シェルソートとは？計算量は？徹底解説！

これまで、単純なソートアルゴリズムと、高速なソートアルゴリズムを解説してきた。

具体的には、以下の通りだ。

リンクも貼っておいたので、よかったら見てみて欲しい。

単純なソートアルゴリズム
高速なソートアルゴリズム

今回は、これらの分類に該当しないソートを解説していこう。

その名を、シェルソートと呼ぶ。

スピードは、この二つの中間くらい。

その計算量ももちろん見ていく。

シノ

今回のソートは結構簡単！

是非自分で組んでみて！

シェルソート
シェルソートの計算量
シェルソートのサンプルプログラム
おわりに

シェルソート

シェルソートは、簡単に言ってしまうと挿入ソートの改良版だ。

改めてになるが、挿入ソートの内容は以下で解説しているので、心配な方は確認しておこう。

単純なソートアルゴリズム「挿入ソート」を解説！ | Shino’s Mind Archive

ここで、いきなりだがちょっと本筋からそれて、挿入ソートの得意・不得意についてちょっと解説をしておこう。

挿入ソートが得意なものは、交換回数が少なくなるもの…ということで、元々整列済み、あるいはそれに近いデータのソートが得意だ。

逆に、ランダムにばらけているようなデータのソートが苦手となる。

ということは、だ。

先に前処理として大雑把に並び替えておいて、その後挿入ソートをすれば速くなるのではないか、という発想になる。

これをやっているのが、シェルソートなのだ。

というわけで、ここからシェルソートの説明を。

シェルソートでは、複数回挿入ソートを行う。

ただ、その複数回がちょっと独特だ。

まず、データを飛び飛びに挿入ソートを行う。

例えば、data[0]、data[4]、data[8]でソートをし、data[1]、data[5]、data[9]でソートをし…というイメージ。

こうすることで、4つ離れた要素の中ではソートが完了する。

このように、4つ置きの挿入ソートを4-ソートと呼ぼう。

同じように、n個置きの挿入ソートをn-ソートと呼ばせてもらう。

次に、このデータを2-ソートする。

今度は2つ置きなので、奇数内と偶数内で挿入ソートを行う。

そして、最後に1-ソート…これは、通常の挿入ソートだ。

ここまでで、奇数、偶数内のデータは並び替えが完了しているので、元々ある程度は整列済みに近い形になっている。

だから、交換回数が少なく済むというわけだ。

これが終わったら、通常の挿入ソートが終わりなので、当然ソート完了となる。

では、具体例を出してみよう。

以下のデータを整列するとする。

i	0	1	2	3	4	5	6	7
data[i]	6	5	1	3	2	7	4	8

ソートする配列

では、上の説明例と同じように4-ソート、2-ソート、1-ソートで見てみよう。

まず、4ソート…4つ置きのデータでソートを行う。

結果は、以下の通りだ。

i	0	1	2	3	4	5	6	7
data[i]	2	5	1	3	6	7	4	8

4-ソート結果

同じ色の数字をソートしている。

次に、2-ソートということで、今度は奇数内、偶数内でソートを行う。

i	0	1	2	3	4	5	6	7
data[i]	1	3	2	5	4	7	6	8

2-ソート結果

この時点で、なんとなくだが小さい順っぽくなっているのが分かるだろうか。

で、最後に1-ソート…通常の挿入ソートを行う。

というわけで、最終的な結果は以下の通りだ。

i	0	1	2	3	4	5	6	7
data[i]	1	2	3	4	5	6	7	8

1-ソート結果=最終結果

基本的に、やっていることは挿入ソートの繰り返しだ。

そこまで難しくないと思う。

シェルソートの計算量

一番気になるのはここだ。

挿入ソートの改良とはいっても、最後に普通の挿入ソートをしていて、なおかつ前処理で何度もソートを行う。

だから、一見計算量は増えてしまいそうな感じがする。

しかし、実際の計算量は\(O(n^{1.25})\)から\(O(n^{1.5})\)程度に収まるそうだ。

やはり、得意を活かしたソートなので、それなりに効果がある。

ちなみに、どんなn-ソートを事前にすればいいかという問題もあるのだが、これは以下が良く使われる。

…, 121, 40, 13, 4, 1
…, 31, 15, 7, 3, 1

1つ目は、後ろから見ると3倍して1足すという操作で1個前の数が得られる。

2つ目は、後ろからn番目の数を\(2^n – 1\)としている。

基本的には、これらを使っていくことが多いようだ。

また、あまりに幅が広すぎるソートもあまり意味がないので、このnの数は大きくてもデータ数の1/9程度までとしておこう。

例えば、1000個のデータを並び替えるときに、一つ目の並びを使うとすると、121は大きすぎるのでパス、という感じだ。

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

最後に、サンプルプログラムを提示しよう。

数字の並びは3倍して1足すことで得られる数列としよう。

function ShellSort(data){
    let n = data.length;
    let h = 0;

    for(h = 1; h < Math.floor(n / 9); h = h * 3 + 1){

    }
    
    for(; h > 0; h = Math.floor(h / 3)){
        for(let i = h; i < n; i++){
            let j = i;
            while(j >= h && data[j - h] > data[j]){
                let tmp = data[j];
                data[j] = data[j - h];
                data[j - h] = tmp;
                j = j - h;
            }
        }
    }
}

まず、5行目のfor文でn-ソートのnで最も大きい数値を求めている。

その後、9行目のforで順番にn-ソートを行っている。

中の挿入ソートの部分については、挿入ソートのプログラムを見比べてみれば分かると思う。

参考までに、今回の書き方に合わせた挿入ソートのサンプルも出しておこう。

function InsertionSort(data){
    let n = data.length;

    for(let i = 1; i < n; i++){
        let j = i;
        while(j >= 1 && data[j - 1] > data[j]){
            let tmp = data[j];
            data[j] = data[j - 1];
            data[j - 1] = tmp;
            j = j - 1;
        }
    }
}