シェルソートのプログラムが分かりません

質問

教科書どおり下のようなプログラムを作ったのですが、ちゃんとソートされません。
打ち間違いなどを探しているのですが見つからないんです・・・
それと、プログラム１１行目のj=j-hが何のためにあるのか分かりません。もしかしたら幼稚な質問かもしれませんがどうかよろしくお願いします。

#include<stdio.h>
void shell(int n,int a[])
{
int i,j,x,h;
h=n/2;
while(h<0)
{
for(i=h;i<=n;i++)
{
x=a[i];
for(j=i-h;j>=0;j=j-h)
{
if(a[j]>x)
{
a[j]=a[j+h];
a[j+h]=x;
}
}
}
h=h/2;
}
}

main()
{
int a[]={30,20,60,29,10,90};
int n=6;
int i;
shell(n,a);
for(i=0;i<n;i++)
{
printf("%4d",a[i]);
}
printf("\n");
}

回答No.4

noname#50176

No.3 です。
＜訂正＞
for(i=h;i<=n;i++)
は、
for(i=h;n-i;i++)
です。

インクリメントですので
for(i=h;i<n;i++) でなくてもいく訳です。

回答No.3

noname#50176

勉強なさっているようなので、
以下も参考になさってみてください。

http://oshiete.nikkeibp.co.jp/qa3323110.html

この No.3 の回答（私ですが…）の例を理解してみてください。
これは寄り道再帰と言う方法を使ったシェルソートです。
初見では分け解からないかもしれませんが、
ゆっくりと辿れば解かると思います。
尚、この寄り道再帰はゲームプログラムで非常に役立つので
参考になさってみて下さい。

回答No.2

noname#50176

以下が正解かと思います。

#include<stdio.h>
void shell(int n,int a[])
{
int i,j,x,h;
h=n/2;
while(h>0)
{
for(i=h;i<=n;i++)
{
for(j=i-h;j>=0;j=j-h)
{
x=a[j];
if(x>a[j+h])
{
a[j]=a[j+h];
a[j+h]=x;
}
}
}
h=h/2;
}
}

≪説明≫
while(h<0)
となっていましたがこれではグループ数に関わらず無条件で
ロジックスルー（目的処理しない）してしまいます。
つまりこの場合グループ数が、
{3>1(3/2=1.5の切捨て)>0(1/2=0.5の切捨て)}
ですから0以上の間、つまり　while(h>0)　です。

x=a[i];
for(j=i-h;j>=0;j=j-h)
{
if(a[j]>x)
{
a[j]=a[j+h];
a[j+h]=x;

これでは要素を比較して入れ替える際に左側要素を壊してしまいます。
x=a[i];　がループ中に常時評価されると必ず　a[i]　が代入される
のでデータが上書きされてしまいます。
したがって

x=a[j];
if(x>a[j+h])
{
a[j]=a[j+h];
a[j+h]=x;

にすることでループ中に評価されたもの同士を入れ替えます。

for(j=i-h;j>=0;j=j-h)　についてですが
例えば流れとして
A,B,C,D,E,F,G,H,I,J の１０個を以下のようにします。
グループ数：5(10/2)※間隔はグループ数-1となる
AとF,BとG,CとH…
このときは各1回でいいのですがグループ数が2になったとき、
AとC,CとE,EとG,GとI のように4回ループします。
この時、j=比較元位置 h=グループ数 ですから
G（位置：7)から、j=j-h で 7-2=5 つまり次の対照の E(位置：5)
が算出できたわけです。

回答No.1

asuncion

> while(h<0)
> {
> for(i=h;i<=n;i++)

ざっと見ただけですけれど、上に引用した３行のうち、
・１行目の不等号の向きは正しいですか？
・３行目の、for文の継続条件に等号は必要ですか？

教科書に書いてあるコードをもう一度確認してみてはいかがでしょうか。