【Python】バブルソート【アルゴリズム】

この記事は約2分で読めます。

バブルソートについて

  • 計算量はO(n^2)
  • リストの先頭から順に2つの要素の大小比較し、大きい方の要素がリストの先頭に近ければその2つの要素の位置を入れ替える
  • 先頭から前述の比較と入れ替えを繰り返す
  • 最大の要素がリストの最後尾に移動する
  • リストの右端から(最大値から)順に確定していく

コード

[5,1,3,8,2,9,10,6,7,4]をバブルソートする場合

始めに5,1の大小比較をします。5の方が大きいので、位置を入れ替えます

→[1,5,3,8,2,9,10,6,7,4]

次に5,3の大小比較をして位置を入れ替えます。

→[1,3,5,8,2,9,10,6,7,4]

次に5,8の大小比較をしますが、8の方が大きいのでそのままです。

これを繰り返すと、10が最後尾に移動します。これで最大値である10がソート済となりました。

→[1,3,5,2,8,9,6,7,4,10]

ここまでが外側のforループの1回目の動作です。

もう一度先頭から大小比較を行います。

内側のループで、for j in range(len(data)-i-1): とありますが、

len(data)-i-1は、ループが1周したことでiが増えているので、-1しています。

また、1回目のループで10がソート済みとなっているので、ソートすべき数が1つ減っています。

ループした回数だけ、ソート済みの要素が増えるので、-iとしています。

コメント