これまで、単純なソートアルゴリズムと、高速なソートアルゴリズムを解説してきた。
具体的には、以下の通りだ。
リンクも貼っておいたので、よかったら見てみて欲しい。
今回は、これらの分類に該当しないソートを解説していこう。
その名を、シェルソートと呼ぶ。
スピードは、この二つの中間くらい。
その計算量ももちろん見ていく。
今回のソートは結構簡単！
是非自分で組んでみて！
シェルソート
シェルソートは、簡単に言ってしまうと挿入ソートの改良版だ。
改めてになるが、挿入ソートの内容は以下で解説しているので、心配な方は確認しておこう。
単純なソートアルゴリズム「挿入ソート」を解説！ | 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 |
同じ色の数字をソートしている。
次に、2-ソートということで、今度は奇数内、偶数内でソートを行う。
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| data[i] | 1 | 3 | 2 | 5 | 4 | 7 | 6 | 8 |
この時点で、なんとなくだが小さい順っぽくなっているのが分かるだろうか。
で、最後に1-ソート…通常の挿入ソートを行う。
というわけで、最終的な結果は以下の通りだ。
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| data[i] | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
基本的に、やっていることは挿入ソートの繰り返しだ。
そこまで難しくないと思う。
シェルソートの計算量
一番気になるのはここだ。
挿入ソートの改良とはいっても、最後に普通の挿入ソートをしていて、なおかつ前処理で何度もソートを行う。
だから、一見計算量は増えてしまいそうな感じがする。
しかし、実際の計算量は\(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;
}
}
}おわりに
今回は、シェルソートの解説を行った。
ちょっと特殊な立ち位置にいるやつだが、単純なソートアルゴリズム並みに分かりやすく、しかもちょっと速い。
ただ、安定ではなくなっていることには注意しよう。
とはいえ、そこに気を使わなくてもいいなら、単純なソートアルゴリズムをそのまま使うメリットは薄い。
できれば、こちらや高速なソートアルゴリズムを使うようにしていこう。
最後のオマケだが、シェルソートの名前は、発表者の名前から来ているらしい。
コメント