バブルソート｜コードで実践

バブルソート

このレッスンで分かること

ソートは「データを並べる」だけでなく、その後の 二分探索 や 重複削除 の前処理としても重要

実装が極めて単純で、ソートアルゴリズムを学ぶ最初の題材として定番です

バブルソート (bubble sort) は、隣り合う 2 つの要素を比較し、順序が逆ならば交換 (swap) する操作を繰り返して配列を整列するアルゴリズムです

バブルソートとは

隣り合う要素を比較・交換していくバブルソートを実装し、O(n^2) の整列アルゴリズムを体感する。本レッスンでは、バブルソートの基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

バブルソート (bubble sort) は、隣り合う 2 つの要素を比較し、順序が逆ならば交換 (swap) する操作を繰り返して配列を整列するアルゴリズムです。名前の由来は、大きい値が泡 (bubble) のように配列の末尾へ「浮き上がってくる」ように見えるところから来ています。

実装が極めて単純で、ソートアルゴリズムを学ぶ最初の題材として定番です。一方、計算量は O(n^2) で、n が大きくなると現実的には使えません。Python の sorted() や JS の Array.prototype.sort は O(n log n) のソート (Timsort など) を採用していて、桁違いに速いです。

バブルソートは 教育目的。実戦では sorted() や Array.sort を使う。だが「ループの中でループ」の典型例として理解しておく価値がある。

アルゴリズムの流れ

1 回のパス (外側ループ 1 周) で、配列の末尾に 最大値 が確定します。次のパスでは末尾を除いた範囲で同じことを繰り返し、n - 1 回のパスでソートが完了します。

diagram (will load when visible)

図のポイント (テキスト併記)

各パスで隣接ペアを左から右へ全部比較するので、内側ループは最大 n - 1 回まわります

各パスで隣接ペアを左から右へ全部比較するので、内側ループは最大 n - 1 回まわります。合計 n(n-1)/2 回の比較となり、最高次の項を取って O(n^2) です。

Python での実装例

Python

def bubbleSort(arr):
    a = list(arr)
    n = len(a)
    for i in range(n):
        for j in range(n - i - 1):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return a

入力配列を破壊しないよう、list(arr) でコピーしてから処理します。Python では a, b = b, a で簡単に swap できます。

JavaScript での実装例

JavaScript

function bubbleSort(arr) {
  const a = [...arr];
  const n = a.length;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (a[j] > a[j + 1]) {
        const tmp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = tmp;
      }
    }
  }
  return a;
}

[...arr] でスプレッド演算子を使ってコピーします。swap には一時変数 tmp を使うか、[a[j], a[j+1]] = [a[j+1], a[j]] の分割代入も使えます。

計算量

比較回数は最悪・平均・最良すべて O(n^2) です (最良ケースで O(n) にする最適化版もありますが、ここでは素朴な実装で考えます)。n = 1000 で 約 50 万回 程度の比較、n = 10000 で 約 5000 万回 になるので、扱える n の上限は 数万 程度です。

O(n^2) のソートは小さな配列でしか使えない。O(n log n) のマージソートやクイックソートを覚えるのが次のステップ。

よくある間違い

1 つ目は 内側ループの範囲を n で固定する こと。for j in range(n - 1) でも動きますが、n - i - 1 にすれば既に確定した末尾を再比較せずに済み、無駄が減ります。

2 つ目は 入力配列を破壊する こと。問題の仕様によっては元の配列を変更してはいけないので、コピーしてから処理するのが安全です。

3 つ目は swap を間違える こと。Python の a[j], a[j+1] = a[j+1], a[j] は同時代入なので問題なく動きますが、tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp を間違えて a[j] = a[j+1]; a[j+1] = a[j] と書くと値が両方とも a[j+1] の値になります。

やってみよう

[5, 2, 4, 6, 1, 3] をソートして [1, 2, 3, 4, 5, 6] が返ることを確認する。
既にソート済みの配列を渡してみる。素朴な実装でも結果は変わらず正しい。
n = 100 と n = 1000 で時間を比べてみる。n を 10 倍すると 100 倍遅くなるのを実感できる。

ソートは「データを並べる」だけでなく、その後の 二分探索 や 重複削除 の前処理としても重要。

Go での実装

func bubbleSort(arr []int) []int {
    a := make([]int, len(arr))
    copy(a, arr)
    n := len(a)
    for i := 0; i < n; i++ {
        for j := 0; j < n-i-1; j++ {
            if a[j] > a[j+1] {
                a[j], a[j+1] = a[j+1], a[j]
            }
        }
    }
    return a
}

Go でも 2 重ループの構造はまったく同じです。a, b = b, a のような同時代入 (swap) が言語仕様で使えるのが嬉しいポイントです。

早期終了の最適化

素朴なバブルソートは常に O(n^2) ですが、「あるパスで一度も swap が起きなかった = もうソート済み」というフラグを追加すれば、ソート済みの配列に対しては O(n) で終了できます。最良ケースの計算量を O(n) に改善する小ワザですが、最悪計算量はやはり O(n^2) のままです。

アルゴリズムの最適化は 最良 / 平均 / 最悪 のどこを改善しているかを意識すると、効果を測りやすい。

安定ソートとしての性質

バブルソートは 安定 (stable) なソートです。安定とは「等しい値の相対順序が保たれる」性質で、[("a", 1), ("b", 1)] をキー 1 でソートしても順序が ("a", 1), ("b", 1) のまま入れ替わらないことを意味します。複数キーでのソートや、データベースの ORDER BY の組み合わせで重要になります。一方、クイックソートやヒープソートは標準的には不安定です。

よくある質問

Q. バブルソートとクイックソートはどっちが速い？

A. ほぼ常にクイックソートの方が高速です。バブルソートは O(n²)、クイックソートは平均 O(n log n) です。バブルソートはアルゴリズムの学習用で、実務では Arrays.sort（Java）や sorted（Python）の内部実装（TimSort 等）を使います。

Q. バブルソートを早期終了させるには？

A. 1 周回中に交換が 1 度も無ければソート済みなので break で抜けられます。最良ケースが O(n) に改善し、ほぼソート済みの配列で効果を発揮します。実装は swapped フラグを毎周回リセットするだけで簡単です。

Q. 安定ソートとは何ですか？

A. 同じキー値の要素同士の元の順序が保たれるソートです。バブルソート・マージソート・TimSort は安定、クイックソート・ヒープソートは一般に不安定です。複数キーでソートする場合（学年→名前順）に違いが効いてきます。

次のレッスン

次は 配列の最大と最小 に進みましょう。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

バブルソートの要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. バブルソートとは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

バブルソート