C言語のバブルソートの実装方法、4選: 比較関数、番兵を使った高速化等

O(n^2)はどれぐらいの計算量かと言うと、二重のfor文が総当たりで回るぐらいの遅さです。
行列を描画するときに二重のfor文を使うと思いますが、行列の要素を1つずつ描画していく感覚を持ってもらうとわかりやすいかもしれません。
たとえば10 x 10の行列であればその要素数はぜんぶで100になります。
つまり100個の要素を描画する遅さです。

ソートするデータ量が100個の場合、その最悪計算時間は10000個分になるということです。
こう考えるとどれぐらいO(n^2)が遅いのかわかりますね。

実装が簡単なので使いやすいことは使いやすい

バブルソートは確かに遅いのですが、実装が簡単なため使いやすいことは使いやすいです。
速度が必要とされる場面では非実用的なソートアルゴリズムですが、それ以外のケースでは使われることもあります。
ただボトルネックになりやすいアルゴリズムのため、実装に使う場合は他のソートアルゴリズムと交換できるように工夫しておく必要があります。

バブルソートは嫌われ者なのか？

バブルソートは嫌われているのでしょうか？
遅い、非実用的、作者不明と嫌われる要素はたくさん持っていますが、じっさいのところどうなのでしょうか？

とんでもない、それは誤解です

バブルソートが嫌われているという認識は大きな誤解です。
バブルソートは確かにデメリットの多いソートアルゴリズムですが、実装が簡単で安定したソートとしてたくさんの人から好かれているアルゴリズムと言っていいでしょう。
バブルソートは遅いですが実装が簡単で使いやすく、取り回しが容易です。

みんなから愛されているソートアルゴリズム

バブルソートほどたくさんの人に認知され利用されているアルゴリズムはなかなか無いでしょう。
バブルソートは大学の教材などにも利用されるし、しばしばプログラマーの仕事にも使われます。
まさにみんなから愛されているソートアルゴリズムと言ってもいいのがバブルソートです。

バブルソートは仕事で使ってもいいものか？

バブルソートは実用性に疑問点がついていますが、プログラマーの仕事に使われることはあるのか？
使っても良いものなのか？　というところですが、これは使い方によります。

ベタ書きのバブルソートはリプレースが大変

たとえばバブルソートのアルゴリズムをソースコードにベタ書きするとどうなるでしょうか。
そのベタ書きの部分でボトルネックなどが発生した場合に書き直すのが困難になる可能性があります。
そのためバブルソートのアルゴリズムのベタ書きは控えたほうが良いと言えます。

仕事で使うならAPIを定義しよう

仕事で使う場合は、バブルソートの専用を関数を作ってAPIを定義しましょう。
そうすればボトルネックが発生したときにその関数の呼び出し部分をリプレースすれば取り換えできます。
こうしておくとバブルソートを使っても安心です。

バブルソートはなぜ学ぶ必要があるのか？

実用性に疑問符が付いているバブルソートですが、なぜ我々はバブルソートを学ぶ必要があるのでしょうか？
クイックソートなどもっと実用的なソートアルゴリズムを学んだ方が良いのでは？
たしかにクイックソートなどの実用的なソートを学ぶのは大事ですが、バブルソートにはバブルソートの利点があります。

ソートの基本的アルゴリズムとして学ぶ

バブルソートはソートの基本的アルゴリズム、ソートの基礎として学ぶのにうってつけのアルゴリズムです。
そのため学習用途のアルゴリズムとして適しています。
実装が簡単なため、短時間でソートの概要について学ぶことができるし、なんならアルゴリズムの暗記も可能です。
それぐらいコンパクトなアルゴリズムなので、勉強に最適と言うことです。

学習のハードルが低いためアルゴリズム入門の定番

バブルソートはコンパクトなので、学習のハードルが低く、アルゴリズムの入門として適しています。
クイックソートなどは複雑なアルゴリズムのため学習が難しいですが、バブルソートであれば単純なため学習が容易です。
そのためアルゴリズム入門用のアルゴリズムとしても最適というわけです。

バブルソートはどんな時に使われるのか？

バブルソートはどんなときに使われるのでしょうか？
バブルソートの実用範囲は？
バブルソートを使えるシーンはどんな時？

まとめると↓2つです。

入社試験や面接でのコーディングの出題として
速度を必要としない場面で使う

入社試験や面接でのコーディングの出題として

バブルソートはコンパクトなアルゴリズムで、書こうと思えばすぐに書くことができるため入社試験や面接の出題などでたびたび出されることがあります。
筆者もプロジェクトの面接でバブルソートを実装してみてほしいと言われ、実装した思い出があります。

（^ _ ^）

ちなみにその面接には受かりました

アルゴリズムに対する認識があるかどうか、という点を問うのにバブルソートは向いています。
アルゴリズムを学んだことがある人なら必ず実装するであろう基礎的なアルゴリズムだからです。

速度を必要としない場面で使う

