【Python】バブルソート法（交換法）を実装

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

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

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

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

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

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

## 【サンプルコード】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)

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


    return arr


# バブルソート１
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]
"""