バブルソートとは

バブルソートのアルゴリズムは単純で、全ての要素を舐めていって、隣接する要素と比較して順序が逆であればスワップすることを、(要素数 – 1)回繰り返すだけの安定なソートです。そのため、最悪計算時間が O(n2) になりますが、アルゴリズムが単純なため、他のソートアルゴリズムの基礎として、始めに覚えるソートアルゴリズムとなるでしょう。

日本語では、”基本交換法”とか”隣接交換法”と言ったりしますが、”バブル”の語源はバブル全盛期に開発されたアルゴリズムだからです。なんてことは当然なくて、先頭から要素の位置が確定していく様子が泡(bubble)が浮かび上がってくるように見えることから、”バブルソート”と呼ばれるようになりました。

#include <stdio.h>
#define swap(x, y) { (x != y) && (x += y, y = x - y, x -= y); }

void bubble_sort(int *, int);
void show(int *, int);

// ソート前のデータを表示後、ソートしてからソート後のデータを表示する
int main(void) {
    // ソートするデータの情報
    const int count = 5;
    int data[] = { 3, 2, 5, 1, 4 };

    // ソート前のデータを表示
    printf("ソート前：");
    show(data, count);

    // バブルソート実行
    bubble_sort(data, count);
    
    // ソート後のデータを表示
    printf("ソート後：");
    show(data, count);

    return (0);
}

// data[] を順に表示する
void show(int data[], int count) {
    int i;
    for (i = 0; i < count; i++) printf("%d, ", data[i]);
    printf("\n");
}

// バブルソート関数
void bubble_sort(int data[], int count) {
    int i, j;

    for (i = 0; i < (count - 1); i++) {
        for (j = (count - 1); j > i; j--) {
            if (data[j - 1] > data[j]) {
                swap(data[j], data[j - 1])
            }
        }
    }
}

実行結果

ソート前：3, 2, 5, 1, 4,
ソート後：1, 2, 3, 4, 5,

ソート関数の解説

void bubble_sort(int data[], int count) {
    int i, j;
 
    for (i = 0; i < (count - 1); i++) {
        for (j = (count - 1); j > i; j--) {
            if (data[j - 1] > data[j]) {
                swap(data[j], data[j - 1])
            }
        }
    }
}

冒頭に書いた通り、全ての要素を舐めていって、隣接する要素と比較して順序が逆であればスワップすることを、(要素数 – 1)回繰り返すだけです。バブルソートで行う処理は、2つのデータの比較と入れ替えだけです。以下の部分ですね。

if (data[j - 1] > data[j]) {
    swap(data[j], data[j - 1])
}

この処理の行われる回数については単純な計算で求められます。データ数を n とすると、変数i のループの1周目は、一番小さいデータを一番上まで運ぶのに (n – 1)回(変数j のループ) の処理が行われます。変数i のループ2周目は、二番目に小さいデータを上から二番目まで運ぶのに (n – 2)回(変数j のループ) の処理が行われます。

そして、最後は二番目に大きなデータを下から二番目に運ぶのに 1回 の処理が行われます。最後に値の位置が確定していないのは、一番下と下から二番目だけですからね。下から二番目のデータまで決定すると、当然一番下のデータは動きようがありませんので処理はありません。つまり計算式としては (n – 1) + (n -2) + … + 2 + 1 となります。n(n – 1) / 2 、冒頭に書いた通り O(n²) ですね。

つまり、データの数の二乗の処理が行われるため、データ量が2倍、3倍に増えると、処理速度は4倍、9倍と増えていきます。そんな感じで、遅いけど単純で書きやすいアルゴリズムがバブルソートです。