【Python】ソートの復讐１：バブルソート

ソートの復習用の記事です。

最初なので実装も簡単なバブルソートについて書きます。

ひとまず結論

• 最悪・平均計算量： O(n²)
• Pythonでの実装例

def bubble_sort(input_arr):
    len_arr = len(input_arr)
    update_flag = True
    while update_flag:
        update_flag = False
        for i in range(1,len_arr):
            if input_arr[i-1] > input_arr[i]:
                input_arr[i-1], input_arr[i] = input_arr[i], input_arr[i-1]
                update_flag = True
  
    return input_arr

バブルソート

• 入力配列を隣接要素の比較・入れ替え操作でソートするアルゴリズム
• 名前の由来：比較・入れ替え操作により大きい/小さい要素が浮かび上がるようにみえるから（バブル：泡のように）
• 利点：アルゴリズムが単純　→　実装が容易
• 欠点：平均計算量が大きい（要素数がNの場合、最大でN²の操作が必要）
• アルゴリズムの内容：手順(小さい順に並べる場合)
  • 入力配列をin、入力配列サイズをNとする
    1. i = 0とする
    2. in[i]とin[i+1]の値を比較
    3. もし、in[i] > in[i+1]ならば、値の入れ替えを実施
    4. iをインクリメント
    5. i < N ならば操作2に戻る
    6. 操作2-5で、入れ替えを行った場合は操作1に戻る
    7. 終了
• N=5の配列に対して、バブルソートを実行すると以下図のような処理の流れになる

バブルソート例(サイズ5)

Pythonでの処理速度

• 計測環境
  • ASUS ZenBook UX390U （ノートPC）
    • Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz
• 下記コードを評価に使用
• 配列サイズNを変化させて評価

import numpy as np
import time

def bubble_sort(input_arr):
    len_arr = len(input_arr)
    update_flag = True
    while update_flag:
        update_flag = False
        for i in range(1,len_arr):
            if input_arr[i-1] > input_arr[i]:
                input_arr[i-1], input_arr[i] = input_arr[i], input_arr[i-1]
                update_flag = True

    return input_arr


N=10
input_arr = np.random.rand(N)

st = time.time()
result_arr = bubble_sort(input_arr)
elapsed = time.time() - st

print("Elapsed time[sec] : ", elapsed)

評価結果

配列サイズ	100	1000	10000
処理時間[sec]	0.009	1.153	48.133

平均計算量が配列サイズの2乗に比例するため、配列サイズの増加量以上に処理時間が伸びている。

サイズ100→1000のときは、サイズが10倍になって処理時間が100倍になっており計算量の増加にあった処理時間の増加である。

ただし、入力配列がソートされた状態に近いほど走査回数は少なくなるため速く完了する。

まとめ

今回は、実装が簡単なバブルソートを復習しました。

関数実装は簡単ですが、評価結果からもわかるように、配列サイズの増加に対する処理時間の増加は恐ろしいものです。

配列サイズが大きいときは、別のアルゴリズムを選択するべきです。

配列サイズがちいさいときには、便利なソートアルゴリズムではないでしょうか？

以上、ありがとうございました。