Ｃ言語によるアルゴリズムとデータ構造

戻る  

演習6-17の解答

           01
         ／　＼
      03        05
    ／   ＼    ／＼
  07      09  02  04
 ／＼   ／
06  08  10

/*
    演習6-17
    ヒープソート（ソートの過程をグラフで表示）
*/

#include  <stdio.h>

#define swap(type, x, y)    do { type t = x; x = y; y = t; } while (0)

/*--- 2のn乗を求める ---*/
int pow2(int n)
{
    int  k = 1;

    while (n--)
        k *= 2;
    return (k);
}

/*--- ヒープを表示 ---*/
static void disp_heap(int a[], int n)
{
    int  i, w, level;
    int  height = 1;        /* 木の高さ */

    i = n;
    while (i /= 2)
        height++;

    i = 0;
    w = 1;
    for (level = 0; level < height; level++) {
        int  k;
        printf("%*s", pow2(height - level) - 2 , "");
        for (k = 0; k < w; k++) {
            printf("%02d", a[i++]);
            if (i >= n) goto Exit;
            printf("%*s", pow2(height - level + 1) - 2, "");
        }
        putchar('\n');

        printf("%*s", pow2(height - level) - 3 , "");
        for (k = 0; k < w; k++) {
            if (2 * k + i     < n) printf("／");
            if (2 * k + i + 1 < n) printf("＼");
            printf("%*s", pow2(height - level + 1) - 4, "");
        }
        putchar('\n');
        w *= 2;
    }
Exit:
    putchar('\n');
    putchar('\n');
}


/*--- a[left]～a[right]をヒープ化 ---*/
static void downheap(int a[], int left, int right)
{
    int  temp = a[left];                /* 根 */
    int  child;
    int  parent;

    for (parent = left; parent < (right + 1) / 2; parent = child) {
        int  cl = parent * 2 + 1;       /* 左の子 */
        int  cr = cl + 1;               /* 右の子 */
        child = (cr <= right  &&  a[cr] > a[cl]) ? cr : cl;     /* 大きい方 */
        if (temp >= a[child])
            break;
        a[parent] = a[child];
    }
    a[parent] = temp;
}

/*--- ヒープソート ---*/
void heapsort(int a[], int n)
{
    int  i;

    for (i = (n - 1) / 2; i >= 0; i--) {
        disp_heap(a, n);
        downheap(a, i, n - 1);
    }

    for (i = n - 1; i > 0; i--) {
        swap(int, a[0], a[i]);
        disp_heap(a, n);
        downheap(a, 0, i - 1);
    }
}

int main(void)
{
    int  i;
    int  x[100];
    int  n;
    int  nx = sizeof(x) / sizeof(x[0]);

    do {
        printf("要素数（1～%d）は：", nx);
        scanf("%d", &n);
    } while (n < 1  ||  n > nx);

    printf("%d個の整数を入力せよ。\n", n);
    for (i = 0; i < n; i++) {
        printf("x[%d] : ", i);
        scanf("%d", &x[i]);
    }

    heapsort(x, n);                     /* 配列xをヒープソート */

    puts("昇順にソートしました。");
    for (i = 0; i < n; i++)
        printf("x[%d] = %d\n", i, x[i]);

    return (0);
}

戻る