バブルソートは、ソートのアルゴリズムの一つ。最悪計算時間がO(n²)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。

バブルソートを高速化したソート法として、シェーカーソートやコムソートが知られている。

アルゴリズム

---

1番目と2番目を比較し、順番が逆であれば入れ換える。次に2番目と3番目を比較して入れ換える。これを最後まで行うと、最後の数だけが最小または最大の数として確定するので、確定していない部分について1つずつ減らしながら繰り返す。

実装例

int data^* = { /* ... */ }; for (i = 0; i < n; i++) { for (j = 1; j < n - i; j++) { if (data- 1 > data^*) swap(data- 1, data^*); } }

動作例

初期データ: 8 4 3 7 6 5 2 1

4 3 7 6 5 2 1 8 （1回目のループ終了時）

3 4 6 5 2 1 7 8 （2回目のループ終了時）

3 4 5 2 1 6 7 8 （3回目のループ終了時）

3 4 2 1 5 6 7 8 （4回目のループ終了時）

3 2 1 4 5 6 7 8 （5回目のループ終了時）

2 1 3 4 5 6 7 8 （6回目のループ終了時）

1 2 3 4 5 6 7 8 （7回目のループ終了時）

計算時間

---

「比較回数」は、n(n-1)/2回。交換回数は、元のデータ列によって異なるが、一回のスキャンで平均n/2回なので、全体では約n²/2回。

ソート

ترتيب الفقاعات | Bubblesort | Bubble sort | Ordenamiento de burbuja | Kuplalajittelu | Tri à bulles | מיון בועות | Buborékrendezés | Bóluröðun | Bubble sort | Burbulo rūšiavimo algoritmas | Bubblesort | Sortowanie bąbelkowe | Bubble sort | Сортировка пузырьком | Bublinkové triedenie | Bubble sort | Сортування стандартним обміном | 冒泡排序