【Python】バブルソート法(交換法)を実装

Pythonでバブルソート法(交換法)を実装する方法をソースコード付きで解説します。

【バブルソートとは】リストを昇順・降順ソート

バブルソート法(交換法)は、リストの隣接する2つの要素の値を順に比較し、大小関係が指定した条件を満たしていない場合に、交換を行うアルゴリズムです。
交換が一度も行われなくなったときに処理を終了し、そのときのリストが整列(ソート)されます。

値が大きい、もしくは小さい要素が浮かびあがってくることから、バブル(bubble:泡)ソートと呼ばれます。

バブルソート法で昇順ソートする場合の手順は以下のとおりです。

順序 操作
1番目の要素と、隣接する2番目の要素の値を比較する。1番目の値の方が大きければ、要素の値を交換する。
2番目の要素と、隣接する3番目の要素の値を比較する。2番目の値の方が大きければ、要素の値を交換する。
終端要素nまで2つの要素の比較と交換を繰り返す。
終端の要素には、最も大きい値が格納されるので、比較と交換を行う終端位置を1つ減らす。
交換が一度も生じなくなるまで手順①〜③を繰り返す。
参考 【バブルソート法(交換法)とは】リストの昇順・降順ソートと計算量

【サンプルコード】Python3

Python3でリストのバブルソートを行うサンプルコードです。

def babble_sort(arr):
    # リストの要素数
    N = len(arr)

    for i in range(N-1):

        cnt = 0  # 交換回数のリセット

        for j in range(0, N-1-i):
            # 前から順に隣り合う要素を比較し、左が右の要素に比べ大きい場合交換
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                cnt = cnt + 1  # 交換回数をカウント

        print(str(i+1)+"回目:", arr)

        # 交換が1度も発生しなければ終了
        if cnt == 0:
            return arr


    return arr


# バブルソート1
arr = [7, 2, 5, 3]
print("ソート前:", arr)
babble_sort(arr)
print("ソート後:", arr)

print("-----------")

# バブルソート2
arr = [2, 3, 7, 5]
print("ソート前:", arr)
babble_sort(arr)
print("ソート後:", arr)

"""
ソート前: [7, 2, 5, 3]
1回目: [2, 5, 3, 7]
2回目: [2, 3, 5, 7]
3回目: [2, 3, 5, 7]
ソート後: [2, 3, 5, 7]

-----------

ソート前: [2, 3, 7, 5]
1回目: [2, 3, 5, 7]
2回目: [2, 3, 5, 7]
ソート後: [2, 3, 5, 7]
"""

関連記事
1 Python版OpenCV入門 サンプル集
2 【画像処理入門】アルゴリズム&プログラミング

コメント