Programação Incondicional VII

Já estabeleci que é possível escrever algoritmos recursivos sem ifs. Agora, resolvi atacar os algoritmos de ordenação.

Antes de alterar os algoritmos estabelecidos, resolvi criar um algoritmo inerentemente incondicional. O algoritmo não tem jeito de ser original, mas não encontrei outro semelhante no Google. Por isso, tomo a liberdade de batizá-lo: Power Sort. Logo se verá por que ele tem esse humilde nome.

O algoritmo funciona da seguinte forma:

1. Inicializa-se uma variável p com 0;
   
2. Para cada número n da lista, soma-se 2ⁿ a p;
3. O último elemento da lista é a potência do maior múltiplo de 2 que caiba em p;
4. Repete-se o passo 3 tantas vezes quantos elementos houver na lista.

O código abaixo mostra o algoritmo em Perl.

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

 my $p=0;
 foreach my $n (@sorted) {
  $p+=2**$n;
 }

 my $log2=log(2);
 for(my $i=$length-1; $i>=0; $i--) {
  my $n=int(log($p)/$log2);
  $sorted[$i]=$n;
  $p=$p-(2**$n);
 }

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

As vantagens são:

1. Não tem ifs!
2. Requer pouquíssima memória (não precisa de array auxiliar);
3. Não executa trocas;
4. Tem complexidade O(n).

E as restrições são:

1. Não pode haver números repetidos (embora funcione, de quando em vez);
2. Não funciona com arrays grandes, porque a soma cresce muito rapidamente;
3. Não funciona com números negativos.

Em linguagens que permitem números maiores, como Lisp e Tcl, podem ser ordenadas listas maiores. Em Java, é possível usar BigDecimal para representar números maiores. Em linguagens sem facilidades para números realmente grandes, fica-se restrito a listas relativamente pequenas.

Com base e, ele ficaria mais simples e rápido, mas o número máximo de elementos seria menor.