【Python】バブルソートを実装してみた

ソートアルゴリズムの1つであるバブルソートを実装してみました。

ソートの中でも1番最初に習う基本のソートです。

まずはアルゴリズムから見ていきましょう。

[toc]

アルゴリズム

  1. 左から1番目の値(A)と右隣の値(B)を比較し、Aの方が大きければBと交換(スワップ)します。
  2. 1.の処理を、左から2番目、3番目、、と続け、リストの最後に行くまで繰り返します。
  3. 一度もスワップが発生しなければそこで終了です。スワップが発生したら、1番右の値を整列済みとし残りの値からできるサブリストで1と2の処理を繰り返します。

この処理を1度進めると1番大きな値が泡(バブル)のように1番右に出現することから、バブルソートと言われております。

Wikipediaの具体例を見てみるとわかりやすいかと思います。

初期データ: 8 4 3 7 6 5 2 1
結果が確定した部を太字でしめすと、

4 3 7 6 5 2 1 8 (1回目の外側ループ終了時 交換回数:7)
3 4 6 5 2 1 7 8 (2回目の外側ループ終了時 交換回数:5)
3 4 5 2 1 6 7 8 (3回目の外側ループ終了時 交換回数:3)
3 4 2 1 5 6 7 8 (4回目の外側ループ終了時 交換回数:2)
3 2 1 4 5 6 7 8 (5回目の外側ループ終了時 交換回数:2)
2 1 3 4 5 6 7 8 (6回目の外側ループ終了時 交換回数:2)
1 2 3 4 5 6 7 8 (7回目の外側ループ終了時 交換回数:1)

https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%96%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88

実装例

def bubble(l):

    n = len(l)

    for i in range(n):
        swapped = False
        for j in range(n-i-1):
            if l[j] > l[j+1]:
                l[j],l[j+1] = l[j+1],l[j]
                swapped = True

        if swapped == False:
            break

    return l


number_list = [2,3,1,4,7,5]

print(bubble(number_list))

おわり。

ABOUTこの記事をかいた人

個人アプリ開発者。Python、Swift、Unityのことを発信します。月間2.5万PVブログ運営。 Twitter:@yamagablog