C言語で書いてみました

■ ヒープソート（平成17年春期午後問4）

#include <stdio.h>

/* 基本情報 平成17年春期午後問4 */
/* ヒープソート */
void MakeHeap(int Top, int Last);
void Swap(int X, int Y);
void InitHeap(int Last);

int A[] = { 0, 91, 86, 72, 72, 45, 69, 24, 55, 1, 12, };

void HeapSort(int Num)
{
    int Idx;
    InitHeap(Num);
    for (Idx = Num; Idx > 1; Idx--) {
        Swap(1, Idx);
        MakeHeap(1, Idx-1);
    }
}

void MakeHeap(int Top, int Last)
{
    int L, R;
    L = Top * 2;
    R = L + 1;
    if (R <= Last) {
        if (A[L] < A[R]) {
            if (A[Top] < A[R]) {
                Swap(Top, R);
                MakeHeap(R, Last);
            }
        } else {
            if (A[Top] < A[L]) {
                Swap(Top, L);
                MakeHeap(L, Last);
            }
        }
    } else {
        if (L <= Last) {
            if (A[Top] < A[L]) {
                Swap(Top, L);
                MakeHeap(L, Last);
            }
        }
    }
}

void Swap(int X, int Y)
{
    int Tmp;
    Tmp = A[X];
    A[X] = A[Y];
    A[Y] = Tmp;
}

void InitHeap(int Last)
{
    int Idx;
    for (Idx = Last / 2; Idx >= 1; Idx--)
        MakeHeap(Idx, Last);
}

int main()
{
    int i;
    int Num = sizeof(A) / sizeof(A[0]) - 1; 
    HeapSort(Num);
    printf("Num = %d\n", Num);
    for (i = 1; i <= 10; i++)
        printf("A[%2d] = %2d\n", i, A[i]);
    return 0;
}