バブルソート

バブルソートは、隣り合う要素を繰り返し比較し、昇順になっていない場合に入れ替える比較ベースのソートアルゴリズムです。1回のパスが終わると、未ソート部分に残っている最大値が右端の確定位置へ移動します。この名前は、値がリストの中を繰り返し移動する様子を表しています。バブルソートは手順を追いやすく実装も簡単ですが、実行時間が二次となるため、大きなデータ集合には適していません。

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

n 個の要素を持つ配列 A では、A[0] と A[1] を比較し、次に A[1] と A[2] を比較するというように、未ソート部分の末尾まで順に比較します。左側の値が右側の値より大きければ、2つを入れ替えます。この条件で昇順に並びます。降順にするには比較条件を逆にします。

1回のパスでは、左から右へ一巡します。パスの終わりには、調べた部分の最大値が右端に到達するため、次のパスではその1つ手前まで調べれば十分です。最初のパスでは n - 1 組を比較し、次は n - 2 組、その後も同様に減っていきます。固定回数の実装では n - 1 回のパスを行いますが、最後のパスで確認する組は1つだけです。要素数が2未満のリストでは比較は必要ありません。

バブルソートの例

入力が (5, 3, 4, 2, 1) だとします。1回目のパスでは、隣り合う組を順番に比較します。5 と 3 を入れ替えると (3, 5, 4, 2, 1) になります。次に 5 と 4 を入れ替えると (3, 4, 5, 2, 1)、5 と 2 を入れ替えると (3, 4, 2, 5, 1)、最後に 5 と 1 を入れ替えると (3, 4, 2, 1, 5) になります。これで最大値が右端に確定します。

2回目のパスでは先頭の4つの値だけを調べ、結果は (3, 2, 1, 4, 5) になります。3回目のパスで未ソート部分は (2, 1, 3, 4, 5) に、4回目で (1, 2, 3, 4, 5) に変わります。この例から、パスごとに調べる範囲が縮まり、すでに確定した値は再度比較しないことが分かります。

C++でのバブルソートの実装

次の完全なプログラムは、例の配列をその場で並べ替えます。内側のループの上限 n - i - 1 により、すでに確定した末尾部分との比較を避けます。また、values[j] > values[j + 1] のときに順序が逆の隣接要素を入れ替えるため、小さい値が左へ移動します。

この例を実行します。

このセクションのコードと表示されるラベルや出力は英語のままです。

#include <iostream>
#include <utility>
#include <vector>

void bubble_sort(std::vector<int>& values) {
    const int n = static_cast<int>(values.size());
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            if (values[j] > values[j + 1]) {
                std::swap(values[j], values[j + 1]);
            }
        }
    }
}

int main() {
    std::vector<int> values{5, 3, 4, 2, 1};
    bubble_sort(values);
    std::cout << "Sorted:";
    for (int value : values) {
        std::cout << ' ' << value;
    }
    std::cout << '\n';
}

Sorted: 1 2 3 4 5

提供された実行結果では、プログラムは正常に終了し、英語のラベル Sorted: に続いて、ソート済みの値 1 2 3 4 5 を出力しました。コード内のラベルと出力は英語のままです。

バブルソートの計算量と制約

固定回数のパスを行う実装では、入力の並び方にかかわらず (n - 1) + (n - 2) + ... + 1、つまり n(n - 1) / 2 回の比較を行います。そのため、最良・平均・最悪のいずれの場合も時間計算量は O(n²) です。逆順に並んだ入力などの最悪の場合には、多くの入れ替えも必要になります。この実装はベクターを直接変更し、入れ替え用の一時値だけを使うため、補助空間計算量は O(1) です。

早期終了版では、各パスで入れ替えがあったかを記録し、リストに変化がなければ処理を終了できます。この版は、すでに整列済みの入力なら O(n) 時間で処理できますが、平均と最悪の場合は引き続き O(n²) です。上記の固定回数版には、この最適化は含まれていません。バブルソートは隣接要素の比較を学ぶときや、ごく小さな入力には役立ちますが、大きなデータ集合には通常、標準ライブラリのソートアルゴリズムのほうが適しています。