バブルソート

バブルソートは、配列の先頭から最後まっで、隣り合う二つの要素の値を順に比較して、必要に応じて両者の値を入れ替えることで整列を行うアルゴリズムである。具体的なアルゴリズムは次のようになっている。

  1. j = n - 1, n - 2, ..., 2, 1, 0 として、A[j] と A[j + 1] を比較する。
    1. A[j] > A[j + 1] ならば、A[j] と A[j + 1] の要素を入れ換える。
    2. A[j] < A[j + 1] ならば、何もしない。
    この操作により、最小値が配列の先頭に移動される。
  2. 手順 1 を n 回繰り返す。ただし、i 回目の操作を行うとき、配列の 1 番目から i - 1 番目までの要素はすべて整列済みであることから、A[j] と A[j + 1] の比較は、j = i, i + 1, ..., n - 1 に対して行う。

このように、配列中に n 個の要素があるとき、n + (n - 1) + (n - 2) + ... + 2 + 1 = n(n+1)/2 回の操作を行うことになる。その計算量は O(n2) である。アルゴリズムとして非常に単純で、配列の要素数が少ない時は手軽に利用できるが、要素数が多くなると計算量が要素数の 2 乗のオーダーで増えるため、計算速度が著しく低下する。

C/C++ を利用してこのアルゴリズムを実装すると次のようになる。

#include <stdio.h>

void bubbleSort(int array[], int array_size) {
    int i, j, k;

    for (i = 0; i < (array_size - 1); i++) {
        for (j = (array_size - 1); j > i; j--) {
            if (array[j] < array[j - 1]) {
                k = array[j];
                array[j] = array[j - 1];
                array[j - 1] = k;
            }
        }
    }
}

int main (void) {

    int i;
    int array[10] = {3, 6, 1, 7, 2, 0, 4, 5, 9, 8};

    printf("       array: ");
    for (i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    bubbleSort(array, sizeof(array) / sizeof(array[0]));

    printf("sorted array: ");
    for (i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    return 0;
}