バブルソート実装
バブルソート実装
このレッスンで分かること
- バブルソートは「隣を見て、必要なら交換する」を最後まで繰り返すだけ
安定ソートで、in-place(追加メモリ不要)、実装が短い、そして何より「ソートとは何か」を直感的に説明できる、教育用としては最良のアルゴリズムです- 配列を小さい順に並べ替える最も素朴な方法が
バブルソートです
バブルソート実装 とは
隣接する要素を比較・交換していくバブルソートを実装し、整列アルゴリズムの基本動作と計算量を学ぶ。本レッスンでは、バブルソート実装 の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。
配列を小さい順に並べ替える最も素朴な方法が バブルソート です。隣り合う要素を見比べ、左 > 右 なら入れ替える、これを端から繰り返すだけ。1 周終わると、最大値が末尾まで 浮かび上がる 動きが「泡」に似ているのが名前の由来です。
安定ソート で、in-place (追加メモリ不要)、実装が短い、そして何より「ソートとは何か」を直感的に説明できる、教育用としては最良のアルゴリズムです。一方で実行効率は O(n^2) と遅く、本番コードで使うことはまずありません。それでも仕組みを手で書ける状態にしておくと、後続の 挿入ソート 選択ソート マージソート がぐっと理解しやすくなります。
バブルソートは「隣を見て、必要なら交換する」を最後まで繰り返すだけ。難しい再帰や分割は要らない。
動作のイメージ
[5, 1, 4, 2, 8] をソートしてみましょう。
1 周目で隣同士を比較すると [1, 4, 2, 5, 8] のように 8 が末尾に到達します。2 周目で [1, 2, 4, 5, 8] となり完了です。各ラウンドで「最も大きい未確定要素が右端へ確定する」ので、n - 1 回のラウンドで必ず整列します。
図のポイント (テキスト併記)
-
各ラウンドで「右端から 1 つずつ確定」していくため、内側ループの終端を
n - 1 - iまで縮められる
各ラウンドで「右端から 1 つずつ確定」していくため、内側ループの終端を
n - 1 - iまで縮められる。
Python での実装
Python
def bubbleSort(arr):
a = list(arr)
n = len(a)
for i in range(n - 1):
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
return alist(arr) で入力をコピーしてから操作するのが安全です。a[j], a[j + 1] = a[j + 1], a[j] の タプル代入 で 1 行スワップになるのが Python らしい書き方。
JavaScript での実装
JavaScript
function bubbleSort(arr) {
const a = [...arr];
const n = a.length;
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
[a[j], a[j + 1]] = [a[j + 1], a[j]];
}
}
}
return a;
}JS では [...arr] でコピー、[a, b] = [b, a] の分割代入でスワップします。
計算量と最適化
比較回数は最悪 n * (n - 1) / 2、計算量は O(n^2)。n が 100 なら問題なくても、100000 だと 100 億回 の比較になり実用に耐えません。
軽い最適化として「1 周の中で 1 度も交換しなかったら、すでに整列済み」というフラグ判定があります。ほぼ整列した配列なら O(n) まで縮みます。
バブルソートは
O(n^2)。実務で大きな配列を扱うならクイックソートやマージソートを使うこと。
よくある間違い
1 つ目は 内側ループの範囲ミス。for j in range(n) のまま回すと a[j + 1] で範囲外アクセスになります。必ず n - 1 まで。2 つ目は 入力配列を破壊的に書き換える こと。受け取った arr をそのまま並べ替えると呼び出し側に副作用が出ます。コピーしてから操作するのが安心です。3 つ目は 不等号の向き。降順にしたいときは < を使います。条件を逆にしたつもりが等号入りになって安定性が崩れることもあります。
やってみよう
[3, 3, 2, 1]を入れて結果を確認する。安定性をチェックするには同じ値を区別できる構造にして実験する。- 早期終了フラグを追加して、整列済み配列で
比較回数がどれだけ減るか計測する。 - 降順バブルソートも書いてみる。条件式の
>を<に変えるだけ。
早期終了フラグの実装
「1 周中に 1 度も交換しなかった」場合、配列はすでに整列済みです。フラグでこれを検出して早期終了させると、ほぼ整列済みの入力で O(n) まで縮みます。
Python
def bubbleSortOptimized(arr):
a = list(arr)
n = len(a)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not swapped:
break
return aswapped フラグが立たないまま 1 周を終えたら break。整列済みの配列を入れると 1 周だけで終わるので比較は n - 1 回、計算量は O(n) です。
バブルソートの歴史
バブルソートは 1956 年の論文で初めて議論された古典中の古典です。1962 年には Cocktail Shaker Sort (左右に振り子のように往復するバリエーション) が提案され、最悪計算量は同じものの 特定の入力では速い という研究もありました。教育的価値が高い一方、計算機科学の大家 Knuth は「バブルソートは教材としてしか価値がない」と評しています。それでも ソートとは何か を 1 番ストレートに教えてくれるアルゴリズムであることは間違いありません。
実務ではほぼ使われないが、ソートの概念を初めて学ぶならバブルソートから入るのが王道。
よくある質問
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 セクションを読み返してみましょう。
関連レッスン
要件
- 組み込みのソート関数 (Python の sorted, JS の sort, Go の sort.Slice) は使わない
- 隣接要素を比較・交換するバブルソートで実装する
- 戻り値は新しい配列で、入力 arr を破壊的に書き換えない
入出力例
test-cases.txt
bubbleSort([5,1,4,2,8]) → [1,2,4,5,8]
bubbleSort([1,2,3,4,5]) → [1,2,3,4,5]
bubbleSort([5,4,3,2,1]) → [1,2,3,4,5]
bubbleSort([3,1,3,2,1]) → [1,1,2,3,3]
bubbleSort([42]) → [42]
bubbleSort([-3,5,0,-1,2]) → [-3,-1,0,2,5]