[ソート] バブルソート

バブルソート

バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n²)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。

出典: フリー百科事典『ウィキペディア（Wikipedia）』

「配列の先頭から最後まで、自身と次の要素を比較して、正しい順序関係にない場合は互いを交換する」という処理を繰り返します。

例えば数値を昇順にソートする時、最も大きい数値が先頭にあったら、次の要素との交換が繰り返され、泡がどんどん上に登っていくようなイメージで、最も大きい数字は一番最後まで移動します。

その後は、一番最後に移動した要素は除き、先頭から同じ処理を繰り返します。

また、ループを回した際に要素の交換が発生しない場合は、整列が終了しているので、その場合はフラグを用いてソートを終了することができます。

平均計算時間、最悪計算時間ともに\( O (N ^ 2) \) です。

安定ソートで、内部ソートです。

Python で実装

バブルソートを Python で実装します。

import random

def bubble_sort(array):
    # ソート済みかの判定フラグ
    swapped = False
    
    for i in range(len(array)):
        if swapped:
            return array

        swapped = True
        for k in range(len(array) - 1, i, -1):
            if (array[k] < array[k - 1]):
                swap(array, k, k - 1)
                # 一度でも swap すればソート済みではない
                swapped = False

    return array
                
def swap(array, x, y):
    array[y], array[x] = array[x], array[y]


if __name__ == '__main__':
    # ランダムな配列の生成
    random.seed(1)
    array = [random.randrange(100) for i in range(10)]
    print('未ソート', array)
    # 未ソート [17, 72, 97, 8, 32, 15, 63, 97, 57, 60]
    
    print('ソート済み', bubble_sort(array)) 
    # ソート済み [8, 15, 17, 32, 57, 60, 63, 72, 97, 97]