ソートアルゴリズムの1つであるバブルソートを実装してみました。
ソートの中でも1番最初に習う基本のソートです。
まずはアルゴリズムから見ていきましょう。
[toc]
アルゴリズム
- 左から1番目の値(A)と右隣の値(B)を比較し、Aの方が大きければBと交換(スワップ)します。
- 1.の処理を、左から2番目、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))
おわり。