Coundown Sort II

O Countdown Sort foi otimizado! Infelizmente, a melhoria custou um if adicional. Mesmo assim, como o algoritmo agora está quatro vezes mais rápido, acho que valeu a pena.

O algoritmo original percorria todo o array subtraindo 1 de cada elemento e anexando os que chegavam a 0 a um array ordenado. Evidentemente, não é preciso percorrer os elementos que já chegaram a 0, então resolvi tirá-los da jogada.

  public static short[] countdownSort(short in[]) {
    short[] order=new short[in.length];
    int index=0;
    short delta=0;
    int last=in.length-1;
    do {
      for(int i=last; i>=0; i--) {
        if(in[i]-delta==0) {
          order[index]=in[i];
          index++;
          if(i<last) {
            in[i]=in[last];
          }
          last--;
        }
      }
      delta++;
    } while(last>=0);
    return order;
  }

Agora, sempre que encontrar um 0, o algoritmo o troca pelo último elemento do array original e diminui em uma posição a abrangência da busca. Se justamente o último elemento é que chegou a 0, então basta subtrair 1 do índice que aponta para o fim do array (representado no código pela variável last).

Isso significa que o array original será destruído, mas, como o método retorna uma versão ordenada dos números, o problema não é grave.

Paira ainda no ar a dúvida sobre se algo realmente útil pode advir deste algoritmo.