バブルソート（Pythonによるアルゴリズムとデータ構造）

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。

今回は、単純な整列アルゴリズムであるバブルソート（Bubble Sort）について学んでいきます。

バブルソートとは
Pythonでバブルソートを実装してみる
動作確認
参考書籍

バブルソートとは

バブルソート（Bubble Sort）とは、リストの最後から先頭に向かってスキャンをしていき、大小を比較した後に、 $n$ 番目の値が $n-1$ 番目の値より小さければ（昇順の場合）入れ替えをします。

バブルソートでは、外側のループと内側のループに分けてスキャンをしていき、外側のループではリストの先頭からリストのサイズ $n-1$ までループし、内側のループではリストの最後から整列済でないインデックスまでをスキャンしていきます。

そのため、バブルソートでは値の小さいものから順番に前へと（泡のように）浮かび上がってくる特徴があることから、このような名前が付いたようです。

また、外側では $n-1$ 回のループ： $O(n)$ 、内側では $\frac{n}{2}$ 回のループ： $O(n)$ 、その他は $O(1)$ のため、 $O(n^2)$ の計算量となります。

なお、バブルソートは安定な整列アルゴリズム（データの位置関係が保存される）となります。

Pythonでバブルソートを実装してみる

それでは、Pythonでバブルソートを実装してみます。

# bubble_sort.py
import time
import pickle

def bubble_sort(lst):
    for i in range(len(lst)-1):
        for j in range(len(lst)-1, i, -1):
            if lst[j-1] > lst[j]:
                tmp = lst[j]
                lst[j] = lst[j-1]
                lst[j-1] = tmp

with open('sample_data.pkl', 'rb') as f:
    lst = pickle.load(f)

start = time.time()
bubble_sort(lst)
print("elapsed {} sec".format(time.time() - start))