前提
Cで https://daeudaeu.com/heap-sort/ のサイトを参考にヒープソートのプログラムを作っています。
アルゴリズムに問題はないと思うのですが、途中の書き方で予期せぬ無限ループに陥ってしまいました。
問題が起きているのは、サイトのrenoveHeap関数のwhileの中です。
※該当のソースコードは全てのコードを貼ると長くなるので、一部分だけ切り取っています。なのでサイトを見ながらの方がわかりやすいかと思います。お手数ですが、
宜しくお願いします。
実現したいこと
発生している問題
デバッグで挙動を見たところ、leftとrightの大小比較が終わったタイミングで必ず、コメント"// 両方存在する"の下の行 if(array[left] > array[right])を経由してからwhileの先頭に戻っていることが確認できました。
問題は実行途中で if(array[left] > array[right]) に飛んでしまい、なぜか無限ループに陥ってしまうことです。(しかもswap関数を呼ぶときに毎回起きるのではなく、あるタイミングで起きる)
該当のソースコード
C
while(1) { left = GetLeft(parent); right = GetRight(parent); // if(leftもrightも存在するか？ (配列長の端に来てるとleftのみor両方ない場合がある) ) if (left < size && right < size) { // 両方存在する if (array[left] > array[right]) { // leftの方がrightより大きい if (array[left] > array[parent]) { // さらにleftがparentより大きい swap(&array[left], &array[parent]); parent = left; } // elseの場合は何もしない } else if (array[right] > array[left]) { // rightの方がleftより大きい if (array[right] > array[parent]) { // さらにrightがparentより大きい swap(&array[right], &array[parent]); parent = right; } } } // leftのみ存在 else if (left <= size) { // leftの方がparentより大きい if (left > parent) { swap(&array[left], &array[parent]); parent = left; } } // 両方ない else { break; }
試したこと
該当箇所(removeHeapのwhile内)をサイトの通りに書くと正常に動きました。
C
while(1){ left = GetLeft(parent); right = GetRight(parent); // if(leftもrightも存在するか？ (配列長の端に来てるとleftのみor両方ない場合がある) ) if (left < length && right < length) { // 両方存在 if (array[left] > array[right]) { // leftの方がrightより大きい large = left; } else { large = right; } } // leftのみ存在 else if (left <= length) { // leftの方がparentより大きい large = left; } // 両方ない else { break; } // leftとrightの大きい方と,parentとの大小比較と入れ替え if (array[large] <= array[parent]) { break;} else { swap(&array[large], &array[parent]); } // 根ノードはデータを交換した子ノードの位置に移動する parent = large;}
補足情報（FW/ツールのバージョンなど）
ここにより詳細な情報を記載してください。
0 コメント