バブルソートとは
- 隣同士の要素を比較して並べ替えるソート手法
- 大きい（または小さい）値が「泡」のように端に移動していく様子から「バブルソート」と呼ばれる
- 特徴
- 計算量は O(n²) と遅い
- 実装が簡単
- 安定ソート（同じ値の順序は保たれる）
- 主に 学習用・教育用で使われ、実用で使われることは少ない
バブルソートの仕組み
バブルソートは、隣り合う要素を比較して入れ替えることを繰り返し、配列を整列していくアルゴリズムです。
下のgifでは、左から順に数を比較し、もし前の値が後ろより大きければ入れ替えています。
1回の操作（パス）が終わると、その時点での最大値が配列の右端に確定します。
そのため、次のパスでは最後の要素を比較する必要はなくなり、1回ごとに比較回数が減っていくのが特徴です。これを繰り返すことで、徐々に小さい値は左へ、大きい値は右へと集まり、最終的に昇順に並び替えられます。
実装コード
def bubble():
array_count = len(array)
for i in range(array_count - 1):
for j in range(array_count - 1 - i):
if array[j] > array[j+1]:
array[j],array[j+1] = array[j+1],array[j]
if __name__ == "__main__":
array = [9,5,6,1,2]
bubble()
print(array)
# [1, 2, 5, 6, 9]
バブルソートの計算量について
バブルソートはとてもシンプルなアルゴリズムですが、計算量は O(n²) と効率が悪いと言われます。
ここでは、なぜそうなるのかを分かりやすく説明します
1回ごとの比較回数
配列の要素数を n とします。
バブルソートでは隣同士を比較して並び替えるため、1回のパス（走査）で次の回数だけ比較します。
1回目 … n-1 回
2回目 … n-2 回
3回目 … n-3 回
…
最後 … 1 回
つまり、比較回数の合計は次のようになります。
(n-1) + (n-2) + ... + 2 + 1
等差数列の和で計算する
これは、1から (n-1) までの和と同じです。
等差数列の和の公式を使うと、
1 + 2 + 3 + ... + (n-1) = (n-1)n / 2
となります。
O(n²) になる理由
上の式を整理すると、
(n-1)n / 2
となり、おおよそ n²/2 です。
計算量を表すビッグオー記法では、定数や 1/2 のような係数は無視するため、最終的に
O(n²)
と表されます。