quarta-feira, 17 de março de 2010

Programação Incondicional IX

Generalizar o Power Sort para permitir números duplicados não é difícil: basta usar um hash.

sub psort {
my @sorted=@_;
my $index=scalar(@_);

my $pp=0;
my $pn=0;

my %occurrences=();

foreach my $n (@_) {
$pp+=(2**$n) * ($n>=0 && $occurrences{$n}==0);
$pn+=(2**abs($n)) * ($n<0 && $occurrences{$n}==0);
$occurrences{$n}++;
}

my $log2=log(2);
while($pp>0) {
my $n=int(log($pp)/$log2);
$sorted[--$index]=$n while $occurrences{$n}-->0;
$pp=$pp-(2**$n);
}

$index=0;
while($pn>0) {
my $n=-int(log($pn)/$log2);
$sorted[$index++]=$n while $occurrences{$n}-->0;
$pn=$pn-(2**abs($n));
}

return @sorted;
}
my @sorted=psort(1,1,-3,-5,-7,2,4,8,-10,-10);
print join ',', @sorted;

Tenho que escrever isso em Java, para ver como fica.

Nenhum comentário: