Hello Algo 徹底解説：バブルソートの仕組み・flag 最適化・計算量解析・安定性を多言語実装で学ぶ

2026-09-07 13:55:08作者：宣利权Counsellor

バブルソート（bubble sort）は、隣接する要素の大小を繰り返し比較・交換して配列全体を整列する、最も基本的なソートアルゴリズムのひとつです。《Hello 算法》の日本語版ドキュメント bubble_sort.md は、この「泡が水面に浮かび上がる」過程を図解で解説し、基本実装・flag による効率最適化・時間/空間計算量・安定性の 4 点に絞って整理しています。本記事では、このドキュメントの骨格を完全に踏襲しながら、リポジトリ内の Python / Java / C / C++ / Go 実装（ja/codes 配下）を照合し、ループ構造の意味や「最良 O(n)」が成立する条件までをコードと式で検証します。読み終えると、バブルソートを「原理 → 実装 → 最適化 → 特性評価」の流れで一気通貫に説明できるようになります。

バブルソートとは：隣接交換で最大要素を右端へ「浮かび上がらせる」

ドキュメント冒頭の定義をそのまま確認しましょう。「隣接する要素を繰り返し比較して交換することで整列を行う」アルゴリズムであり、その過程が泡が下から上へ浮かび上がる様子に似ていることから、バブルソートと呼ばれます。

このとき 1 回の「バブル処理」は、次の交換操作としてシミュレートできます。

配列の最も左の端から右へ走査する。
隣接する要素の大小を順に比較し、「左要素 > 右要素」であれば両者を交換する。
走査が終わった時点で、最大の要素は配列の最も右端へ移動している。

右端まで到達した要素は「浮かび上がった泡」であり、以降の整列対象から除外されます。ドキュメントではこの 1 回のバブル処理が bubble_operation_step1.png から bubble_operation_step7.png までの 7 コマでアニメーション的に描かれており、「最大の泡が水面に浮かび、残った $n - 1$ 個の要素が水底の未ソート区間に残る」というイメージを視覚化しています。

アルゴリズムの流れ： $n - 1$ 回のバブル処理で整列を完了する

配列の長さを $n$ とすると、バブルソートの手順は次の 4 段階に整理できます。

まず $n$ 個の要素に対して「バブル処理」を行い、配列中の最大要素を正しい位置（右端）へ交換する。
次に残りの $n - 1$ 個の要素に対して「バブル処理」を行い、2 番目に大きい要素を正しい位置へ交換する。
このようにして $n - 1$ 回の「バブル処理」を終えると、大きいほうから $n - 1$ 個の要素がすべて正しい位置へ交換される。
残った 1 つの要素は必ず最小要素なので並べ替える必要がなく、これで配列のソートが完了する。

上の全体図は「1 回のバブル処理で未ソート区間の最大値が灰色の確定区間（浮出水した要素）に追加され、未ソート区間が $[0, i]$ から $[0, i - 1]$ へと縮小していく」ことを示しています。走査対象の長さが 1 つずつ減るため、外側のループは $n - 1$ 回で十分であり、最後の 1 要素は比較対象を持たないのです。

基本実装を読む：未ソート区間 $[0, i]$ を双ループで縮める

ドキュメント本文では {file} タグにより bubble_sort コードへの参照が埋め込まれています。実際のリポジトリの Python 実装（ja/codes/python/chapter_sorting/bubble_sort.py）を完全な形で見てみましょう。

def bubble_sort(nums: list[int]):
    """バブルソート"""
    n = len(nums)
    # 外側のループ：未ソート区間は [0, i]
    for i in range(n - 1, 0, -1):
        # 内側のループ：未ソート区間 [0, i] の最大要素をその区間の最右端へ交換
        for j in range(i):
            if nums[j] > nums[j + 1]:
                # nums[j] と nums[j + 1] を交換
                nums[j], nums[j + 1] = nums[j + 1], nums[j]

コードのコメントにある「未ソート区間は $[0, i]$ 」という表現が、このアルゴリズムの本質です。外側のループ変数 $i$ が右端から 1 ずつ縮小し、内側のループは常に「区間 $[0, i]$ の中で隣接ペアを左から右へ検査して、区間内の最大値を最右端へ運ぶ」役割を担います。交換は nums[j] > nums[j + 1]、すなわち厳密に大きいときだけ行う点に注目してください。ここが後述する「安定ソート」の根拠になります。

この構造は言語を変えても完全に対応しており、リポジトリ内では次の 15 言語すべてに同一ロジックの実装が用意されています。

Python：bubble_sort.py
Java：bubble_sort.java（bubbleSort(int[] nums)）
C++：bubble_sort.cpp（std::swap で交換）
C：bubble_sort.c（配列がポインタに減衰するため int nums[], int size の 2 引数）
Go：bubble_sort.go（多重代入 nums[j], nums[j+1] = nums[j+1], nums[j]）
そのほか C# / Dart / JavaScript / Kotlin / Ruby / Rust / Swift / TypeScript / Zig

たとえば Java 版（bubble_sort.java）は一時変数 tmp を使った 3 ステップの交換、C 版（bubble_sort.c）は配列長を明示的に受け取るシグネチャ、Go 版（bubble_sort.go）は並列代入という違いはありますが、「外側で $i$ を減らす／内側で $[0, i]$ を走査する」という枠組みは完全に一致しています。

flag による効率の最適化：交換ゼロで即終了

ドキュメントの「効率の最適化」節の核心は次の観察です。

