Rubyでバブルソートを書いてみる

f:id:y_hakoiri:20191102121704j:plain

Rubyにはsortメソッドがあって、その名の通りソートしてくれるんだけど

a = (1..9).to_a.shuffle
=> [1, 2, 8, 7, 4, 3, 9, 5, 6]
a.sort
=> [1, 2, 3, 4, 5, 6, 7, 8, 9]

これをsortを使わずに実現したい。

バブルソートで実装してみる。

バブルソートとは

バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。

バブルソート - Wikipedia

要素の右端から比較を始める
右端の要素とその左隣の要素を比較し、右側の要素の方が小さければ、左右を入れ替える
左端に到達するまでこれを繰り返し、左端の要素はソート済みにする

これを全ての要素がソート済みになるまで繰り返すと、整列が終了する。

やってみる

要素の数が9個の場合、最初の1周目は8回比較を行うことになる。

a = (1..9).to_a.shuffle
=> [1, 2, 8, 7, 4, 3, 9, 5, 6]

1回目...5と6を比較
2回目...9と5を比較。右側の要素(5)の方が小さいので、左右を入れ替える

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

3回目...3と5を比較
4回目...4と3を比較。右側の要素(3)の方が小さいので、左右を入れ替える

これを左端に到達するまで行うと、

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

こうなる。

たまたま今回は1,2,3となっているけど、1周完了すると1が左端に、2周完了すると2が左から2番目に...と順番にソート済みになっていく。

コードに起こす

右端から左右の要素を比較していき左端に到達するまでの1周をコードに置き換えようとすると、

a = (1..9).to_a.shuffle
=> [1, 2, 8, 7, 4, 3, 9, 5, 6]

1回目...a[-2]とa[-1]を比較
2回目...a[-3]とa[-2]を比較。右側の要素の方が小さいので、左右を入れ替える

a = (1..9).to_a.shuffle
bubble_count = a.size - 1
i = 0
bubble_count.times do
  l, r = a[-2-i], a[-1-i]
  if l > r
    a[-2-i] = r
    a[-1-i] = l
  end
  i += 1
end

こんなところかな。

1周で比較する回数が要素数-1になるので、最初の1周は8回。

次の1周は7回...と1回ずつ比較回数が減っていくので、最終的には

a = (1..9).to_a.shuffle

bubble_count = a.size - 1
loop do
  i = 0
  bubble_count.times do
    l, r = a[-2-i], a[-1-i]
    if l > r
      a[-2-i] = r
      a[-1-i] = l
    end
    i += 1
  end
  bubble_count -= 1
  break if bubble_count.zero?
end