Sleep Sort

Alguns algoritmos têm pouco valor prático, mas grande valor didático. Há poucas horas foi criado mais um destes (vale ouro presenciar o nascimento de um novo algoritmo de ordenação!): o Sleep Sort. Ele é tão novo, que não tem página na Wikipédia ainda.

O algoritmo é simples: para cada número x, deixam-se passar x unidades de tempo para adicioná-lo à lista ordenada. Quanto maior o valor de x, mais tempo ele precisará esperar e, portanto, mais para o fim da lista ficará posicionado.

Minha solução em Javascript é esta:

function sleepSort(n,callback) {
  var out=new Array();
  for(i in n) {
    var x=n[i];
    var pusher=function(x) {
      return function() { 
        out.push(x); 
        if(out.length==n.length) {
          callback(out);
        }
      };
    }(x);
    setTimeout(pusher, x*100);
  }
}

Como o método setTimeout() usa milissegundos como unidade, multiplico o valor de cada elemento por 100, para ter certeza que haverá tempo suficiente entre eles para não haver confusão.

Quando o último elemento for adicionado, a nova lista estará tão grande quanto a original e a função de callback será chamada. Dada a natureza do algoritmo, não é possível retornar imediatamente o resultado a partir de sleepSort().

O lado didático desse exercício é que ele ajuda a esclarecer como funcionam as closures do Javascript. Eu uso uma função que cria outra função, porque as closures têm referências às variáveis do contexto que as circunda. Logo, sem a função anônima intermediária, todas as chamadas usariam o último valor atribuído a x. Como a função intermediária recebe o x como parâmetro e os parâmetros são passados por cópia, o x da função mais aninhada é cópia e não referência do x original. Logo antes da chamada a setTimeout() está a chamada à função intermediária.

Segue um teste simples:

sleepSort([19,48,61,3,10,20,45,33],
  function(result) { 
    alert(result.join(",")); 
  }
);

Só falta nessa função uma maneira de tirar aquele if intrometido.

P.S. No dia 17/06/2011 surgiu uma entrada na Wikipédia sobre o Sleep Sort.