バブルソートについて
- 計算量はO(n^2)
- リストの先頭から順に2つの要素の大小比較し、大きい方の要素がリストの先頭に近ければその2つの要素の位置を入れ替える
- 先頭から前述の比較と入れ替えを繰り返す
- 最大の要素がリストの最後尾に移動する
- リストの右端から(最大値から)順に確定していく
コード
|
1 2 3 4 5 6 7 |
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としています。
コメント