バブルソート
最終更新
バブルソートはリストを繰り返し走査し、隣り合う各要素のペアを比較して、順序が誤っていれば交換します。1回の完全なパスごとに、残りの最大値が末尾の正しい位置へ「浮かび上がる」ため、各パスは1つ少ない要素だけを見ればよくなります。上の再生を押して比較と交換を観察するか、1ステップずつ進めてください。
最も理解しやすいソートアルゴリズムの1つで、最初に学ぶアルゴリズムとして優れています。ただし実行時間が O(n²) のため、大きな入力には実用的ではありません。
時間計算量と空間計算量
| ケース | 計算量 | 備考 |
|---|---|---|
| 最良ケース | O(n) | すでにソート済み、早期終了チェックあり |
| 平均ケース | O(n²) | ランダムな順序 |
| 最悪ケース | O(n²) | 逆順にソート済み |
| 空間 | O(1) | インプレース、一時変数のみ |
| 安定 | はい | 等しい要素は相対順序を保つ |
ステップごとの説明
| ステップ | 何が起こるか |
|---|---|
| 1 | 配列の先頭から始める。 |
| 2 | 現在の要素を次の要素と比較する。 |
| 3 | 順序が誤っていれば交換する。 |
| 4 | 1つ右へ進め、末尾まで繰り返す（1回のパス）。 |
| 5 | パスを繰り返す。各パスで末尾の要素がもう1つ確定する。 |
| 6 | 完全な1パスで交換が起きなくなったら停止する。 |
具体例
[5, 2, 4, 1] をソートする場合：
| パス | 配列 | 動作 |
|---|---|---|
| 1 | [2, 4, 1, 5] | 5,2、次に 5,4、次に 5,1 を交換。5 が末尾へ浮かび上がる。 |
| 2 | [2, 1, 4, 5] | 2,4 は正しい順序。4,1 を交換。4,5 は正しい順序。4 が確定する。 |
| 3 | [1, 2, 4, 5] | 2,1 を交換。残りはすでに正しい順序。2 が確定する。 |
| 4 | [1, 2, 4, 5] | 完全な1パスで交換が起きないため、配列はソート済みでアルゴリズムは停止する。 |
バブルソートを使うべき場面
| 使うべきとき | 避けるべきとき |
|---|---|
| 比較ソートの仕組みを教える、または学ぶとき | O(n²) が遅すぎる大きな入力をソートするとき |
入力がごく小さい、またはほぼソート済みのとき（早期終了で O(n) に近づく） | 最速の汎用ソートが必要なとき — quicksort や merge sort を使う |
| ほとんどコードを書かずに安定でインプレースなソートが欲しいとき | データがランダムな順序で、性能が重要なとき |
| 短いリストが1パスですでにソート済みかを検出するとき | 書き込み回数が多いとコストが高いとき（例：フラッシュメモリ）。選択ソートの方が交換が少ない |
Bubble Sortのコード
Python, JavaScript, Java, C++, Cによるクリーンで実行可能なBubble Sortの実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。
PythonでのBubble Sortのコード
Python
1def bubble_sort(a):2 n = len(a)3 for i in range(n - 1):4 swapped = False5 for j in range(n - 1 - i):6 if a[j] > a[j + 1]:7 a[j], a[j + 1] = a[j + 1], a[j]8 swapped = True9 if not swapped:10 break # no swaps means the list is already sorted11 return a12
13
14nums = [5, 1, 4, 2, 8]15print("Before:", nums)16bubble_sort(nums)17print("After: ", nums)JavaScriptでのBubble Sortのコード
JavaScript
1function bubbleSort(a) {2 for (let end = a.length - 1; end > 0; end--) {3 let swapped = false;4 for (let j = 0; j < end; j++) {5 if (a[j] > a[j + 1]) {6 [a[j], a[j + 1]] = [a[j + 1], a[j]];7 swapped = true;8 }9 }10 if (!swapped) break; // Already sorted: stop early11 }12 return a;13}14
15const data = [5, 2, 9, 1, 7, 3];16console.log("Before:", data);17console.log("Sorted:", bubbleSort([...data]));JavaでのBubble Sortのコード
Java
1import java.util.Arrays;2
3public class Main {4 static void bubbleSort(int[] arr) {5 for (int i = arr.length - 1; i > 0; i--) {6 boolean swapped = false;7 for (int j = 0; j < i; j++) {8 if (arr[j] > arr[j + 1]) {9 int tmp = arr[j];10 arr[j] = arr[j + 1];11 arr[j + 1] = tmp;12 swapped = true;13 }14 }15 if (!swapped) break; // already sorted16 }17 }18
19 public static void main(String[] args) {20 int[] arr = {5, 1, 4, 2, 8, 3};21 System.out.println("Before: " + Arrays.toString(arr));22 bubbleSort(arr);23 System.out.println("After: " + Arrays.toString(arr));24 }25}C++でのBubble Sortのコード
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10void bubbleSort(std::vector<int>& a) {11 for (size_t pass = 0; pass + 1 < a.size(); ++pass) {12 bool swapped = false;13 // Each pass bubbles the largest remaining value to the end14 for (size_t j = 0; j + 1 < a.size() - pass; ++j) {15 if (a[j] > a[j + 1]) {16 std::swap(a[j], a[j + 1]);17 swapped = true;18 }19 }20 if (!swapped) break; // already sorted21 }22}23
24int main() {25 std::vector<int> data = {5, 1, 4, 2, 8, 3};26 std::cout << "Before: ";27 printVec(data);28 bubbleSort(data);29 std::cout << "After: ";30 printVec(data);31 return 0;32}CでのBubble Sortのコード
C
1#include <stdbool.h>2#include <stdio.h>3
4void printArr(const int a[], int n) {5 for (int i = 0; i < n; i++) printf("%d ", a[i]);6 printf("\n");7}8
9void bubbleSort(int a[], int n) {10 for (int pass = 0; pass < n - 1; pass++) {11 bool swapped = false;12 // Each pass bubbles the largest remaining value to the end13 for (int j = 0; j < n - 1 - pass; j++) {14 if (a[j] > a[j + 1]) {15 int tmp = a[j];16 a[j] = a[j + 1];17 a[j + 1] = tmp;18 swapped = true;19 }20 }21 if (!swapped) break; // already sorted22 }23}24
25int main(void) {26 int data[] = {5, 1, 4, 2, 8, 3};27 int n = sizeof(data) / sizeof(data[0]);28 printf("Before: ");29 printArr(data, n);30 bubbleSort(data, n);31 printf("After: ");32 printArr(data, n);33 return 0;34}バブルソートのよくある質問
バブルソートの時間計算量はどのくらいですか？
バブルソートは入れ子ループのため、平均ケースと最悪ケースで
O(n²) の時間で実行されます。早期終了の最適化を使えば、すでにソート済みの配列で O(n) に達することができます。追加空間は O(1) です。バブルソートは安定ですか？
はい。バブルソートは隣り合う要素を厳密に順序が誤っているときだけ交換するため、等しい要素が互いを追い越すことはなく、元の相対順序を保ちます。
なぜバブルソートと呼ばれるのですか？
各パスで、未ソートの最大値が泡が水面へ浮かび上がるように一歩ずつ配列の末尾へ移動するため、「バブル（泡）」ソートと呼ばれます。
バブルソートと挿入ソートの違いは何ですか？
どちらも
O(n²) で実行され、安定かつインプレースですが、データの動かし方が異なります。バブルソートは順序が誤った隣接ペアを繰り返し交換し、挿入ソートは各要素を取り出してソート済みの前半部分の正しい位置へ滑り込ませます。挿入ソートは通常書き込み回数が少なく、特にほぼソート済みのデータでは実際に高速です。quicksort ではなくバブルソートを使うべきなのはいつですか？
実際のワークロードではほぼありません。quicksort の平均時間
O(n log n) は、ごく小さな入力を除けばバブルソートの O(n²) を圧倒します。バブルソートが役立つのは、リストが非常に小さいかほぼソート済みのとき、または教育目的で可能な限り単純な安定ソートが欲しいときだけです。早期終了の最適化はバブルソートの最悪ケースを変えますか？
いいえ。パスで交換が起きたかを記録すると、バブルソートは早く停止でき、すでにソート済みの入力で
O(n) に達しますが、逆順にソートされた配列は依然としてすべての比較が必要なため、最悪ケースは O(n²) のままです。この最適化は最良ケースとほぼソート済みのケースにのみ役立ちます。関連リソース
その他の可視化
