Rubyでバブルソート

Tech

バブルソートによる数値の並べ替えを行うプログラムを書いてみました。

この例は、Arrayクラスに新たにbubble_sortというメソッドの定義を追加しています。

class Array
  def bubble_sort
    puts '----- bubble sort -----'
    counter = 0
    sort_done = false
    until sort_done
      sort_done = true
      1.upto((self.length-1)-counter) do |i|
        puts i.to_s + ": " + self[i-1].to_s + " vs " + self[i].to_s  
        if self[i-1] > self[i]
          puts '--> Exchanged!!'
          self[i-1], self[i] = self[i], self[i-1]
          sort_done = false
        end
      end
      counter = counter + 1
      puts '--- '
    end
    self
  end
end

p [3, 4, 1, 2, 5, 2, 5, 6, 4, 3].bubble_sort

出力結果は、以下の通り。

irb(main):023:0* p [3, 4, 1, 2, 5, 2, 5, 6, 4, 3].bubble_sort 
----- bubble sort -----
1: 3 vs 4
2: 4 vs 1
--> Exchanged!!
3: 4 vs 2
--> Exchanged!!
4: 4 vs 5
5: 5 vs 2
--> Exchanged!!
6: 5 vs 5
7: 5 vs 6
8: 6 vs 4
--> Exchanged!!
9: 6 vs 3
--> Exchanged!!
--- 
1: 3 vs 1
--> Exchanged!!
2: 3 vs 2
--> Exchanged!!
3: 3 vs 4
4: 4 vs 2
--> Exchanged!!
5: 4 vs 5
6: 5 vs 5
7: 5 vs 4
--> Exchanged!!
8: 5 vs 3
--> Exchanged!!
--- 
1: 1 vs 2
2: 2 vs 3
3: 3 vs 2
--> Exchanged!!
4: 3 vs 4
5: 4 vs 5
6: 5 vs 4
--> Exchanged!!
7: 5 vs 3
--> Exchanged!!
--- 
1: 1 vs 2
2: 2 vs 2
3: 2 vs 3
4: 3 vs 4
5: 4 vs 4
6: 4 vs 3
--> Exchanged!!
--- 
1: 1 vs 2
2: 2 vs 2
3: 2 vs 3
4: 3 vs 4
5: 4 vs 3
--> Exchanged!!
--- 
1: 1 vs 2
2: 2 vs 2
3: 2 vs 3
4: 3 vs 3
--- 
[1, 2, 2, 3, 3, 4, 4, 5, 5, 6]
=> nil

もっとキレイなコードが書けそうな気がするなぁ。

ところで、Rubyの多重代入がとても便利。変数aと変数bを入れ替えるのに、

a, b = b, a

とするだけでよく、一時変数を使って入れ替える必要がないのはいいですね。

参考サイト