rubyでバブルソート
class Sort def bubble(ary) max = ary.length - 1 tmp = nil until max == 0 (0..max).each do |i| break if i == max if ary[i] > ary[i + 1] tmp = ary[i + 1] ary[i + 1] = ary[i] ary[i] = tmp end end max -= 1 end ary end end require "test/unit" require_relative "./sort.rb" class TestSort < Test::Unit::TestCase def setup @obj = Sort.new end def test_sort assert_equal([3,4,8],@obj.bubble([8,3,4])) assert_equal([1,2,3],@obj.bubble([3,2,1])) assert_equal([1,2,3,4,5,6,7,8],@obj.bubble([8,4,3,7,6,5,2,1])) end end Started [3, 4, 8] [3, 4, 8] [2, 1, 3] [1, 2, 3] [4, 3, 7, 6, 5, 2, 1, 8] [3, 4, 6, 5, 2, 1, 7, 8] [3, 4, 5, 2, 1, 6, 7, 8] [3, 4, 2, 1, 5, 6, 7, 8] [3, 2, 1, 4, 5, 6, 7, 8] [2, 1, 3, 4, 5, 6, 7, 8] [1, 2, 3, 4, 5, 6, 7, 8] . Finished in 0.000539 seconds. ------------------------------------------------------------------------------- 1 tests, 3 assertions, 0 failures, 0 errors, 0 pendings, 0 omissions, 0 notifications 100% passed ------------------------------------------------------------------------------- 1855.29 tests/s, 5565.86 assertions/s
バブルソート久しぶりに書いた。簡単にかけるかと思ったけど、結局ゴリゴリデバッグないと動かなかった。
・最も大きい要素が終端に行く
・終端を狭める
ことを理解したら、すんなり動いた。この2点が肝だと思う。アルゴリズムの問題見ていると、ビギナーレベルでも、何書いてあんだかさっぱり分からない問題が多くて、凹む。