rubyist.or.kr 에 포스팅이 하도 없어 올려봅니다. Counting Sort의 루비 구현.
def counting_sort(ary)
max = ary.max
c = Array.new(max + 1, 0)
# Counting
ary.each do |e|
c[e] += 1
end
# Cumulative Counting
for i in 1..(c.size-1)
c[i] += c[i-1]
end
# Putting numbers in order considering
# cumulative counting
result = Array.new(ary.size)
ary.reverse.each do |e| # Use reverse to make sorting stable
result] = e
c[e] -= 1
end
result[1..-1]
end
if __FILE__ == $0
for i in (1..100)
puts “Testing #{i}”
ary = [ ]
1000.times {
ary << rand(1000)
}
if ary.sort == counting_sort(ary)
puts "pass"
else
puts "fail"
exit 0
end
end
end
[/code]
Leave a Reply