sexta-feira, 26 de fevereiro de 2010

Programação Incondicional VIII

Após sub-repticiamente introduzir o Power Sort ao mundo, decidi investir mais tempo no seu aprimoramento. O primeiro passo é permitir a ordenação de inteiros negativos. O algoritmo original utiliza uma variável para acumular potências de 2. Os negativos poderiam ser guardados na parte fracionária, mas achei mais simples e mais eficiente usar um segundo acumulador.

O código Perl abaixo mostra como os números negativos são acumulados numa variável ($pn) e os positivos noutra ($pp). Depois, os números positivos são devolvidos à lista em ordem decrescente, do fim para o início. Os negativos são inseridos do início para o fim, até encontrarem os positivos.

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

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

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

my $log2=log(2);

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

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

return @sorted;
}
my @sorted=psort(-2,19,8,3,20,16,13,-22,11,52,5,2,-33,
18,-4,4,15,1,9,14,6,7,10,17,12,27,50,0,-13);
print join ',', @sorted;

O primeiro laço usa um truque baixo para evitar os ifs, porque, embora existam alternativas mais condizentes com a filosofia da Programação Incondicional, elas são um tanto crípticas.

Então, o próximo ramo de pesquisa da Programação incondicional são as fórmulas que produzam 0 ou 1 para identificar números positivos ou negativos.

Nenhum comentário: