バブルソート — シンプルな比較ベースのソートアルゴリズム

仕組み

高いレベルでは、このアルゴリズムは配列全体に対して複数回のパスを行います。各パスでは、隣り合う各組を比較し、順序が逆なら交換します。最初のパスが終わると最大要素が配列の末尾へ移動し、2回目のパスでは次に大きい要素が所定の位置に落ち着く、という具合に進みます。完全な1パスで交換が一度も起きなくなった時点で、リストは整列済みだと判断して処理を終了します。

1. リストの先頭から始める。
2. 現在の要素と次の要素を比較する。
3. 順序が逆なら交換する。
4. 1つ前へ進み、パスの終わりまで繰り返す。
5. あるパスで交換が起きなくなるまで、パスを繰り返す。

計算量と特徴

バブルソートはインプレースで動作し、追加で必要なメモリは定数量だけです。安定なソート法でもあり、同じ値どうしの相対順序は保たれます。典型的な時間計算量は平均ケースと最悪ケースで O(n^2) の比較と交換であり、大規模データには実用的ではありません。交換が一度も行われなかったら早期終了する単純な最適化を加えると、すでに整列されたリストでは最良ケースが O(n) になります。

変種と比較

小さな変種はいくつかあります。よくある改善は、交換が発生したかを示すフラグを追加して早めに抜ける方法です。カクテルシェイカーソート（双方向バブル）は左から右、右から左へと交互にパスし、大きい要素と小さい要素の両方をより速く移動させます。選択ソートや挿入ソートと比べると、バブルソートは遅いことが多いですが、概念が分かりやすいため教学では今も人気があります。対話的なデモは 可視化 を試してください。

例として、[5, 1, 4, 2, 8] を考えると、最初のパスでは 5 と 1 を比較して交換し、次に 5 と 4 を交換し、さらに 5 と 2 を交換し、最後に 5 と 8 は交換しません。これで 5 は末尾に残ります。パスを繰り返すことで、最終的に [1, 2, 4, 5, 8] という整列済みの並びになります。バブルソートは仕組みが明快で実装コストも低いため、小規模またはほぼ整列済みの入力、診断用コード、教室でのデモには役立ちますが、本番規模のソートには向いていません。