Counting Sort

Tags:

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]

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *