質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
86.02%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

解決済

C言語 if文の書き方で無限ループに陥ってしまう

yukatii
yukatii

総合スコア4

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

1回答

0グッド

0クリップ

328閲覧

投稿2022/11/26 09:01

前提

Cで https://daeudaeu.com/heap-sort/ のサイトを参考にヒープソートのプログラムを作っています。
アルゴリズムに問題はないと思うのですが、途中の書き方で予期せぬ無限ループに陥ってしまいました。
問題が起きているのは、サイトのrenoveHeap関数のwhileの中です。

※該当のソースコードは全てのコードを貼ると長くなるので、一部分だけ切り取っています。なのでサイトを見ながらの方がわかりやすいかと思います。お手数ですが、

宜しくお願いします。

実現したいこと

  • なぜこのような動作になるのかが知りたい

発生している問題

デバッグで挙動を見たところ、leftとrightの大小比較が終わったタイミングで必ず、コメント"// 両方存在する"の下の行 if(array[left] > array[right])を経由してからwhileの先頭に戻っていることが確認できました。
問題は実行途中で if(array[left] > array[right]) に飛んでしまい、なぜか無限ループに陥ってしまうことです。(しかもswap関数を呼ぶときに毎回起きるのではなく、あるタイミングで起きる)

該当のソースコード

C

1while(1) { 2 left = GetLeft(parent); 3 right = GetRight(parent); 4 5 // if(leftもrightも存在するか? (配列長の端に来てるとleftのみor両方ない場合がある) ) 6 if (left < size && right < size) { 7 // 両方存在する 8 if (array[left] > array[right]) { // leftの方がrightより大きい 9 if (array[left] > array[parent]) { // さらにleftがparentより大きい 10 swap(&array[left], &array[parent]); 11 parent = left; 12 } 13 // elseの場合は何もしない 14 } 15 else if (array[right] > array[left]) { // rightの方がleftより大きい 16 if (array[right] > array[parent]) { // さらにrightがparentより大きい 17 swap(&array[right], &array[parent]); 18 parent = right; 19 } 20 } 21 } 22 23 // leftのみ存在 24 else if (left <= size) { // leftの方がparentより大きい 25 if (left > parent) { 26 swap(&array[left], &array[parent]); 27 parent = left; 28 } 29 } 30 31 // 両方ない 32 else { break; }

試したこと

該当箇所(removeHeapのwhile内)をサイトの通りに書くと正常に動きました。

C

1while(1){ 2 left = GetLeft(parent); 3 right = GetRight(parent); 4 5 // if(leftもrightも存在するか? (配列長の端に来てるとleftのみor両方ない場合がある) ) 6 if (left < length && right < length) { 7 // 両方存在 8 if (array[left] > array[right]) { // leftの方がrightより大きい 9 large = left; 10 } 11 else { large = right; } 12 } 13 // leftのみ存在 14 else if (left <= length) { // leftの方がparentより大きい 15 large = left; 16 } 17 // 両方ない 18 else { break; } 19 20 // leftとrightの大きい方と,parentとの大小比較と入れ替え 21 if (array[large] <= array[parent]) { break;} 22 else { swap(&array[large], &array[parent]); } 23 24 // 根ノードはデータを交換した子ノードの位置に移動する 25 parent = large; 26}

補足情報(FW/ツールのバージョンなど)

ここにより詳細な情報を記載してください。

以下のような質問にはグッドを送りましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

グッドが多くついた質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

matukeso

2022/11/26 09:34

ぱっと見left==rightの時の動作が上下で全然違うみたいだけど、、

回答1

0

ベストアンサー

サイトのコードにあるif (array[large] <= array[parent]) { break;}に相当する処理が行われていないのが原因です。

array[left] > array[parent]がfalseの場合、つまりarray[left] <= array[parent]の場合はbreak;で抜けなければならないのに、// elseの場合は何もしないとコメントにあるように抜けずにそのままループを続けるので、parentが更新されないままループの先頭に戻り、同じ処理を永遠に続けることになります。

投稿2022/11/26 09:40

編集2022/11/26 09:48
actorbug

総合スコア1769

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

回答へのコメント

yukatii

2022/11/27 07:31

おかげさまで挙動を理解することができました。ありがとうございました!

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
86.02%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。