アルゴリズム紹介pt.1 バブルソート

はじめに

ソートアルゴリズムの基本中の基本である、バブルソートをわかりやすく紹介します！

コード

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        isswapped  = False
        for j in range(1, n - i):
            if arr[j] < arr[j-1]:
                arr[j], arr[j-1] = arr[j-1], arr[j]
                isswapped = True
        if not isswapped:
            break

解説

バブルソートは、隣り合う要素の大小を比較しながら整列をしていきます。バブルソートのアニメーション

まず、引数として配列arrを取得します。

配列の要素数をlen()で取得した後、ループを動かします。以下のコードはループ部分を抜き取ったものです。

for i in range(n):
        isswapped  = False
        for j in range(1, n - i):

最初のループは要素数だけ回します。これにより配列の要素すべてで比較を行うことができます。

そして二つ目のループでは要素数から最初のループの回数を引いた回数まで、1から回します。

最初のループのiは0から始まるため、jを1にしないと、iループ中にi = jとなる場面が生まれ、非効率です。

また、n-iにすることで、交換して整列が済んでいる部分を比較せず次のループに回ることができます。すでに整列をしているところを比較しても、要素が交換されることはないのでその部分をカットしています。

ループの間にあるisswappedは、そのループ内で1度も交換が行われなかった場合、すべての要素が整列しているため、それ以降の無駄なループをカットするためのフラグです。

次に、交換部分を見てみましょう。

	if arr[j] < arr[j-1]:
		arr[j], arr[j-1] = arr[j-1], arr[j]
		isswapped = True
# ---ここまでfor j in range(1, n-i)の中---
if not isswapped:
	break
# ---ここまでfor i in range(n)の中---

arr[j]とそのひとつ前の要素arr[j-1]を比較して、ひとつ前の要素のほうが大きければ交換をしています。

交換後はisswappedを真にすることで、フラグを立たせて交換が行われたことを示します。

以上がバブルソートの動作です！

解析

	オーダー
最悪計算時間	$O(n^2)$
最良計算時間	$O(1)$
平均計算時間	$O(n^2)$

比較回数

このソート中に比較を行う回数は、

\frac {n \cdot (n-1)}{2}

です。

2つ目のループをi回(n回)回しており、2つ目のループがどこまでループするかを見てみると、

回数(i)	n-i
1	n-1
2	n-2
3	n-3
4	n-4
...	...
n	0

となるので、合計すると等差数列の和の公式から、

\begin{split} \displaystyle \sum_{i = 1}^{n-1} (n-i) &=(n-1)+(n-2)+\cdots +1\\ &= \frac {n \cdot (n-1)}{2} \end{split}

となります。そのため計算量Oは $O(n^2)$ となります。

交換回数

交換は隣り合う2つの要素が入れ替える必要があるかないかの2通りなので、確率は1/2であることが分かります。比較のたびにその確率が発生すると仮定すると、

\begin{split} 平均比較回数 &= 比較回数 \times \frac{1}{2}\\ &= \frac {n \cdot (n-1)}{2} \times \frac{1}{2}\\ &= \frac {n \cdot (n-1)}{4} \end{split}

になります。そのため計算量Oは $O(n^2)$ となります。

実行

以下のコードを使用し、100,000個のデータを格納した配列を作成、ソート時間を計測しました。

import time
import random
from python.sort.bubble import bubble_sort

def make_dummy(n=100000):
    return [random.randint(0,65535) for _ in range(n)]

if __name__ == "__main__":
    print(f"Generating 100,000 elements...")
    arr = make_dummy()
    
    print("Start sorting...")
    start = time.time()
    bubble_sort(arr)
    end = time.time()

    print(f"Done! Elapsed time:{end - start:.5f} sec")

実行環境

物	詳細
OS	Windows 11 pro 25H2
CPU	Intel Core Ultra 7 255H
メモリ	32GB
Python	3.14.3
環境	VScode+Terminal

結果

Generating 100,000 elements...
Start sorting...
Done! Elapsed time:225.48860 sec

sort()と比較

同様のコードでbubble_sort()をarr.sort()に置き換えたものの実行時間は以下の通りでした。

Generating 100,000 elements...
Start sorting...
Done! Elapsed time:0.01906 sec

Pythonのsort()はTiｍソートを利用しているため非常に高速であることわかります。

まとめ

計算時間がO(n^2)であるため、非常に時間がかかることが分かりました。しかし、実装が非常にシンプルであることや、安定ソートである点、in-place設計であることなど一応メリットはあります。実用することはほぼないですが、今後のソートを学ぶ際の基礎かつ比較対象として押さえておく必要はあります！

次回は選択ソートです！