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

戻る  

演習6-4の解答

/*
    演習6-4
    単純交換ソート（第３版：走査範囲を限定）
*/

#include  <stdio.h>

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


/*--- 単純交換ソート（第３版：走査範囲を限定） ---*/
void bubble(int a[], int n)
{
    int  i = 0, j, m;
    int  ccnt = 0;      /* 比較回数 */
    int  scnt = 0;      /* 交換回数 */
    int  k = 0;                             /* a[k]より前はソート済み */

    while (k < n - 1) {
        int  j;
        int  last = n - 1;                  /* 最後に交換した位置 */

        printf("パス%d：\n", ++i);
        for (j = n - 1; j > k; j--) {
            for (m = 0; m < n - 1; m++)
                printf("%3d %c" , a[m], (m != j-1) ? ' ' :
                                        (a[j - 1] > a[j]) ? '+' : '-');
            printf("%3d\n", a[n - 1]);

            ccnt++;
            if (a[j - 1] > a[j]) {
                swap(int, a[j - 1], a[j]);
                last = j;
                scnt++;
            }
        }
        k = last;
        for (m = 0; m < n; m++)
            printf("%3d  " , a[m]);
        putchar('\n');
    }
    printf("比較は%d回でした。\n", ccnt);
    printf("交換は%d回でした。\n", scnt);
}

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

    bubble(x, nx);                          /* 配列xを単純交換ソート */

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

    return (0);
}

戻る