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

バブルソートについて
コード

バブルソートについて

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

コード

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

for i in range(len(data)):                 #要素の数だけ大小比較を繰り返す
  for j in range(len(data)-i-1):           #[1] ソートされていない要素のうち、2番目以降の要素数だけ繰り返す
    if data[j]>data[j+1]:                  #[2]j+1番目よりもj番目の要素が大きい場合
      data[j],data[j+1]=data[j+1],data[j]  #j番目とj+1番目の要素を入れ替える
print(data)

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

for i in range(len(data)): #要素の数だけ大小比較を繰り返す

for j in range(len(data)-i-1): #[1] ソートされていない要素のうち、2番目以降の要素数だけ繰り返す

if data[j]>data[j+1]: #[2]j+1番目よりもj番目の要素が大きい場合

data[j],data[j+1]=data[j+1],data[j] #j番目とj+1番目の要素を入れ替える

print(data)

[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としています。