あとは速度を必要としない場面で使われることがあります。
バブルソートはとにかく遅いです。そのため大量のデータ処理には向いていません。
しかしデータ量が少なくて、それほど頻繁に呼ばれることがない処理では使われることもあるアルゴリズムです。
ソートも安定しているので安心して使うことができるのも特徴です。

バブルソートはどんなアルゴリズムか？

バブルソートのアルゴリズムは単純です。
たとえば配列aryがあったとします。
この配列を外側のforループで回します。
そして内側にもforループを作ってaryの要素数-1だけ回します。
そして内側のforループで隣り合う要素を比較し、比較が真であれば、つまりどちらかが小さければ（大きければ）その隣り合う要素を交換（スワップ）します。
内側のfor文では先頭から末尾までこのスワップを繰り返します。
そして外側のfor文が終わるまでループを回します。

内側のfor文でスワップが発生しなければ、その配列はすでに整列が完了しているということになります。
そのためこの特徴を利用して最適化することも出来ます。

また、バブルソートは配列の末尾から要素が整列されていく特徴があるため、番兵を使って末尾の要素の比較をスキップして高速化することも可能です。

バブルソートで使われるスワップはどんな技術か？

バブルソートでは「スワップ」という技術を使います。
スワップとは2つの値をたがいに「交換する」技術のことを言います。
たとえばC言語ならスワップは↓のようなものです。

    int a = 1, b = 2;

    // aとbの値をスワップする
    int tmp = a;
    a = b;
    b = tmp;

    printf("a[%d] b[%d]\n", a, b);
    // a[2] b[1]

C言語によるバブルソートの実装方法

それではC言語によるバブルソートの実装を見てみたいと思います。

基本的なバブルソート

まずは基本的なバブルソートからです。
なんの最適化もほどこしていない、もっとも原始的なバブルソートです。

#include <stdio.h>

/**
 * 原始的なバブルソートを実行する
 * 
 * @param[in|out] ary 配列
 * @param[in] arylen 配列の長さ
 */
void bubble_sort(int *ary, int arylen) {
    // 外側のfor文
    for (int i = 0; i < arylen - 1; i += 1) {
        // 内側のfor文
        for (int j = 0; j < arylen - 1; j += 1) {
            // 隣り合う要素同士を比較
            if (ary[j] > ary[j + 1]) {
                // スワップの実行
                int tmp = ary[j];
                ary[j] = ary[j + 1];
                ary[j + 1] = tmp;
            }
        }
    }
}

int main(void) {
    int ary[] = {4, 2, 3, 1};  // ソート対象のint型の配列
    int arylen = sizeof(ary) / sizeof(ary[0]);  // 配列の長さ

    bubble_sort(ary, arylen);  // バブルソートの実行

    // バブルソートの結果を出力
    for (int i = 0; i < arylen; i += 1) {
        printf("%d ", ary[i]);
    }
    puts("");

    return 0;
}

↑のコードをコンパイルして実行すると↓のように出力されます。

1 2 3 4

これは昇順（小さい順）のソートになります。
bubble_sort()内のif文である↓の部分、

            // 隣り合う要素同士を比較
            if (ary[j] > ary[j + 1])

この比較演算子（>）を変えると昇順と降順を変えることができます。
ためしに比較演算子を<にしてみてください。
ソートの結果は降順（大きい順）になるはずです。

このバブルソートでもソートは可能ですが、一部に無駄があり、まだ効率化が可能です。

スワップ・フラグによる最適化

「スワップ・フラグ」を使うとバブルソートを効率化することができます。
スワップ・フラグはスワップが発生した場合にtrueになるフラグです。
スワップが発生している状態は、まだ配列は整列されていない状態です。
しかしスワップが発生していない状態はすでに配列が整列されている状態です。
そのためスワップ・フラグがfalseの場合は外側のループから抜けることができます。

#include <stdio.h>
#include <stdbool.h>

/**
 * スワップ・フラグを使ったバブルソートを実行する
 * 
 * @param[in|out] ary 配列
 * @param[in] arylen 配列の長さ
 */
void bubble_sort(int *ary, int arylen) {
    bool swapped;  // スワップしたかどうかのフラグ

    for (int i = 0; i < arylen - 1; i += 1) {
        swapped = false;  // フラグを折っておく
        for (int j = 0; j < arylen - 1; j += 1) {
            if (ary[j] > ary[j + 1]) {
                int tmp = ary[j];
                ary[j] = ary[j + 1];
                ary[j + 1] = tmp;
                swapped = true;  // フラグを立てる
            }
        }

        // フラグが折れたままならスワップが発生していないということになる
        // 「スワップが発生していない＝整列されている」ということ
        // その場合はループから抜ける
        if (!swapped) {
            break;
        }
    }
}

int main(void) {
    int ary[] = {4, 2, 3, 1};  // ソート対象のint型の配列
    int arylen = sizeof(ary) / sizeof(ary[0]);  // 配列の長さ

    bubble_sort(ary, arylen);  // バブルソートの実行

    // バブルソートの結果を出力
    for (int i = 0; i < arylen; i += 1) {
        printf("%d ", ary[i]);
    }
    puts("");

    return 0;
}