ある回の「バブル処理」で交換操作が一度も行われなければ、配列はすでにソート済みであり、結果をそのまま返せる。

そこで、交換が発生したかどうかを記録するフラグ flag を導入し、1 回の内側ループが終わっても flag が立っていなければ break で即座に抜けます。

def bubble_sort_with_flag(nums: list[int]):
    """バブルソート（フラグ最適化）"""
    n = len(nums)
    # 外側のループ：未ソート区間は [0, i]
    for i in range(n - 1, 0, -1):
        flag = False  # フラグを初期化する
        # 内側のループ：未ソート区間 [0, i] の最大要素をその区間の最右端へ交換
        for j in range(i):
            if nums[j] > nums[j + 1]:
                # nums[j] と nums[j + 1] を交換
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                flag = True  # 交換する要素を記録
        if not flag:
            break  # このバブル処理で要素交換が一度もなければそのまま終了

ポイントは 2 つあります。

flag は外側ループの各回の先頭で必ず False に初期化されます（Python では第 25 行、Java では第 32 行）。過去の回の情報を引き継がないためです。
ある回で一度も交換がなければ「どの隣接ペアも既に昇順だった」ことを意味し、以降の回でも交換は発生し得ません。したがって即座に全体のソート完了と判定できます。

この最適化により、入力配列が完全に整列済みのとき最良時間計算量は $O (n)$ に達します。ただしドキュメントも明言するとおり、最悪・平均の時間計算量は依然として $O (n^{2})$ のままです。最適化版は Python の bubble_sort_with_flag のほか、Java の bubbleSortWithFlag、C の bubbleSortWithFlag、Go の bubbleSortWithFlag など、全言語に同名で収録されています。

アルゴリズムの特徴：計算量・空間・安定性の 3 軸で評価する

ドキュメントの最後の節では、バブルソートの特性が次の 3 点に要約されています。

時間計算量は $O (n^{2})$ 、適応的ソート：各回のバブル処理で走査する配列の長さは順に $n-1, n-2, \dots, 2, 1$ であり、その総和は
$(n - 1) + (n - 2) + \cdots + 1 = \frac{(n-1)n}{2}$
です。「適応的（adaptive）」とは、入力の整列度に応じて計算量が変わる性質を指し、flag 最適化を導入した場合の最良（完全整列済み入力）は $O (n)$ 、最悪・平均は $O (n^{2})$ となります。
空間計算量は $O (1)$ 、インプレースソート：ポインタ $i$ と $j$ （および交換用の一時変数）という定数サイズの追加領域しか使いません。入力配列自身を書き換えるため、追加の配列コピーを必要としない点が特徴です。
安定ソート：バブル処理では「等しい要素」に出会っても交換しない（> でのみ交換、>= ではない）ため、同値の要素の相対順序が保たれます。テスト配列に含まれる 2 つの 1 のような重複値でも、出現順序が崩れません。

「適応的」と「安定」という 2 つの性質が両立していることは、実務的にバブルソートを評価する際の重要な観点です。なお、交換回数の最悪ケースは比較回数と同じく $n (n - 1) / 2$ ですが、これはコードの条件分岐を追えば「逆順入力で毎回交換が発生する」ことから導けます（推論であり、ドキュメントの明示記述ではありません）。

実行例で確認する：Driver Code のテスト入力と期待出力

各言語の実装には main / __main__ による Driver Code が添付されており、基本版と最適化版の両方を同じ入力で試せるようになっています。テスト入力は全言語共通で

nums = [4, 1, 3, 1, 5, 2]

です（Python は bubble_sort.py 第 38〜43 行、C は bubble_sort.c 第 45〜56 行）。この配列を昇順に整列した結果は理論上 [1, 1, 2, 3, 4, 5] となり、2 つの 1 の相対順序を崩さないこともこの入力で直接観察できます。

実行方法は言語ごとに異なります。たとえば C は ja/codes/c 配下のビルド体系に従ってコンパイル後に実行、Python は python bubble_sort.py で直接実行し、Java / C++ / Go も各章のビルド手順に沿って Driver Code を走らせることで、基本版と flag 最適化版の出力が同じ整列結果になることを確認できます。実行環境の前提はインストールガイドにまとめられています。

どのような場面に向くのか

計算量と実装の特性から、次のような使い分けが合理的です（これらは特性からの演繹であり、ドキュメント外の主張は含めていません）。

$n$ が小さい配列： $O (n^{2})$ でも定数係数が小さく、実装も単純なため十分実用的です。
ほぼ整列済みのデータ：flag 最適化により最良 $O (n)$ が発揮され、入力の初期状態が良いほど速くなります。
インプレース制約・安定性の要求：追加メモリを使わず、かつ同値要素の順序を保ちたい場合に向きます。
一方、 $n$ が大きい一般データに対しては $O (n \log n)$ 系のマージソート・クイックソート・ヒープソートに劣ります。ソート全般の比較はソートの概要や各章のまとめで体系的に解説されています。

まとめ：バブルソートで学べる 3 つの概念

考え方：「左 > 右なら交換」を右端まで繰り返すと最大値が必ず右端に届く。これを $n - 1$ 回繰り返せば整列完了（bubble_sort.py）。
最適化：交換ゼロの回を検出する flag で早期終了し、完全整列入力では最良 $O (n)$ （bubble_sort_with_flag）。
特性：時間 $O (n^{2})$ ・空間 $O (1)$ ・インプレース・安定・適応的。どれも 10 行にも満たないコードから直接読み取れるため、ソートアルゴリズムの評価指標を学ぶ最初の題材として最適です。