ヒープソートについて

[P387]

閲覧ありがとうございます。
大学の課題で分からなかったので質問させていただきました。
初心者なので、説明が分かりにくい部分があると思いますがよろしくお願いします。


[問題]

134431.jpg (59.59 KiB) 閲覧数: 10900 回

[プログラム]
大域:整数型の配列:H
大域:整数型:n

〇appendNode(整数型:num)
整数型:i,j,tmp
i←n+1
H[ i ]←num
j←i ÷ 2
while ((jが1以上)and(H[ i ]がH[ j ]より大きい))
tmp ← H[ i ]
H[ i ]← H[ j ]
H[ j ]=tmp
i ←j
j←i÷2
endwhile
n←n + 1

[先生からのヒント]
こんな感じで書いて、と言われたものになります。

添付ファイル 134431.jpg がありません

自分でもヒントや、他のサイトを元にプログラムを書いてみたのですが上手く実行出来ず悩んでいます。
分かる方がいましたらご教授いただけるとと幸いです。

[P387]

画像の添付がうまくいっておらず、分かりにくくなってしまい申し訳ございません。
問題は、図が書いてある方で、ヒントは手書きの文字の方です。
逆になってしまって見にくいですがよろしくお願いいたします。

[みけCAT]

大学の課題で分からなかったので質問させていただきました。

これだけでは何が分からないのか (少なくとも自分には) わかりません。

自分でもヒントや、他のサイトを元にプログラムを書いてみたのですが上手く実行出来ず悩んでいます。

そのプログラムを提示していただけますか？
ソースコードを提示する際は、BBCodeが有効な(無効にしない)状態で、
BBCodeのcodeタグの開始タグと終了タグの組(開始タグが先)で囲んでいただけると、
見やすくてありがたいです。

[P387]

みけCAT様

ご回答ありがとうございます。
ただ[先生のヒント]と[プログラム]のものを使っただけのもですが、こちらが自分が書いたものです。

コード:

#include <stdio.h>
void appendNode(int);

int h[10]={0,12,23,34,45,56,67,-1,-1,-1};
int n=6;

main()
{
	int i,x;
	
	for(i=0;i<=2;i++){
        printf();
		scanf("%d",&x);
		appendNode(x);
	}
	for(i=0;i<=9;i++){
	printf("%d",h[i]);
		printf("\n");
}
void appendNode(int num);
{
	int i,j,tmp;
	
	i=n+1;
	h[i]=num;
	j=i/2;
	while(j>=1 && h[i]>h[j]){
		tmp=h[i];
		h[i]=h[j];
		h[j]=tmp;
		i=j;
		j=i/2;
	}
	n=n+1;
  }
}

これを実行すると、エラーで「未定義のシンボル num(関数 main() )」と出ます。
先生のヒントの最初の3回ループの意味や、何も書かれていないprintfの意味も分からずとりあえず書いた...といった感じです。
私自身が先生のヒントを理解出来ていないことや、初心者であるため意味が分からないプログラムを書いていると思いますがご教授いただければ幸いです。

[みけCAT]

とりあえず実行できるようにしてみました。

コード:

#include <stdio.h>
void appendNode(int);

int h[10]={0,12,23,34,45,56,67,-1,-1,-1};
int n=6;

/* main関数の戻り値intと引数voidを明示する */
int
main(void)
{
	int i,x;
	
	for(i=0;i<=2;i++){
		/* printfの引数を入れる (空文字列だと警告が出た) */
		printf("%s", "");
		scanf("%d",&x);
		appendNode(x);
	}
	/* H[1]～H[9]を表示したいので、0からではなく1から始める */
	for(i=1;i<=9;i++){
		printf("%d",h[i]);
		printf("\n");
	/* 抜けていた閉じカッコを加える */
	}
}
/* 余計なセミコロンを消す */
void appendNode(int num)
{
	int i,j,tmp;
	
	i=n+1;
	h[i]=num;
	j=i/2;
	while(j>=1 && h[i]>h[j]){
		tmp=h[i];
		h[i]=h[j];
		h[j]=tmp;
		i=j;
		j=i/2;
	}
	n=n+1;
/* 余計な閉じカッコを消す */
}

3回ループというのは、H の後半の未使用要素に入力をそれぞれ読み込みたい、ということだと思います。
何も書かれていないprintfは謎ですね。消していいかもしれません。

そもそも、H[1]～H[9]の9個を表示しているはずなのに、実行結果に6個しか要素が無い、というのもおかしい気がします。
(例えば、未使用要素は表示せず、全て未使用要素を表す -1 を入力として与えるなら辻褄は合うが…)

さらに、提示されたプログラム中の h は親ノードの値が子ノードの値よりも小さいヒープになっているにもかかわらず、
親ノードの値が子ノードの値よりも大きいヒープに値を追加する手続きである appendNode を使っているため、結果がおかしくなるかもしれません。
(ちなみに、手書きの文字の H は、11→41→25 という親子関係があるので、ヒープではありません)

ちなみに、通常のヒープソートでは、ソートを行う要素をヒープに入れた後、ヒープから要素を順に取り出すことによるソートを行います。
それに対し、ここで扱っているプログラムには、ヒープから要素を取り出す処理が無いようです。
(それは後々加えるのかな？)
ヒープソート - Wikipedia

[P387]

みけCAT様

ご返信ありがとうございます。

なるほど、3回ループの意味はそういう事だったのですか...解説して頂きありがとうございます。
printfはやはりよく分からないですね。

みけCAT様のコードを書かせていただき、エラーは出なくなりました!
コードにも何を行っているか詳しく書いてくださり分かりやすかったです！

ちなみに、通常のヒープソートでは、ソートを行う要素をヒープに入れた後、ヒープから要素を順に取り出すことによるソートを行います。
それに対し、ここで扱っているプログラムには、ヒープから要素を取り出す処理が無いようです。

今、実行結果が何も出ないのはヒープから要素を取り出す処理が無いからであり、その処理を付け加える必要があるということですかね？

[みけCAT]

今、実行結果が何も出ないのはヒープから要素を取り出す処理が無いからであり、その処理を付け加える必要があるということですかね？

P387 様の #4 のプログラムは、コンパイルエラーになるため、実行結果は出ません。
自分が修正した #5 のプログラムは、実行結果が出るので、この質問の前提を満たしません。
よって、この質問の答えは「いいえ」(実行結果が出ないのはコンパイルエラーになるためであり、ヒープから要素を取り出す処理が無いからではない) となるでしょう。
別のプログラムについての質問であれば、そのプログラムを提示してください。

[P387]

みけCAT様

ご回答ありがとうございます。
みけCAT様が修正していただいたプログラムをそのままコピーさせていただいたのですが、やはり私の方だと実行結果が何も出ないみたいです...。

原因を探ってみたいと思います。
ここまで長々とお付き合いいただきありがとうございました！

[dic]

また立て逃げや
答えんでよかった

[P387]

みけCAT様

今更ではございますが、実行出来ました！

書き込んでいた場所が変だったようで、新規で作り直し、写したらきちんと課題通りにすることが出来ました。

お騒がせして申し訳ございませんでした。
改めて感謝申し上げます。