Ｃ言語講座：バブルソート

/* 今日からしばらくの間、ソート ( 整列 ) について学びます。ソートとは、ある規則によってデータを並び替えることです。ソートのアルゴリズムには、色々なものがあります。アルゴリズムによっては、高速にも低速にもなります。また、同じアルゴリズムでも、ソート対象のデータのばらつきかたで、実行速度が影響を受けることもあります。 */

/* バブルソート */

/* 今日は、高速ではないが、容易に理解できる、バブルソート ( 単純交換法 ) を取りあげます。今日のソート対象のデータは、１桁の整数１０個です。これを小さい方から順に並べます。

バブルソートは、隣り合う二つのデータを比較して、前の要素の方が大きかったら交換します。データ列の後方から前方へ向かって全てのデータについてこれを行うと、最も小さいデータが、先頭に来て、位置が確定します。

２回目のソートでは、ソート対象は２番目以降のデータになります。このソートで、２番目のデータの位置が確定します。これを繰り返すことで、ソートが完成します。

２重の for ループを使って、上記のアルゴリズムをコードにしたのが、BubSort( ) です。for ループの i と j の値の変化について注目して下さい。引数として、ソートするデータの配列と、データの数を取ります。

ShowData( ) は、ソート前、ソート中、ソート後のデータを画面に表示します。プログラムを実行すると、先頭から要素の位置が確定して行くのが、良くわかると思います。この過程が、泡が浮かび上がって行く様子に似ているので、バブルソートと名付けられました。

バブルソートの実行時間は、データのばらつきかたに、影響を受けません。 */

/* ここからソースプログラム */

#include  <stdio.h>

int BubSort(int x[ ], int n);
void ShowData(int x[ ], int n);
void main(void);

#define NUM_DATA 10                           /* ソートするデータの数 */
int x[ ] = {9, 4, 6, 2, 1, 8, 0, 3, 7, 5};    /* このデータをソート */


  /* バブルソートを行う */
int BubSort(int x[ ], int n)
{
    int i, j, temp;

    for (i = 0; i < n - 1; i++) {
        for (j = n - 1; j > i; j--) {
            if (x[j - 1] > x[j]) {  /* 前の要素の方が大きかったら */
                temp = x[j];        /* 交換する */
                x[j] = x[j - 1];
                x[j - 1]= temp;
            }
        }	
        /* ソートの途中経過を表示 */
        ShowData(x, NUM_DATA);
    }
}
	
  /* ソート対象のデータを表示 */
void ShowData(int x[ ], int n)
{
    int i;

    for (i = 0; i < n ; i++)
        printf("%d\t", x[i]);
}

void main(void)
{		
      /* ソート前のデータを表示 */
    printf("ソート前:\n");
    ShowData(x, NUM_DATA);
    printf("\n\n");

    BubSort(x, NUM_DATA);

      /* ソート後のデータを表示 */
    printf("\n\nソート後:\n");
    ShowData(x, NUM_DATA);
}

/* ここまでソースプログラム */

/* バブルソートの処理速度は、データの要素数の２乗にほぼ比例します。

速度は遅いけれど、データの数が少ない時は、充分実用になります。また、アルゴリズムが単純で分かりやすいので、ソースプログラムを作るのも楽です。 */