番兵を使ったバブルソート

外側のfor文のカウント変数iは内側のfor文の番兵として使うことができます。
番兵を使うことでさらにバブルソートの効率化が可能です。
ここまで最適化するとコンプリートなバブルソートという感じになります。

#include <stdio.h>
#include <stdbool.h>

/**
 * 番兵を使ったバブルソートを実行する
 * 
 * @param[in|out] ary 配列
 * @param[in] arylen 配列の長さ
 */
void bubble_sort(int *ary, int arylen) {
    bool swapped;

    for (int i = 0; i < arylen - 1; i += 1) {
        swapped = false;
        // arylen - i - 1 でiを番兵にする
        for (int j = 0; j < arylen - i - 1; j += 1) {
            if (ary[j] > ary[j + 1]) {
                int tmp = ary[j];
                ary[j] = ary[j + 1];
                ary[j + 1] = tmp;
                swapped = true;
            }
        }

        if (!swapped) {
            break;
        }
    }
}

int main(void) {
    int ary[] = {4, 2, 3, 1};  // ソート対象のint型の配列
    int arylen = sizeof(ary) / sizeof(ary[0]);  // 配列の長さ

    bubble_sort(ary, arylen);  // バブルソートの実行

    // バブルソートの結果を出力
    for (int i = 0; i < arylen; i += 1) {
        printf("%d ", ary[i]);
    }
    puts("");

    return 0;
}

比較関数を使ったバブルソート

隣り合う要素の比較をソート関数の外に出せれば、ユーザーが自由に要素の比較を行うことができます。
要素の比較を自由に行えるということは、降順と昇順のソートをユーザーが切り替えられるということです（比較演算子を切り替えればいいため）。
そういったソート関数の設計をしたい場合は、↓にように関数ポインタを使って比較関数を渡せるようにします。
↓のcompare()というのが比較関数です。

#include <stdio.h>
#include <stdbool.h>

/**
 * 比較関数を使ったバブルソートを実行する
 * 
 * @param[in|out] ary 配列
 * @param[in] arylen 配列の長さ
 */
void bubble_sort(int *ary, int arylen, bool (*compare)(int, int)) {
    bool swapped;

    for (int i = 0; i < arylen - 1; i += 1) {
        swapped = false;
        for (int j = 0; j < arylen - i - 1; j += 1) {
            // 比較関数（compare）を使って条件分岐する
            if (compare(ary[j], ary[j + 1])) {
                int tmp = ary[j];
                ary[j] = ary[j + 1];
                ary[j + 1] = tmp;
                swapped = true;
            }
        }

        if (!swapped) {
            break;
        }
    }
}

/**
 * バブルソートで使われる比較関数 
 *
 * @param[in] left 左の要素
 * @param[in] right 右の要素
 */
bool my_compare(int left, int right) {
    return left > right;
}

int main(void) {
    int ary[] = {4, 2, 3, 1};  // ソート対象のint型の配列
    int arylen = sizeof(ary) / sizeof(ary[0]);  // 配列の長さ

    bubble_sort(ary, arylen, my_compare);  // 比較関数を渡してバブルソートの実行

    // バブルソートの結果を出力
    for (int i = 0; i < arylen; i += 1) {
        printf("%d ", ary[i]);
    }
    puts("");

    return 0;
}

↑の場合、my_compare()という関数内の比較演算子を切り替えれば、昇順と降順を切り替えることができます。

バブルソートの次に何を学ぶべきか？

バブルソートの次は何を学ぶべきでしょうか？
ソートアルゴリズムはいろいろありますが、クイックソートについて学ぶといいかもしれません。

バブルソートの次はクイックソートを学ぼう

クイックソートは実用的なバブルソートでソートアルゴリズム界のスーパースターです。
このアルゴリズムについて学べばさらにソートについて理解を深めることが可能になるでしょう。

ソートのアルゴリズムは奥が深い

ソートは配列などの要素を並べ替えるだけのアルゴリズムですが、その奥は深く、さまざまな手法が考案されています。
マージソートや、コムソート、挿入ソートにスリープソートなど。
ソートアルゴリズムにはまればアルゴリズムに関してより一層詳しくなれること間違いなしですね。

おわりに

今回はC言語によるバブルソートの実装について解説しました。
バブルソートと一言で言ってもバリエーションがあり、また実装もお手軽なので試しやすく親しみのあるソートと言えます。
バブルソートは丸暗記もいけるコンパクトさなので、ぜひ丸暗記をおすすめします。
きっと役に立つ日が来ます。

（^ _ ^）

バブルソートで並べ替えよう

（・ v ・）

1億件のデータお願い！

（^ _ ^）

あ、パスします

C言語のバブルソートの実装方法、4選: 比較関数、番兵を使った高速化等

目次

関連記事

関連動画