バブルソートとは？仕組み・計算量・C++実装例を初心者向けに解説

バブルソートとは

バブルソート（Bubble Sort）は、比較に基づく基本的なソートアルゴリズムの一つです。隣り合う要素同士を順番に比較し、大小関係が逆になっている場合は交換（スワップ）を行うことで、データ全体を正しい順序へと並べ替えていきます。

バブルソートは他のソートアルゴリズムと比べて非常にシンプルで理解しやすいという特徴がありますが、その反面いくつかの欠点も抱えています。特に、大量のデータセットには不向きであり、ソート処理に多くの時間を要する点が弱点です。学習用途や小規模なデータには適していますが、実務で大規模データを扱う場合はクイックソートやマージソートなどが選択されることが一般的です。

バブルソートの仕組み

バブルソートでは、配列の先頭から隣接する2つの要素を比較していきます。前の要素が後ろの要素より大きければ両者を交換し、これを配列の末尾まで繰り返します。この一連の処理を「パス（走査）」と呼びます。大きな値が泡（バブル）のように浮かんでくる動きが名前の由来です。

各パスが終わるごとに、未ソート部分の最大値が末尾側に確定していきます。また、あるパスで一度も交換が発生しなかった場合は、すでに整列済みであることを意味するため、そこで処理を打ち切ることで無駄な繰り返しを省くことができます。

バブルソートの計算量

• 時間計算量： 最良ケースはO(n)、平均ケースおよび最悪ケースはO(n²)
• 空間計算量： O(1)

最良ケースでO(n)となるのは、改良版のバブルソートが交換フラグによる早期終了を持っているためです。データがすでにソート済みの場合、最初のパスで交換が一度も起こらず、ループを抜けます。

入力と出力

入力:
ソートされていないデータのリスト: 56 98 78 12 30 51
出力:
ソート後の配列: 12 30 51 56 78 98

アルゴリズム

bubbleSort( array, size)

入力 − データの配列と、配列内の要素の総数

出力 − ソート済みの配列

擬似コード

Begin
    for i := 0 to size-1 do
      flag := 0;
      for j := 0 to size – i – 1 do
        if array[j] > array[j+1] then
          swap array[j] with array[j+1]
          flag := 1
      done

      if flag ≠ 1 then
        break the loop.
    done
End

外側のループはパスの回数を管理し、内側のループで隣接要素の比較と交換を行います。変数flagは、そのパスで交換が行われたかどうかを記録しており、交換が一切なかった場合（flagが1でない場合）はループを脱出します。

C++による実装例

#include<iostream>
using namespace std;

void swapping(int &a, int &b) { //aとbの中身を入れ替える
    int temp;
    temp = a;
    a = b;
    b = temp;
}

void display(int *array, int size) {
    for(int i = 0; i<size; i++)
        cout << array[i] << " ";
    cout << endl;
}

void bubbleSort(int *array, int size) {
    for(int i = 0; i<size; i++) {
        int swaps = 0; //交換の有無を検出するためのフラグ
        for(int j = 0; j<size-i-1; j++) {
            if(array[j] > array[j+1]) { //現在の要素が次の要素より大きい場合
                swapping(array[j], array[j+1]);
                swaps = 1; //交換フラグをセット
            }
        }
        if(!swaps)
            break; //このパスで交換がなければ配列はソート済み
    }
}

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int arr[n]; //指定された要素数で配列を作成
    cout << "Enter elements:" << endl;

    for(int i = 0; i<n; i++) {
        cin >> arr[i];
    }

    cout << "Array before Sorting: ";
    display(arr, n);
    bubbleSort(arr, n);

    cout << "Array after Sorting: ";
    display(arr, n);
}

このプログラムでは、まずユーザーから要素数と各要素を受け取り、ソート前の配列を表示します。その後bubbleSort関数を呼び出してソートを実行し、結果を出力します。swapping関数は一時変数tempを使って2つの値を入れ替える補助関数です。

実行結果

Enter the number of elements: 6
Enter elements:
56 98 78 12 30 51
Array before Sorting: 56 98 78 12 30 51
Array after Sorting: 12 30 51 56 78 98

バブルソートのメリットとデメリット

メリット

• アルゴリズムが非常に単純で、実装が容易
• 追加のメモリ領域をほとんど必要としない（in-placeソート）
• 安定ソートであり、同じ値の相対的な順序が保たれる
• ほぼ整列済みのデータに対しては高速に動作する

デメリット

• 平均・最悪ケースでO(n²)となり、大規模データには不向き
• 要素の交換回数が多く、実行速度が遅い
• 実務ではクイックソートやマージソートなどの高性能なアルゴリズムが好まれる

以上のように、バブルソートは計算量的には非効率ですが、その分かりやすい動作からソートアルゴリズムの入門として最適な題材です。まずはこの基本をしっかり押さえ、その後より高度なソートアルゴリズムへと学習を進めるとよいでしょう。