C言語のヒープソートで１つ目がソートされない

Question

C言語　ヒープソートについて

ヒープソートをするために以下のようなコードを書きました。

#include<stdio.h>

#define MAX_HEAP 10

int a[MAX_HEAP + 1] = {20, 6, 55, 74, 3, 45, 13, 87, 46, 30};

int n = 10;

void downheap(int from, int to)
{
    int i, j;
    int val;

    val = a[from];

    i = from;
    while(i <= to/2){
        j = i * 2;
        if(j + 1 <= to && a[j] > a[j + 1]){
            j++;
        }

        if(val <= a[j]){
            break;
        }

        a[i] = a[j];
        i = j;
    }
    a[i] = val;
}

void heapsort()
{
    int i;
    int tmp;
    for(i = n/2; i >= 1; i--){
        downheap(i, n);
    }

    for(i = n; i >= 2; i--){
        tmp = a[1];
        a[1] = a[i];
        a[i] = tmp;
        downheap(1, i - 1);
    }
}

int main(void)
{
    //int a[10] = {20, 6, 55, 74, 3, 45, 13, 87, 46, 30};
    int i;

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

    return 0;
}

そして、出力結果は以下のようにいなりました。

20 87 74 55 46 45 30 13 6 3

ここで1つめの２０がソートされないのはなぜでしょうか

Answer 1

範囲 0～n-1 をソートするよう、小手先の修正を試みた:

#include<stdio.h>

void downheap(int* a, int from, int to) {
    int i, j;
    int val;

    val = a[from];

    i = from;
    while (i <= to / 2) {
        j = i * 2;
        if (j + 1 <= to && a[j] > a[j + 1]) {
            j++;
        }

        if (val <= a[j]) {
            break;
        }

        a[i] = a[j];
        i = j;
    }
    a[i] = val;
}

void heapsort(int* a, int n) {
    int i;
    int tmp;
    --a;
    for (i = n / 2; i >= 1; i--) {
        downheap(a, i, n);
    }

    for (i = n; i >= 2; i--) {
        tmp = a[1];
        a[1] = a[i];
        a[i] = tmp;
        downheap(a, 1, i - 1);
    }
}

int main(void) {
    int a[10] = {20, 6, 55, 74, 3, 45, 13, 87, 46, 30};
    int i;

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

    return 0;
}

aをいっこ左にズラしただけですけどねwww

Answer 2

範囲 1〜n をソートしてるからでしょ、0〜n-1 じゃなく。

Answer 3

    downheap(i, n);

このiは１より小さくはなりません。
配列の０番目の要素はソートの対象にはなりません

Comments

[y_waiwai]

まずはデバッグできる環境を揃えましょう
Eclipseや、WindowsならVisualStudioなど。
コードの任意の行で実行を止め、変数の中身を参照できます。
また、そこから１行づつ実行させてコードの流れや変数の変化を見ることができます

そうすれば、アテずっぽでコードを書かなくて済むようになり、
なぜ動かないか他人に聞くようなこともしないで済むようになります

[Fukada]

ご回答ありがとうございます
ではこれは一応ソート成功と言ってもいいのですか？
それともプログラム改良しなければいけないですか？

[Fukada]

すみません２つ目の回答を確認する前に返信してしまいました。
visual studioをインストールしてみることにします

[episteme]

> ではこれは一応ソート成功と言ってもいいのですか？
1～n の範囲についてはソートできてるでしょけど、
Cでは配列は0から始まるので(0～n-1でないと)実用にはちと苦しい...