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

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

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

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

スポンサーリンク

アルゴリズム

  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

実装例

おわり。