バブルソートでは要素数回ソートを回せば、必ず順に並びきるのか

Question

すみません。気になったので質問です。
rubyでバブルソートアルゴリズムを書いていて、他の人がどう書いているのか気になったので、調べたところ
下記のようなコードを見つけました。

data = [9,3,5,1,18,2,8]

def bubble_sort(data)
  data.length.times do |i|
    (data.length-(i+1)).times do |j|
      if data[j] > data[j+1]
        data[j],data[j+1] = data[j+1],data[j]
      end
    end
    p data
  end
  data
end

p data のところの結果を見ると、

0
1
2
3
4
5
[3, 5, 1, 9, 2, 8, 18]
0
1
2
3
4
[3, 1, 5, 2, 8, 9, 18]
0
1
2
3
[1, 3, 2, 5, 8, 9, 18]
0
1
2
[1, 2, 3, 5, 8, 9, 18]
0
1
[1, 2, 3, 5, 8, 9, 18]
0
[1, 2, 3, 5, 8, 9, 18]
[1, 2, 3, 5, 8, 9, 18]
[1, 2, 3, 5, 8, 9, 18]

こんな感じで、4回目のソートで昇順に並びきっています。
自分が疑問に思ったのは、上記アルゴリズムが配列の要素数回以内に昇順に並びきると考えられている部分です。
本当に要素数以内にバブルソートは昇順にすることができるのでしょうか？

何卒よろしくお願いします。

Answer 1

要素数以内にバブルソートは昇順にすることができるのでしょうか？

できます。
loopを一度回ることで最大値を配列の末尾に追いやれますから
要素数分loopすることでソートが完了します。

Comments

[tomoharu]

ありがとうございます！　納得できました！