heapsortについて問題

質問

以下の問題はある国立大学の大学院入試過去問題です
空欄を埋めて、プログラムを完成させなさい。
よろしくお願い致します

以下はheapを建てるための方法
void in(int dt,int*val)
{
int i;
val[0]++;
for(i=val[0];i>1&&dt<val[i/2];i=i/2)
val[i]=val[i/2];
val[i]=dt;
}

以下はsort方法だ
int dl(int *val){
int i=1,j,ret= 空欄 ;←自分の考えはval[i]です
while(i<=val[0]/2){
j=2*i;
if(j+1<val[0]&& 空欄 <　空欄 )←自分の考えはval[j+1]<val[j]
j++;
if(val[val[0]]<val[j])
break;
val[i]=val[j];
i=j;
}
val[i]=空欄;←自分の考えはval[i]=nullです、でも納得できない
val[0]--;
return ret;
}

void hs(int sz,int d[])
{
int i,*val;
val = malloc(sizeof(int)*(sz+1));
val[0]=0;
for(i=0;i<sz;i++)
in(d[i],val);
for(i=0;i<sz;i++)
d[i]=dl(val);

}

orzorzorzorzorz

回答No.3

Yanch

> あ。。。分かった、
> この空欄がval[val[0]]だ。
> でもこういうheapsortは確かに分かりにくいです
正解。
おめでとうございます。

回答No.2

Yanch

トレースでどこまでわかっていますか？

わかっている事実を書いてくれるとアドバイスを貰いやすいかもしれません。

> szが｛2,0,3,1｝だったとすると、
この一文は、意味不明ですが、タイプミスであると想像してみます。

hs(sz, d) 関数を呼び出すのにしようするデータが、
sz に 4、d に {2,0,3,1}と言う事だろうと思って読んでみます。

> 建てされたheapは
> val[0]=4,
> val[1]=0;
> val[2]=1,
> val[3]=3,
> val[4]=2
> です
> そうすると、0，1を脱出した後は、
この0, 1を脱出した後って、言うのは、valの添え字の事ですか？それとも、内容の事ですか？

手前でのトレース情報一部を書いてみます。
hs(sz, d)に、sz に 4 を, d に {2,0,3,1} を指定した場合、

建てられた heap 、
val は｛4, 0, 1, 3, 2｝ですね。
そして、
dl(val)を脱出するごとに、
val は {3, 1, 2, 3}
val は {2, 2, 3}
val は {1, 3}
val は {0}

となってます。

お礼

あ。。。分かった、俺が馬鹿になったぞ。。
この空欄がval[val[0]]だ。
でもこういうheapsortは確かに分かりにくいです

補足

また対応して有難うございます。
脱出順番はもちろん以下です
val は {3, 1, 2, 3}
val は {2, 2, 3}
val は {1, 3}
val は {0}
しかし、val[i]=空欄、
空欄っていうところに何を埋めたほうがいいか是非教えていただきたいです

回答No.1

Yanch

ヒープソートのコーディングは、もっとわかりやすい書き方があると思いますが、
これは穴埋めが目的の課題みたいなので、わざとわかりにくくしているのでしょう。

> int i=1,j,ret= 空欄 ;←自分の考えはval[i]です
これは、正解。
int i=1,j,ret= val[1] ;でも良いと思います。

> if(j+1<val[0]&& 空欄 <　空欄 )←自分の考えはval[j+1]<val[j]
これは、正解。

> val[i]=空欄;←自分の考えはval[i]=nullです、でも納得できない
これは、間違い。
データのトレースをすれば、なにを書くべきかあきらかになると思いますよ。

補足

早速ご対応ありがとうございます、
でも何度も繰り返しトレースをしてみると、
何を書くべきかわからないです、
何卒教えてください。
ちなみに俺の迷いところは以下です

szが｛2,0,3,1｝だったとすると、
建てされたheapは
val[0]=4,
val[1]=0;
val[2]=1,
val[3]=3,
val[4]=2
です
そうすると、0，1を脱出した後は、
残り分はval[1]=2;val[3]=3,
こうなると、どうすればいいですか