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

戻る  

演習6-3の解答

/*
    演習6-3
    単純交換ソート（第２版：交換回数による打ち切り）
*/

#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, j, m;
    int  ccnt = 0;      /* 比較回数 */
    int  scnt = 0;      /* 交換回数 */

    for (i = 0; i < n - 1; i++) {
        int  exchg = 0;                     /* パスにおける交換回数 */
        printf("パス%d：\n", i + 1);

        for (j = n - 1; j > i; 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]);
                exchg++;
                scnt++;
            }
        }
        for (m = 0; m < n; m++)
            printf("%3d  " , a[m]);
        putchar('\n');
        if (exchg == 0) break;              /* 交換が行われなかったら終了 */
    }
    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);
}

戻る