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

演習6-2の解答

パス1:
  6   4   3   7   1   9 + 8
  6   4   3   7   1 - 8   9
  6   4   3   7 + 1   8   9
  6   4   3 + 1   7   8   9
  6   4 + 1   3   7   8   9
  6 + 1   4   3   7   8   9
  1   6   4   3   7   8   9
パス2:
  1   6   4   3   7   8 - 9
  （中略）
比較は21回でした。
交換は8回でした。

　比較・交換の要素が詳細に分かるように、右のような出力を行うプログラムを作成せよ。
　すなわち、比較する二つの要素と要素の間に、交換を行う場合は+を、交換を行わない場合は-を表示すること。
　また、ソート終了時に、比較回数と交換回数を表示すること。

/*
    演習6-2
    単純交換ソート
*/

#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++) {
        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]) {
                scnt++;
                swap(int, a[j - 1], a[j]);
            }
        }
        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);
}

戻る