【図解】バブルソート：アルゴリズム【C言語】

本記事では、基本的なソートの一種である「バブルソート」のアルゴリズム解説・C言語による実装を確認していきます。

アルゴリズム解説では、図を用いた解説を行うため、イメージしやすい構成となっています。

ソートは、アルゴリズムの中でも非常に基本的な分野なので、是非この機会にマスターしましょう。

本記事でわかること

バブルソートの基本的な情報
アルゴリズムの流れ
C言語による実装方法

こちらの記事で、他のソートアルゴリズムをまとめています。

>>ソートアルゴリズム　計算量・特徴一覧

アルゴリズム入門書はこの一冊で十分！

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

created by Rinker

¥3,938 （2020/09/01現在 Amazon調べ・詳細）

1 バブルソートとは
2 バブルソートのアルゴリズム
3 バブルソートの実装【C言語】

バブルソートとは

バブルソートは、ソートアルゴリズムの一種であり、比較的簡単なソートです。

基本的な情報は以下になります。

最悪計算時間 \(O\)	安定性
\(O(n^2)\)	安定

次の章で確認するように、バブルソートは配列中の隣接する要素を次々に比較・交換していきます。

また、挿入ソートや選択ソートと同じく、左端から徐々にソート済み部分が増えていくアルゴリズムとなっています。

>>【図解】挿入ソート：アルゴリズム【C言語】

>>【図解】選択ソート：アルゴリズム【C言語】

その様子が、泡が次々と水面に上がっていくように見えることから、「バブルソート」と呼ばれるらしいです。

（個人的には、そうは見えないけど、、）

バブルソートのアルゴリズム

まずは、軽く全体的な流れを確認し、その後、図を用いた説明へと移ります。

バブルソートのアルゴリズムは以下のようになります。

配列の大小関係が逆になっている隣接要素が無くなるまで次の処理を繰り返す。

配列の末尾の要素から隣接する要素を順番に比較し、大小関係が逆であれば交換する。

文面だと伝わりづらいので、さっそく実例を見ていきましょう。

では、サイズが８の配列で昇順ソートの具体例を見ていきます。

ここでは、配列の初期状態を次のようにします。

初期状態では、すべての要素が未ソート部分となりますね。

まずは、配列の末尾「６」に着目し、その左の要素「２」と比較していきます。

この例だと、６は２よりも大きいため、交換はしません。

次に、着目する要素を１つずらし、「２」とその左の要素「４」を比較します。

今回は左の要素の方が大きいため、値を交換します。

さきほどと同様に、着目する要素を１つずらし、「２」とその左の要素「７」を比較します。

今回も左の要素の方が大きいため、値を交換します。

ここまで確認してきたことを、左端に到着するまで繰り返していきます。

ここからは機械的に進めていきます。

これで、左端の要素がソート済みとなりました。

この後は、ここまで行ってきた動作を繰り返します。

つまり、「配列の末尾の要素から順番に、隣接する要素と比較」を繰り返すということです。

ここまでの動作を１セットとします。

では、もう１セット見てみましょう。

ここも機械的に進めます。

これで、左側の２つの要素がソート済みとなりました。

2セット目が終わった段階ではこうですね。

3セット目以降は、１セットおきの配列の状態のみを確認します。

（全部の過程を載せると冗長になるので）

残りの処理を自分でやってみて、下の画像を答え合わせ的な感じで使うのもいいかもしれませんね。

これで配列の要素すべてがソート済みとなりました。

ここまでがバブルソートアルゴリズムの動きとなります。

次の章では、これをC言語で実装していきます。

実際に自分の手で実装することで、より理解が深まるので、是非確認してみてください。

バブルソートの実装【C言語】

さっそく、プログラム全体のコードを示します。

#include <stdio.h>
#define N 8

// 配列の全ての要素を出力する
void printArray(int A[], int n) {
    for (int i = 0; i < n; i++) {
        if (i == 0)
            printf("%d", A[i]);
        else
            printf(" %d", A[i]);
    }
    printf("\n");
}

// 配列の要素を入れ替える
void swap(int A[], int a, int b) {
    int temp;
    temp = A[a];
    A[a] = A[b];
    A[b] = temp;
}

// バブルソートを行う
void bubbleSort(int A[], int n) {
    int flag = 1;
    for (int i = 0; flag; i++) {
        flag = 0;
        for (int j = n-1; j > i; j--) {
            if (A[j-1] > A[j]) {
                swap(A, j-1, j);
                flag = 1;
            }
        }
    }
}

int main(void) {
    int A[N] = {8, 3, 5, 1, 7, 4, 2, 6};

    printArray(A, N);   // ソート前の配列の要素を表示
    bubbleSort(A, N);   // バブルソートする
    printArray(A, N);   // ソート後の配列の要素を表示
    return 0;
}

#include <stdio.h>

#define N 8

// 配列の全ての要素を出力する

void printArray(int A[], int n) {

for (int i = 0; i < n; i++) {

if (i == 0)

printf("%d", A[i]);

else

printf(" %d", A[i]);

}

printf("\n");

}

// 配列の要素を入れ替える

void swap(int A[], int a, int b) {

int temp;

temp = A[a];

A[a] = A[b];

A[b] = temp;

}

// バブルソートを行う

void bubbleSort(int A[], int n) {

int flag = 1;

for (int i = 0; flag; i++) {

flag = 0;

for (int j = n-1; j > i; j--) {

if (A[j-1] > A[j]) {

swap(A, j-1, j);

flag = 1;

}

int main(void) {

int A[N] = {8, 3, 5, 1, 7, 4, 2, 6};

printArray(A, N); // ソート前の配列の要素を表示

bubbleSort(A, N); // バブルソートする

printArray(A, N); // ソート後の配列の要素を表示

return 0;

}

長々としていますが、バブルソート本体は、24~35行目の bubbleSort関数の中で実装しています。

バブルソートの実装は比較的容易であるため、詳細の解説は割愛します。

bubbleSort関数のループ内で、配列の要素が交換されるたびに要素を出力するようなコードを書き加えると、前の章で確認したような数値の並びになることが確認できるかと思います。

では、今回はここまでとします。

お疲れさまでした。

別のソートを確認したい方は、ソートアルゴリズム　計算量・特徴一覧をご覧ください。