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

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

ただいまの
回答率

88.04%

ヒープソートでうまくソートできていないときがある

解決済

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 512

score 87

実現したいこと

ヒープソートで配列aを小さい順に並べたい。

問題点

できたとき。

n=7
34 12 54 23 72 345 100

12 23 34 54 72 100 345


できないとき。

n=10
2 6 3 213 12 543 84 23 15 100

2 3 6 12 15 23 84 213 100 543


213より100が大きいことになってしまいます。
途中経過を出力したりしてみましたが原因がわかりません。
どうしてこのようになるのか教えてください。

コード

//ヒープソート
#include<stdio.h>

//aとbの値を交換する関数
void swap(int *a,int *b)
{
    int tmp;
    tmp=*b;
    *b=*a;
    *a=tmp;
}

//ヒープソート
void heap_sort(int a[],int n)
{
    int i,j,k,h[n],w;

    h[0]=a[0];
    for(k=1;k<n;k++){
        i=k;
        h[i]=a[i]; //新しいデータを一番下段・左から詰めた最後にi●仮置きします
        j=(i-1)/2;
        while (1){
            if(h[j]>h[i]){ //親jのデータが子iのデータよりも大きければ
                swap(&h[j],&h[i]); //二つのデータを交換します
                i=j; //ヒープ条件を調べる子をj
                j=(i-1)/2; //親をjの親のように更新します
            }else{
                break;
            }
        }
    }
    /*
    printf("ソ\ート前 ");
    for(i=0;i<n;i++){
        printf("%d ",h[i]);
    }
    printf("\n");
    */
    //ソートする
    i=1,j=0;
    int num=n; //配列hのデータ数
    for(k=0;k<n;k++){
        i=1,j=0;
        a[k]=h[0]; //取り除いて別に用意するソート列の最初に置きます.
        h[0]=h[num-1]; //ヒープの空いた場所に,ヒープの一番最後のデータを移動します●
        num--; //ヒープのデータ数を1減らします
        //printf("ソ\ート中 ");
        /*
        for(w=0;w<num;w++){
            printf("%d ",h[w]);
        }
        */

        while(i<num){
            //printf("j=%d i=%d\n",j,i);
            //printf("while中 \n");
            /*
            for(w=0;w<num;w++){
            printf("%d ",h[w]);
            }
            */

            if(h[j]>h[i]){ //親が子よりも大きい場合
                if(h[2*j+1]<h[2*(j+1)]){ //子の中で小さい方と交換すること
                //printf("h[2*j+1]=%d\n",h[2*j+1]);
                    swap(&h[2*j+1],&h[j]);
                    j=i;
                    i=2*(j+1); //下の段へ
                }else{
                //printf("h[2*(j+1)]=%d\n",h[2*(j+1)]);
                    swap(&h[2*(j+1)],&h[j]);
                    j=i;
                    i=2*(j+1);
                }
            }else{
                //printf("while出る\n");
                break;
            }
        }


    }

}


int main(void)
{
    int i,n,a[10];
    printf("n=");
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    heap_sort(a,n);

    printf("\n");
    for(i=0;i<n;i++){
        printf("%d ",a[i]);
    }

    return 0;
}
  • 気になる質問をクリップする

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

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

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

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+1

質問のコードがよく分からないので、全部書き直してみました。

#include <stdio.h>

#define swap(x, y) (c = x, x = y, y = c)

void heap_sort(int a[], int n)
{
    int c, i, j, k = 0;
    while (++k < n)
        for (j = k; j > 0 && a[i = (j-1)/2] < a[j]; j = i)
            swap(a[i], a[j]);
    while (--k > 0) {
        swap(a[0], a[k]);
        for (i = j = 0; ; j = i) {
            c = (j + 1) * 2;             // c: right child of j
            if (c > k) break;
            if (a[c-1] > a[i]) i = c-1;  // c-1: left child of j
            if (c < k && a[c] > a[i]) i = c;
            if (i == j) break;
            swap(a[i], a[j]);
        }
    }
}

int main(void)
{
    int i,n,a[10];
    printf("n=");
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    heap_sort(a,n);

    for(i=0;i<n;i++){
        printf("%d ",a[i]);
    }
    printf("\n");

    return 0;
}


追記
元のコードの while だけを次のように修正すればよいでしょう。

-        while(i<num){
-            //printf("j=%d i=%d\n",j,i);
-            //printf("while中 \n");
-            /*
-            for(w=0;w<num;w++){
-            printf("%d ",h[w]);
-            }
-            */
-
-            if(h[j]>h[i]){ //親が子よりも大きい場合
-                if(h[2*j+1]<h[2*(j+1)]){ //子の中で小さい方と交換すること
-                //printf("h[2*j+1]=%d\n",h[2*j+1]);
-                    swap(&h[2*j+1],&h[j]);
-                    j=i;
-                    i=2*(j+1); //下の段へ
-                }else{
-                //printf("h[2*(j+1)]=%d\n",h[2*(j+1)]);
-                    swap(&h[2*(j+1)],&h[j]);
-                    j=i;
-                    i=2*(j+1);
-                }
-            }else{
-                //printf("while出る\n");
-                break;
-            }
-        }

+        i = j = 0;  // j は親、i は親子のうち小さいもの
+        while (2*j+1 < num) {  // 子がヒープの範囲内     
+            if (h[2*j+1] < h[j]) i = 2*j+1;  // 左の子が親より小さい
+            if (2*(j+1) < num && h[2*(j+1)] < h[i]) i = 2*(j+1);
+                                             // 右の子が最も小さい
+            if (i == j) break;   // 親が子より小さい
+            swap(&h[i], &h[j]);  // 小さいほうの子を親と交換
+            j = i;               // 子を新しい親とする
+        }


heap_sort関数の中で、int h[n]; を宣言していますが、
これは可変長配列で、コンパイラによってはこの機能をサポートしていません。

質問のコードでは、h[0] が最小値になるヒープを構成し、h[0] を a[0] にコピー。
h[0] に h[n-1] をコピーし、長さが 1小さくなったヒープを再構成し、
新しい最小値 h[0] を a[1] にコピー。
これを繰り返して、ソート結果を配列 a に入れています。

次のようにしてもソートはできます。

h[0] が「最大値」になるヒープを構成し、h[0] を a[n-1] にコピー。
h[0] に h[n-1] をコピーし、長さが 1小さくなったヒープを再構成し、
新しい「最大値」 h[0] を a[n-2] にコピー。
これを繰り返して、ソート結果が配列 a に入る。

こうすると、ヒープが小さくなるたびに最大値を後ろに置くことができます。
すなわち、元の配列 a をそのままソートでき、配列 h は要らないということです。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

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

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

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/11/12 22:20

    丁寧な説明をありがとうございます。おかげでよくわかりました。

    キャンセル

+1

            if(h[j]>h[i]){ //親が子よりも大きい場合
                if(h[2*j+1]<h[2*(j+1)]){ //子の中で小さい方と交換すること

子は2つあるのに親が子よりも大きい場合がif(h[j]>h[i])のみで判定はできません。

また、2*(j+1) < numかつh[2*j+1]が親よりも小さい場合を考慮していない事が気になります。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

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

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

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/11/12 22:20

    なぜできなかったのか理由がわかりました。ありがとうございます。

    キャンセル

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

  • ただいまの回答率 88.04%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

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