#!/usr/bin/perl -w
# 演算法: counting sort
# 作者: 洪朝貴 http://www.cyut.edu.tw/~ckhung
# 授權: public domain (但如果您要將我的程式改寫成有用的大程式,
#	強烈建議將您的版本施以 GPL)
# 執行方式: ./cntsort -r 12 -n 20
#       產生 20 個字母, 每個字母都是從 ABC...JKL 這 12
#       個字母當中, 用亂數挑一個出來的。

use Getopt::Std;
use strict;

my (%opts) = (
    r => 12,	# radix, number of possible distinct input characters
    n => 20,	# number of input characters
);

getopts('r:n:', \%opts);

sub ord2chr { return chr(ord('A')+$_[0]); }
sub print_array {
    my ($name, $as_ch, $a) = @_;
    printf "%-8s:", $name;
    foreach (@$a) {
	printf "%3s", defined $_ ? ($as_ch ? ord2chr($_) : $_) : "*";
    }
    print "\n";
}

my (@input, @output, @count, $i);
@input = map { int(rand()*$opts{r}) } 1..$opts{n};
$#output = $#input;

print_array("input", 1, \@input);
$count[0] = 0;
foreach $i (@input) { ++$count[$i]; }
print_array("count", 0, \@count);
for ($i=1; $i<$opts{r}; ++$i) { $count[$i]+=$count[$i-1]; }
print_array("count", 0, \@count);
print "-" x 60, "\n";
foreach $i (reverse @input) {
    $output[--$count[$i]] = $i;
    print_array("output", 1, \@output);
    print_array("count", 0, \@count);
    print " " x ($i*3+11), "^", "\n";
}