[CLR][Ruby] Counting Sort

'Introduction to Algorithms(CLR)' 8장에 나오는 계수 정렬(Counting Sort)를 루비로 구현해 봤다.

def counting_sort(input, output, k)
  temp = Array.new(k+1, 0)
  length = input.size - 1

  (0..length).each {| i | temp[input[i]] = temp[input[i]] + 1}
  (1..k).each {| i | temp[i] = temp[i] + temp[i - 1]}
  length.downto(0) do | i |
    output[temp[input[i]]] = input[i]
    temp[input[i]] = temp[input[i]] - 1
  end

  output
end

a = [6, 0, 2, 1, 3, 4, 6, 1, 3, 2]
b = Array.new
puts counting_sort(a, b, a.max).inspect