今回はPythonにおけるバブルソートの実装方法と、使いどころについてまとめていきます。

Bubble Sortとは

バブルソートといえば、かのバラク・オバマ大統領がGoogleのCEOのソートに関する質問に対して「バブルソートは間違ったやり方だろう」と答えたことで有名なアルゴリズムです。

実際に計算量が多いことが欠点とされていますが、非常に分かりやすい、というメリットがあり、覚えておいて損はないでしょう。

バブルソートの考え方

バブルソートですが、隣接する値を比較して順番通りに並べる、というアルゴリズムです。

例えば以下のような数値のリストがあるとします。

[32, 1, 9, 6]

Bubble Sortではまず最初の32と1を比較して、もし左側の数字が大きければ値を入れ替えます。

# 1回目 32と1を比較　入れ替え
[1, 32, 9, 6]

このようになります。

これをひたすら繰り返していきます。

# 2回目 32と9を比較　入れ替え
[1, 9, 32, 6]
# 3回目 32と6を比較　入れ替え
[1, 9, 6, 32]
# 4回目 最初に戻って1と9を比較　変更なし
[1, 9, 6, 32]
# 5回目 9と6を比較　入れ替え
[1, 6, 9, 32]

このように順番に並び替えを実施していくのがバブルソートのアルゴリズムです。

コードでの実装

実際にBubble SortをPythonで実施してみましょう。

単純に行うと以下のようになります。

def bubble_sort(a_list):
    loop_size = len(a_list) - 1
    # ループサイズ分繰り返す
    for i in range(loop_size):
        # さらに繰り返す
        for j in range(loop_size):
            # もし左の方が大きければ入れ替える
            if a_list[j] > a_list[j + 1]:
                a_list[j], a_list[j + 1] = a_list[j + 1], a_list[j]
    return a_list


my_list = [32, 1, 9, 6]
my_list = bubble_sort(my_list)

理論上、配列の要素数-1の乗数で計算が完了します。

性能を良くする

上記の例はmaxで繰り返した場合で、この関数は性能を良くする余地があります。

例えば最初のiのループを繰り返した時点で必ず一番大きい数字が一番右に来ます。

上のリストの例ですと…

[1, 9, 6, 32]

この状態になっているということですね。

なので、最後の6と32はそもそも比べる必要がないのです。

同様にiのループを進めていくと、次々に大きい数字が右に寄りますので、応じてjのループを減らしていけます。

以下のように書けます。

def bubble_sort_2(a_list):
    loop_size = len(a_list) - 1
    for i in range(loop_size):
        # 最初のiループを実行したら[1, 9, 6, 32]と、必ず一番大きい数字が右端にくる
        # indexの2番目、つまり9まで繰り返して比較すればいい
        # 2回目以降も同じ原理でjのループを減らせる
        for j in range(loop_size - i):
            if a_list[j] > a_list[j + 1]:
                a_list[j], a_list[j + 1] = a_list[j + 1], a_list[j]
    return a_list

これで計算量を減らせました。

ただし、この方法ですと整列が終わっているのに、処理を実行してしまうという無駄も残っています。

なので、入れ替えが一度も行われなかったら配列をリターンして抜けるようにします。

def bubble_sort_3(a_list):
    loop_size = len(a_list) - 1
    for i in range(loop_size):
        # 入れ替えされてないフラグ
        no_swaps = True
        for j in range(loop_size - i):
            if a_list[j] > a_list[j + 1]:
                a_list[j], a_list[j + 1] = a_list[j + 1], a_list[j]
                no_swaps = False
        # 入れ替えされてなかったらととのっているので終了
        if no_swaps:
            return a_list
    return a_list

これはほとんど整列されているリストをソートするときに顕著な違いがでます。

import time

# ほとんど整列されているデータ
my_list = [i for i in range(0, 5000)]
my_list.insert(100, 0)
my_list.insert(200, 0)

# 通常のバブルソート
_my_list = my_list.copy()
start = time.time()
bubble_sort(_my_list)
print('1:', time.time() - start)
_my_list.clear()

# jループを減らしたバブルソート
_my_list = my_list.copy()
start = time.time()
bubble_sort_2(_my_list)
print('2:', time.time() - start)
_my_list.clear()

# さらに途中で抜けるバブルソート
_my_list = my_list.copy()
start = time.time()
bubble_sort_3(_my_list)
print('3:', time.time() - start)
>>>
1: 1.2833428382873535
2: 0.6306445598602295
3: 0.04900002479553223

ただしバラバラなデータの場合はif文の数だけロスが出るようです。

import time
import random

# ランダムなデータ
my_list = [random.randrange(0, 10000) for i in range(0, 5000)]
# ...省略
>>>
1: 1.8538780212402344
2: 1.1759812831878662
3: 1.1987555027008057

Pythonの組み込みソート

色々と書いてきたんですが、Pythonの組み込みソートの方が圧倒的に速いです。

同じ10,000件のデータで比較してみましょう。

_my_list = my_list.copy()
start = time.time()
_my_list.sort()
print('4:', time.time() - start)
print(_my_list)
>>>
1: 1.8457536697387695
2: 1.1669673919677734
3: 1.1874911785125732
4: 0.0

このように組み込みのソートでは、全く時間がかからずに終わりました。

バブルソートの使いどころ

上で書いたように組み込みのソートの方が圧倒的に速いので、通常はそちらを使えばいいでしょう。

思いつくところでは、特殊な基準でソートするときの最後の仕上げなどで使いどころがあるかもしれません。

例えば以下のようなデータがあったとします。

discography = [
    {'title': 'しばたさとこ島', 'price': 2000, 'release': 2012},
    {'title': 'いじわる全集', 'price': 2300, 'release': 2014},
    {'title': 'SHIBATA SATOKO LIVE SOUVENIR', 'price': 4000, 'release': 2015},
    {'title': '柴田聡子', 'price': 2400, 'release': 2015},
    {'title': '愛の休日', 'price': 2593, 'release': 2017},
    {'title': 'がんばれ！メロディー', 'price': 2593, 'release': 2019},
    {'title': 'ぼちぼち銀河', 'price': 3000, 'release': 2022},
]

柴田聡子さんのアルバムのタイトル、値段、リリース年を記録したディスコグラフィーデータです。

これを例えば、値段が安い順、値段が同じ場合はリリース年が新しい方を上にする、といった要件があったとします。

まずは値段が安い順でソートをかけます。ここはPythonの組み込みの機能です。

discography.sort(key=lambda x: x['price'])
print(discography)
>>>
[{'title': 'しばたさとこ島', 'price': 2000, 'release': 2012},
 {'title': 'いじわる全集', 'price': 2300, 'release': 2014},
 {'title': '柴田聡子', 'price': 2400, 'release': 2015},
 {'title': '愛の休日', 'price': 2593, 'release': 2017},
 {'title': 'がんばれ！メロディー', 'price': 2593, 'release': 2019},
 {'title': 'ぼちぼち銀河', 'price': 3000, 'release': 2022},
 {'title': 'SHIBATA SATOKO LIVE SOUVENIR', 'price': 4000, 'release': 2015}]

愛の休日とがんばれ！メロディーの値段が同じですが、がんばれ！メロディーの方がリリースが新しいので入れ替えをする必要があります。

例えばこういう時にbubbleソートでリリース年のみを比較して仕上げを行います。

def discography_bubble_sort(data):
    loop_size = len(data) - 1
    for i in range(loop_size):
        no_swaps = True
        for j in range(loop_size - i):
            disc = data[j]
            disc_2 = data[j + 1]
            # リリース年の比較
            if disc['price'] == disc_2['price']:
                if disc['release'] < disc_2['release']:
                    data[j], data[j + 1] = data[j + 1], data[j]
                    no_swaps = False
        if no_swaps:
            return data
    return data


print(discography_bubble_sort(discography))
>>>
[{'title': 'しばたさとこ島', 'price': 2000, 'release': 2012},
 {'title': 'いじわる全集', 'price': 2300, 'release': 2014},
 {'title': '柴田聡子', 'price': 2400, 'release': 2015},
 {'title': 'がんばれ！メロディー', 'price': 2593, 'release': 2019},
 {'title': '愛の休日', 'price': 2593, 'release': 2017},
 {'title': 'ぼちぼち銀河', 'price': 3000, 'release': 2022},
 {'title': 'SHIBATA SATOKO LIVE SOUVENIR', 'price': 4000, 'release': 2015}]

意図していた通りに並び替えがされました。

おわりに

上記のケースですと、組み込みのソートで一発で行うことも可能です。

discography.sort(key=lambda x: (x['price'], -x['release']))

ただ、いつか組み込みのソートでは対応できない、複雑な比較を要する要件があるかもしれません。

冒頭で書いた通り、バブルソートは速度は遅いものの、非常に分かりやすい形で実装ができるところにメリットがあります。

引き出しの一つとして覚えておいて損はないでしょう。