どうも〜 シュモクザメです。
今回はシェルソートを実装していきたいと思います。
全体のコードは一番下に貼ってあるので是非参考にしてください！！
またこちらでクイックソートを解説しているのでそちらもよければ是非
シェルソートのアルゴリズム解説
まずはアルゴリズムの確認からです。
配列x[]をソートするとして、まずそれをh1個のグループに分割します。
どういうことかというと
こんな感じで
h1飛ばしで配列をグループ分けします。（同じ色は同じグループ）
次にそのグループごとにソートを行います。
上の例だと、
こんなかんじでソートして、最終的に全てのグループでソートを完了させます。
次はh1>h2となるh2で同じように配列をグループに分割してソートしていきます。
このようにh1>h2>h3>….となるような数列h={h1,h2,h3….}でこの手順を繰り返していき、
最終的にhn=1でグループ分け（つまりグループ分けせずに普通に全体をソートする）まで行けば全体のソート完了です。
分割してソートをしていくことで、最後の全体ソートの際の入れ替えが少なくなって最終的な計算量の削減が見込めるってことね。
分割数列hの決め方
先ほど説明したhですが、
その数列h、つまり分割の仕方によって全体のソートの計算量が変わってきます。
計算量が少なくなるhとしては
が主に挙げられます。
今回はO(n^1.25)の３倍して1を加える数列を用いてソートしていきます。
ここがなぜ計算量が小さくなるかについては触れないので気になる方は各自調べてくださいorz
コードの実装
とりあえずシェルソートのコードをみてみましょう。
void shell(int x[]){
int h, i, j, k;
for(h=1; h<(N/9); h=h*3+1);
while(h>0){
for(i=h; i<N; i++){
j=i;
while(j>=h && x[j-h]>x[j]){
k=x[j];
x[j]=x[j-h];
x[j-h]=k;
j=j-h;
}
}
h = (h-1)/3;
}
}うーん、わからんw!
短いですけど変数とか入り子のfor,whileが多くてややこしいですよね。
一個ずつ紐解いていきましょう。
分割数の最大値を決定
最初の入り子になっていないforでは分割数の最大値を決定してます
for(h=1; h<(N/9); h=h*3+1);あれ？ だったらなんでfor文の第二引数が、
h < Nじゃなくて、
h < (N/9)になってるん？
普通に考えたらそこはh < Nですよね。
ただ最初の方に細かく分割しても全体のソートにあまり良い影響がないらしいです。
なので大胆に配列の長さを9で割った数値以内の最大値となるhを決定してます。
数列に基づいてhを変化させていくwhile
次は入り子になっている部分の一番外側のwhileです。
while(h>0){
/////
/////
h = (h-1)/3;
}ここではまず継続条件をh > 0としてます。
そしてこのwhileの最後で h=(h-1)/3とすることでhを数列上で一つ小さい値に変更してます。
例としてh=121からの時は
h=(121-1)/3=40
h=(40-1)/3=13
h=(13-1)/3=4
h=(4-1)/3=1 と変更されていき、
継続条件と合わせてh=1の時が最後の処理となります
グループ分けと並び替え
中に入っているforとwhileの部分です。
for(i=h; i<N; i++){
j=i;
while(j>=h && x[j-h]>x[j]){
k=x[j];
x[j]=x[j-h];
x[j-h]=k;
j=j-h;
}
}まず外側のforですがここはソートするグループを変更していく役割のある部分で、
whileはグループ内で比較してソートしていく役割があります。
うーん、わからんw！
すこし具体的に考えていきます。
配列の長さN=8 として h = 4 だったとしましょう。
まずfor文でi=hなので
次のj=iでj=h=4が代入されます。
そしてwhile文に入っていきます。
ここでの処理はこんな感じです
j>=hかつx[j-h]>x[j]ならx[j-h]とx[j]を入れ替えてjの値をhだけ小さくする、
これは簡単にいうとグループ内でソートを行なっているんですね。
上の画像だとj-h=0なので、そこからさらにhを引くと当然whileの継続条件j>=hが達成できないのでループが終わります。
するとfor文が一個進んでj=h+1=5となります。
この時の処理は
こんな感じで先ほどの処理を一個隣のグループで行なってますね。
同じようにfor文をもう一個進めてj=h+3=7とした時も
こうなります。
この次もfor文を増加して同様の処理をするのですが、
今回はこれまでと少し違いますよね。
j=h+4=8となるので
今回考えるグループは添字[0],[4],[8]となります。
仮に[3]>[6]なら、まず[3]と[6]を入れ替える。
その後 j =j – 3=3 の処理を入れた後もう一度whileに戻り、このときはj=3>=hをクリアできるので[6]と[0]をソートするかどうかの判定が始まります。(while文はこの判定で終了)
しかし[4]<[8]のときはwhile文の条件(x[j-h]>x[j])が達成できないので[0]と[8]の大小関係を調べることなく終わってしまいますが、
最初のソートで[0]<[4]は確定しているので、[0]<[4]<[8]となるので調べる必要がありませんのでOKです。
これなら無駄な計算が発生しないね
この要領でfor文のiがN-1まで行けばこのhの時のソートは終了です。
これを先ほど説明した一番外側のwhileでhが1になるまで繰り返せば全体のソート完了です！！
実際に使ってみた
はい、大丈夫そうですね。
いや〜シェルソートはアルゴリズム自体は理解しやすいですけどコードを書くとなると急に難しくなりますよね。
今回の記事も書くのが大変でした。
これもよく大学の課題などで出ると思うので是非参考にしてください！！
ではまた〜
全体のコード
#include <stdio.h>
#define N 20
void show(int x[]){
for(int i=0; i<N; i++){
printf("%d ",x[i]);
}
printf("\nxxxxxxxxxxx\n");
}
void shell(int x[]){
int h, i, j, k;
for(h=1; h<(N/9); h=h*3+1);
while(h>0){
for(i=h; i<N; i++){
j=i;
while(j>=h && x[j-h]>x[j]){
k=x[j];
x[j]=x[j-h];
x[j-h]=k;
j=j-h;
}
}
h = (h-1)/3;
}
}
int main(int argc, const char * argv[]) {
int x[N]={1,5,3,4,7,9,8,6,0,2,3,4,8,5,0,9,7,1,4,5};
show(x);
shell(x);
show(x);
return 0;
}
コメント