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

Question

前提

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

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

宜しくお願いします。

実現したいこと

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

発生している問題

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

該当のソースコード

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内)をサイトの通りに書くと正常に動きました。

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/ツールのバージョンなど）

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

Comments

[matukeso]

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

Answer 1

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

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

Comments

[yukatii]

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