バブルソート
隣同士しか見ないのに、全体が並ぶ
並べ替えというと、全体を見渡していちばん小さいものを探して、という手順を思い浮かべます。ところが 隣り合う 2 つだけを見て、順番が逆なら入れ替える という操作を繰り返すだけでも、配列はきちんと並びます。視野は常に 2 つ分しかないのに、全体が整っていくところが面白いところです。
その代わり、1 周では終わりません。何周も往復することになり、その周の数が O(n^2) の正体です。
入れ替えは、退避してから
2 つの値を入れ替える書き方から確認します。
Python
x = 3
y = 8
x, y = y, x
print(x, y) # 8 3Python や Go は同時代入で 1 行です。JavaScript や Java では一時変数を経由します。ここでうっかり x = y を先に書くと x の元の値が上書きされて消え、両方が 8 になります。入れ替えは必ず「片方を退避してから」です。
1 周まわすと、右端が 1 つ確定する
[5, 1, 4, 2, 8] を左から隣同士で比べ、逆なら入れ替えます。1 周終わると、いちばん大きい 8 が右端に来ています。2 周目は、確定した右端を除いた範囲でやり直します。
| 周 | 終わったときの並び | 入れ替えた回数 |
|---|---|---|
| 1 周目 | 1 4 2 5 8 | 3 |
| 2 周目 | 1 2 4 5 8 | 1 |
| 3 周目 | 1 2 4 5 8 | 0 |
見てほしいのは右の列です。3 回、1 回、0 回と減っています。周を重ねるほど並びが整っていくので、入れ替える必要そのものが減っていきます。逆に、最初から並んでいる配列を渡すと、1 周目からいきなり 0 回です。まったく逆順の配列なら、毎周ずっと入れ替え続けることになります。
入れ替えが 0 だった周が、終わりの合図
入れ替えが 1 度も起きなかったということは、隣同士がすべて正しい順序だったということです。それはもう並び終わっている、という意味に他なりません。
Python
swapped = False
# 1 周のあいだに 1 度でも入れ替えたら swapped = True にする
if not swapped:
print("もう並んでいる")この見張りを 1 つ足すだけで、ほぼ並んでいる配列からは早く抜けられます。ただし比べる回数は減りません。1 周目に n - 1 回、2 周目に n - 2 回と比べていくので、最悪の合計は次のようになります。
Python
n = 5
print(n * (n - 1) // 2) # 10n = 1000 なら約 50 万回、n = 10000 なら約 5000 万回です。入れ替えは減っても、比べる回数は 2 乗で増え続けます。
渡された配列をその場で並べ替えてよいかは、先に決めてください。手元で書き換えると、呼び出した側が持っている配列も一緒に変わります。
要件
- バブルソート (隣接要素を比較・交換) のロジックで実装すること
- 組み込みの sorted() や Array.prototype.sort は使わない
- 戻り値は昇順に並んだ配列
入出力例
bubbleSort([5,2,4,6,1,3]) → [1,2,3,4,5,6]
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,2,3,1]) → [1,1,2,3,3]
bubbleSort([7]) → [7]
bubbleSort([2,1]) → [1,2]ヒント
