バブルソート

隣同士しか見ないのに、全体が並ぶ

隣り合う2つを比べ、順番が逆なら入れ替える。それを左から右へ繰り返すだけでも、小さい順に並べられます。この方法がバブルソートです。1周では終わらないことがありますが、1周ごとに右端の値が確定します。

大きい値は、隣と入れ替わるたび右へ進みます。左から順に比べるので、その周でまだ並びが決まっていない範囲の最大値が、最後には右端に来ます。

入れ替えでは、元の値を失わない

Pythonでは2つの値を同時に代入できます。

x = 3
y = 8
x, y = y, x
print(x, y)   # 8 3

右側の元の値を使うので、両方を交換できます。1つずつ代入する方法なら、片方を一時変数に退避します。先に x = y としてから y = x とすると、元の3は消え、両方とも8になってしまいます。

1周まわすと、右端が1つ確定する

n件なら1周目は隣同士をn - 1回比べます。次の周は確定した右端を除き、n - 2回です。毎周、まだ確定していない範囲だけを見ます。

隣の2つが等しいなら、入れ替える必要はありません。比較をした回数と、入れ替えた回数は別の数字です。順番が正しい組でも、確かめるための比較は必要です。

入れ替えが0回だった周で終わる

ある周で入れ替えが一度も起きなければ、未確定の範囲もすでに小さい順に並んでいます。残りの周を省けます。最初から整列済みなら、1周のn - 1回の比較で終わり、時間の増え方は O(n) です。

逆順などの最悪の場合には、比較の合計は (n - 1) + … + 1 = n × (n - 1) / 2 です。1000件なら499500回、10000件なら49995000回です。件数が増えるとほぼ2乗で増えるため、最悪計算量は O(n^2) です。

解説

配列をその場で並べ替える方法では、元の配列も変わります。元の順序を残したい場合は、コピーに対して並べ替える必要があります。

例題で確かめる

商品価格が [5, 1, 4, 2, 8] と並んでいます。左から隣同士を比べ、逆なら入れ替えます。

3周目で入れ替えが0回なので終わります。比較は 4 + 3 + 2 = 9 回、入れ替えは 3 + 1 = 4 回です。早く止まらず残りの1回も比較する場合の10回と、区別して数えます。