#/***********************************************************
#    distsort.rb -- 分布数えソート
#***********************************************************/
MAX = 100
MIN = 0

def distsort( n, a,  b)
    count = []

    for i in 0..MAX; count[i] = 0; end
    for i in 0...n; count[a[i] - MIN] += 1; end
    for i in 1..MAX; count[i] += count[i - 1]; end
    (n - 1).downto(0) do |i|
        x = a[i] - MIN;  b[(count[x] -= 1)] = a[i]
    end
end

N = 20

a = []; b = []

printf("Before:")
for i in 0...N
    a[i] = (MAX - MIN + 1.0) * rand() + MIN
    printf(" %d", a[i])
end
printf("\n")
distsort(N, a, b)
printf("After: ")
for i in 0...N; printf(" %d", b[i]); end
printf("\n")

exit 0