Web備忘録 プログラミングを中心に技術的な事柄を忘れないように書き残します。

[Python] バブルソート/選択ソート/挿入ソートの速度比較

[Python] バブルソート/選択ソート/挿入ソートの速度比較
目次

バブルソート/選択ソート/挿入ソートの速度比較

Pythonで作成した上記ソートアルゴリズムの実装を、処理速度の面から比較してみます。使用するコードは以下のページのものです。

ソートアルゴリズムにはデータによって最良の時間計算量が期待できるものから、最悪の時間計算量に陥るものまでさまざまあるので、同一のデータで検証するべきだと思います。したがって連番リストを生成してからシャッフルしこれを検証用データとします。ただし検証に用いる際にはこれを複製しておきます。

これらのソートアルゴリズムは時間計算量が O(n2) です。したがってデータ件数が多くなるとかなり遅くなるので、1000件くらいまでで確認します。以下のコードだと1000件で0.05秒位、3000件で1秒位です。

検証用コード

まずは3つのアルゴリズムの処理時間を検証してみます。 

def timer(name):
    def _timer(func):
        import functools, datetime
        import time
        @functools.wraps(func)
        def wrapper(*args, **kwargs):
            # 計測した時間を表示
            start = time.clock()
            print(name)
            func(*args,**kwargs)
            runtime = time.clock() - start
            print(runtime)
            # return runtime
        return wrapper
    return _timer

@timer("bubble_sort")
def bubble_sort(array):
    n = len(array)
    for i in range(n-1):
        for j in range(n-1, i, -1):
            if array[j] < array[j-1]:
                tmp = array[j]
                array[j] = array[j-1]
                array[j-1] = tmp

@timer("selection_sort")
def selection_sort(array):
    n = len(array)
    for i in range(0, n-1):
        # 最小値のインデックスを保持
        min = i
        for j in range(i+1, n):
            if array[min] > array[j]:
                min = j
        # 見つけた最小値を未整列末尾要素と交換
        tmp = array[min]
        array[min] = array[i]
        array[i] = tmp

# 挿入ソート
@timer("insertion_sort")
def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        tmp = array[i] # 挿入する値を退避
        if tmp < array[i-1]:
            # 挿入する位置までずらしていく
            j = i
            while True:
                array[j] = array[j-1]
                j -= 1
                if j == 0 or tmp >= array[j-1]:
                    break
            array[j] = tmp # 空いた位置に退避していた値を挿入

# 検証
if __name__ == "__main__":
    import random, copy

    # 連番リストを作成し、シャッフルする
    l = list(range(1000))
    random.shuffle(l)

    # 同一データで検証するため複製
    l1 = copy.deepcopy(l)
    l2 = copy.deepcopy(l)
    l3 = copy.deepcopy(l)

    # 処理速度計測
    bubble_sort(l1)
    print()

    selection_sort(l2)
    print()

    insertion_sort(l3)
    print()

実行してみると、バブルソートが0.1秒弱、選択ソート/挿入ソートが0.05秒前後になりました。件数を変更して確認してみても、バブルソートが1番遅く、その半分位の時間で選択ソート/挿入ソートが終了しています。

この実行コードを少々手直しし、データ件数10～1000件まで10件ずつデータを増加させながら実行時間をプロットした結果が以下のグラフです。

バブルソート/選択ソート/挿入ソートの速度比較BubbleSortSelectionSortInsertionSort501001502002503003504004505000.0000.0150.0300.0450.060

一貫してバブルソートが遅く、選択ソート/挿入ソートが拮抗しているのがわかります。選択ソート/挿入ソートはほとんど差がみられませんでした。

データ件数が少ない場合


データ件数が少ない場合の速度比較BubbleSortSelectionSortInsertionSort1015202530354045500.00000.00010.00020.00030.0004

対象データ件数が少ないと、やや挿入ソートがパフォーマンスに優れるようです。バブルソートはやはり遅いです。確実に選択ソートより交換回数が多くなるので、バブルソートが一番遅いのは明白だと思われます。

挿入ソートの得意なデータ

挿入ソートはデータ件数が少ない場合の他、ほぼソート済のデータについても高速に動作するとされています。極端な例ですが、0～999の1000件の連番データ(ソート済)の末尾に “100” を追加したデータを作成し、ソートしてみます。

検証用のデータを以下のように変更します。ソートアルゴリズムの実装部分はそのままです。 

# 検証
if __name__ == "__main__":
    import random, copy
    print("Start")
    # 0～999に100を追加
    l = list(range(1000))
    l.append(100)

    # 同一データで検証するため複製
    l1 = copy.deepcopy(l)
    l2 = copy.deepcopy(l)
    l3 = copy.deepcopy(l)

    # 処理速度計測
    bubble_sort(l1)
    print()

    selection_sort(l2)
    print()

    insertion_sort(l3)
    print()

この検証では挿入ソートが桁違いに速くなります。ほぼソート済の為、適切な位置を求めるための比較回数及び挿入の為の交換回数が少なくなるためです。同じような理由でバブルソートも選択ソートと同じくらいの速度になっていますが、比較回数はバブルソート/選択ソートともに変わらないので、挿入ソートより圧倒的に遅くなっています。

まとめ

上記の検証から処理速度は 挿入ソート > 選択ソート > バブルソート の順になります。同じ O(n2)族でも差があることがわかりました。

Pythonカテゴリの最新記事