バブルソート
バブルソートは隣り合う要素を比較し、逆順なら交換する整列アルゴリズムです。1回の走査で未整列部分の最大値が末尾に移ります。平均・最悪時間は O(n²)、追加空間は O(1) です。交換のない走査で終了する最適化版は、最良時間が O(n) になります。
大きい値は、左から右への走査に乗って何度も右へ動けます。小さい値が左へ動けるのは、同じ走査中に1回だけです。最小値を末尾に置くと、先頭へ届くまで n − 1 回の走査が必要です。
バブルソートの仕組み
外側のループは i = 0 から n - 2 まで、内側は j = 0 から n - 2 - i まで進みます。arr[j] > arr[j + 1] なら、この2要素を交換します。
位置 j の比較が終わると、arr[j + 1] は arr[0..j + 1] の最大値になります。交換した場合は左にあった大きい値が右へ移り、交換しない場合は右の値が最大値を引き継ぎます。アニメーションの max はこの値を示します。
走査が終わると、未整列部分の最大値が最終位置に届きます。第 i 回の後では、末尾の i + 1 個が確定済みです。次の走査は1要素手前で止まります。緑の領域と区切り線が、この境界を表します。
通常版（Classic）は必ず n − 1 回走査します。最適化版（Optimized）は各走査の前に swapped = false とし、交換時に true にします。走査後も false なら、すべての隣接要素が順序どおりなので終了します。比較と交換の規則は両版で同じです。
バブルソートのステップ
既定の通常版は [24, 38, 12, 45, 19, 31, 7] を使います。7 は添字6から、1回の走査につき1つずつ左へ進みます。
第1回は6比較です。24 ≤ 38 は交換せず、38 > 12 は交換します。38 ≤ 45 の後は45が最大値となり、19、31、7を越えます。4交換後の配列は [24, 12, 38, 19, 31, 7, 45]。45が添字6で確定し、7は添字5に移ります。
第2回は5比較です。24と12を交換し、24と38はそのままにします。38が19、31、7を越えると、[12, 24, 19, 31, 7, 38, 45] になります。末尾の [38, 45] が確定済みです。
第3〜6回は31、24、19、12を確定します。7は添字4から3、2、1、0へ移動します。結果は [7, 12, 19, 24, 31, 38, 45]。合計6走査、21比較、13交換です。
最適化版へ切り替えると、入力は [30, 12, 23, 47, 58, 76, 91] になります。第1回で30が12と23を越え、[12, 23, 30, 47, 58, 76, 91] になります。第2回の5比較では交換せず、swapped が false のままなので終了します。合計11比較、2交換です。第3〜6回は実行しません。
j と j + 1 は比較中の2要素を示します。通常版では走査ごとに緑の領域が1つ増えます。最適化版が交換なしで走査を終えた場合は、行全体が緑になります。
時間・空間計算量
| 場合 | 通常版 | 最適化版 |
|---|---|---|
| 最良：整列済み | O(n²) | O(n) |
| 平均 | O(n²) | O(n²) |
| 最悪：逆順 | O(n²) | O(n²) |
通常版の比較回数は入力順序によらず、次の総和になります。
(n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2
7要素なら 6 + 5 + 4 + 3 + 2 + 1 = 21 比較です。初期順序が変えるのは交換回数です。
整列済み入力では、最適化版は最初の n − 1 比較で終了します。逆順では毎比較で交換するため、7要素なら両版とも21比較、21交換です。最適化版も最悪時間は O(n²) です。
別の配列は作らず、交換用変数だけを使うので追加空間は O(1) です。条件を > にすると同じ値を交換しないため、安定性を保てます。
境界条件
- 1要素：
[42]は隣接ペアを持たず、走査せずに終了します。 - 整列済み：
[12, 23, 30, 47, 58, 76, 91]は最適化版で6比較、0交換です。 - ほぼ整列済み：
[12, 23, 30, 47, 58, 91, 76]は第1回に1交換、第2回に交換なし。11比較で終了します。 - 逆順：
[91, 76, 58, 47, 30, 23, 12]は21比較すべてで交換します。 - 全要素が同じ：5個の42なら最適化版は4比較で終了し、元の順序を保ちます。
よくある間違い
- 内側のループ範囲を誤る：条件は
j < n - 1 - iです。1つ多いと配列外や確定済み領域を比較し、1つ少ないと最大値が末尾まで届きません。 swappedの更新時点を誤る：走査前にリセットし、走査後に判定します。ループ全体の前だけでリセットすると、以前の交換記録が残ります。走査中に終了判定すると、1組の順序だけで配列全体を判断してしまいます。- 交換前の値を上書きする：多重代入を使わない言語では、元の左値を一時変数へ保存します。
- 比較を
>=にする：値は整列しても、同じ値が互いを越えて安定性が失われます。 - 最適化版を常に O(n) とする：O(n) は最良時だけです。平均・最悪は O(n²) のままです。