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

Question

###実現したいこと
ヒープソートで配列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;
}

Answer 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 は要らないということです。

Comments

[langhtorn]

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

Answer 2

        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]が親よりも小さい場合を考慮していない事が気になります。

Comments

[langhtorn]

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