箱のプログラミング日記。

えんじにあ奮闘記

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

こんな感じになりました。

最初から比較回数が決まっているのでもっと効率的なやり方がありそう...。

とりあえずソートの勉強にはなりました。

参考