ヒープソートの仕組みと実現(修正)方法を教えてください

Question

ヒープソートを勉強していて、どうもピンとこず、とりあえず自分で作ってみようと思い立ってみたのですが...なにがいけないのでしょうか。よろしくお願いします。

結果

11 45 24 18 23 12 34

以下ソースコード

#include <stdio.h>

#define N 7

// iの子の値の小さい方を返す
int min(int array[], int i){
    int i1 = 2*i+1, i2 = 2*i+2;
    if(array[i1] > array[i2])
        return i2;
    else
        return i1;
}

// 入れ替え
void swap(int array[], int i, int j){
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

// 反順序性の回復/確保
void pushdown(int array[], int first, int last){
    int i = first;
    while(i <= (last-1)/2){
        int j = min(array, i);  // iの子の値の小さい方
        if(array[j] < array[i]){  // 子 < 親
            swap(array, i, j);  // 親iとjの内容を変換
            i = j;  // さらに子孫を調べる
        } else {
            return;  // 逆転はないので終了
        }
    }
}

// ヒープソート
void heapSort(int array[]){
    int i;
    // 配列arrayをヒープとみなす
    // 反順序性を確立し、arrayを完全なヒープに変換する
    for(i = N/2 -1; i >= 0; i--){
        pushdown(array, i, N-1);
    }
    // ヒープから最小値を順次取り出し、arrayの後ろへ並べていく
    for(i = N-1; i >= 1; i--){
        swap(array, 0, i);  // ヒープの先頭から最小値を取り除く
        pushdown(array, 0, i-1);  // 反順序性を回復する
    }
    // 最終的に大きい順に並んだ配列arrayが得られる
}

// 出力
void showdata(int array[]){
    int i;
    for(i = 0; i < N; i++){
        printf("%d ", array[i]);
    }
    printf("\n");
}

int main(){
    int array[N] = {12, 23, 24, 45, 18, 11, 34};
    heapSort(array);
    showdata(array);
    
    return 0;
}

途中結果

swap(0, 6)
34 18 12 45 23 24 11
pushdown(0, 5)
12 18 34 45 23 24 11
12 18 34 45 23 24 11
12 18 11 45 23 24 34
12 18 11 45 23 24 34

この結果を見た感じ、せっかく最後尾に持って行った11が前array[2]にきている。
pushdownの中で子の小さい方を選んでいるので、親34と子(24, 11)だと11が選ばれswap34<->11されているみたいです…

Answer 1

他の言語に比べC/C++言語の難しいところは、言語仕様の規定に「未定義動作」が多いことだと思います。もっとも厄介な未定義動作の一つに以下があります。

• 不正なアドレス値(ポインター値)を介した間接参照をしたときどうなるか＝＞未定義
• 配列の範囲外をアクセスしたらどうなるか＝＞未定義

上の２つはCにおいては実質的に同じバグです。これをやってしまうと何が起きるか分からないのですが、運が良ければ異常終了してくれます。が、運が悪ければメモリー内のおかしな箇所を破壊しハチャメチャな動作をした挙句正常終了したふりをしたりします。

他の言語ですとプログラマーが一々チェックせずとも言語処理系の方でチェックされるため確実にエラーが起きてくれたりしますが、Cでは余計なチェックを極力省き高速に動作することの方を重視するポリシーで設計されてます。

さて今回質問者さんは運が悪かったようです。自分の環境では運良くSegmentation faultが観察できました。つまり・・・

問題1: このコードはメモリーのおかしな位置を参照しています

本コードでは配列を使っているのでどこかに配列の範囲外をアクセスしている箇所があるはずです。それを見つけてください。発見するには

・コードをよく見る
・チェック論理・デバッグプリントを随所に入れ実行してみる

の二大戦略がありますが経験を積んだプログラマーなら前者で見つけられます。しかし初心者の方には難しいので後者をお勧めします。以下のようにassertを使うとよいと思います。

assertの動作については「C言語 assert」などで調べてみてください。簡単に言うと「成立していなければまずい条件」を明記することができるものです。プログラムを動かしたとき、その条件が成立してないと自動的にどの行で成立しなかったかを印字してプログラムを止めてくれます。

...
#include <assert.h>

...
// iの子の値の小さい方を返す
int min(int array[], int i) {
    assert(i >= 0 && i < N);    // ** iが0以上、N未満でなければ停止。以下同様
    int i1 = 2 * i + 1;
    int i2 = i1 + 1;
    assert(i1 >= 0 && i1 < N);  // **
    assert(i2 >= 0 && i2 < N);  // **
    if (array[i1] > array[i2])
        ...
...

void pushdown(int array[], int first, int last) {
    assert(first >= 0 && last < N && first <= last); // **
    int i = first;
    while (i <= (last-1)/2) {
        int j = min(array, i);
        assert(j >= 0 && j < N);  // **
        assert(j >= 0 && j < N);  // **
        if (array[j] < array[i]) {
            ...

等々

自信があればチェックを入れるところ、入れないところを適宜選ぶとよいですが、そうでなければなるべく丹念に「こうなってないとおかしい」というチェックを入れておくのがよいでしょう。

問題2: 問題1以外にもおかしな点がある

自分はバグの原因を簡単に教わるのは愚策で、自分自身で発見できる方法を知るのが重要と思うので、デバッグしても発見できないでいる状況でないかぎりなるべくデバッグ方法のヒントをアドバイスしたいと思っています。

具体的には問題1で述べた方法(assertによるチェック)に加えデバッグプリントを入れてみるとよいと思います。例えば

・minでi(親の位置)やi1, i2(子供の位置)を印字
・swapでi, j(入れ替え位置)を印字
・swapするたびに結果の配列全体をその都度showdataで表示
・heapSortで前半(反順序性を確立)と後半(最小値を順次取り出す)の区切りを印字
＝＞どこからが後半戦かがわかる

等々です。

質問者さんはかなり注意深くコードを書いておられる印象です。またプログラムの動作を詳しく観察するのに手ごろな複雑さ(配列の大きさがごく小さい※)です。問題1に比べ問題2は少し難しいかもしれませんが、上記のような手段でデバッグするのに非常によい題材だと思うのでぜひデバッグしてみてほしいと感じました。

Comments

[KSwordOfHaste]

なお、デバッグしてみて原因になかなか気づけないときはassertやデバッグプリントを入れたコードとその実行結果、それを見て質問者さんがわかったこと・わからないことなどを質問に書くとよいアドバイスが得られると思います。

[hatomugi_tarou]

ご回答ありがとうございます。
ご助言通りにしてみたところ(問題１)、min関数のreturn値に誤りがあることに気がついたので、修正しました(array[j] -> j, array[i] -> i)。
また、pushdown関数の中で、さらに子孫を調べる行のiとjが逆になっていることにも気がつきました。
しかし、結果としては「11 45 24 18 23 12 34」となりまだ不完全ではありますが、今後も活用できるassertといった知識も教えてくださりありがとうございました。

[KSwordOfHaste]

失礼しました。質問者さんが気づかれたi, jが逆という点を言い忘れてました。自分が述べた問題2は残りの一つのバグのことを言ったいるつもりでした。
も少しヒントを申し上げますとheapsort後半戦で一番最初に配列末尾に移動した最小値11がなぜ末尾にずっととどまってくれないのかに着目してデバッグするとよいと思います。

[hatomugi_tarou]

大変助かりました、ありがとうございます。
KSwordOfHaste様をBAにするつもりだったのですが、teratailの仕様がよく分かっておらず、自分の回答をBAにしてしまいました。大変申し訳ありません。

[hatomugi_tarou]

修正できました。失礼しました。
改めて、ありがとうございました。

[KSwordOfHaste]

自分は「質問者さんご自身で原因を見つけてほしい。見つけられると思う」と考えていました。
「おめでとうございます！」という言葉を贈らせていただきます。

[tacsheaven]

昔のHP-UXのCでメモリがらみのおかしな動作に悩まされた記憶が……
1. 16バイトと宣言しているのにそれ以上のメモリが取られていて、境界越えてもしばらく気づかない
2. malloc(0) とやったときに、null でない（けどアクセスできない）ポインタが帰ってくる
特に2には悩まされました……確かに仕様上、0バイトのメモリを確保できているからnull以外のポインタが帰ってきて、かつそのポインタは0バイトの領域を指しているからアクセスできない、んですが……
※DBからの結果に従って動的に構造体の配列を確保するので、計算式がmallocの引数に書かれていたため、0になることに気づくのが遅れた

Answer 2

min関数の引数にlastを追加、中でi2がlast以上であればi1を返すようにしたら、上手くいきました

int min(int array[], int i, int last){
    int i1, i2;
    i1 = 2*i+1; i2 = 2*i+2;
    //printf("i1 = %d, i2 = %d\n", i1, i2);
    if(array[i1] > array[i2]){
        if(i2 <= last)
            return i2;
        else
            return i1;
    } else{
        return i1;
    }
}

おそらくi1 >= lastになることはないと思いますが...

加えて、heapSort関数の中で、後半のpushdown関数が引数(array, 0, 0)になったとき、(last-1)/2 = (0-1)/2 = -1となると思いきや、0となったので、if(i <= (last-1)/2)が上手く働かなかったため、heapSort関数の中でswap後if(i-1 == 0)で終了にした。最後の一個なので反順序性は保たれている、はず。

void heapSort(int array[]){
    int i;
    for(i = N/2 -1; i >= 0; i--){
        pushdown(array, i, N-1);
    }
    printf("ここから後半戦\n");
    for(i = N-1; i >= 1; i--){
        swap(array, 0, i);
        printf("swap(%d, %d)\n", 0, i);
        if(i-1 == 0) return;
        pushdown(array, 0, i-1);
        printf("pushdown(%d, %d)\n", 0, i-1);
    }
}
``

結果

45 34 24 23 18 12 11

Comments

[KSwordOfHaste]

既にお気づきのように本来heapsortは2のべき乗-1以外の配列に対しても常に正しく動くものなので、サイズが0, 1, 2, ...の任意のサイズで配列領域外をアクセスしたりおかしな結果にならないように配慮することが注意すべきポイントの一つと思います。