Boa tarde pessoal!
Estou tentando implementar o algoritmo counting sort em java, mas
estou encontrando alguns problemas.
Eis o que eu fiz:
[code]/* =================================== COUNTING SORT ==================================
* Não é baseado em comparações.
* Funciona apenas para ordenar um vetor de n elementos, no qual o valor do
* maior elemento pertence a O(n), ou seja, todos os elementos do vetor têm que ter
* valores entre 0 e k, onde k <=n.
* Esse algoritmo percorre o vetor dado e vai somando um na posição correspondente
* do vetor auxiliar criado.
* Por exemplo: no passo i a posição i do vetor tem valor 3, então somo 1 ao valor contido
* na posição três do vetor auxiliar. Isso faz com que no final desse looping, eu tenha guardado
* em um vetor o número de vezes que cada elemento apareceu.
* Depois basta criar um vetor resposta, e copiar os valores do vetor dado com base
* nos indices do vetor auxiliar.
*/
public static void countingSort(int[] vetor){
int menor = vetor[getIndiceDoMenorElemento(vetor, 0, vetor.length)];
int maior = vetor[getIndiceDoMaiorElemento(vetor, 0, vetor.length)];
//Cria um vetor com o número de posições igual ao número máximo de elementos diferentes do vetor a ser ordenado
int[] aux = new int[maior - menor +1];
for(int x=0;x<vetor.length;x++){ // aux[i] fika com o número de elementos iguais a i
aux[vetor[x] -1]++;
}
for(int x=1;x<aux.length;x++){ // aux[i] fika com o número de elementos menores ou iguais a i
aux[x] += aux[x -1];
}
int[] resposta = new int[vetor.length]; // Crio um vetor para guardar os elementos ordenados
for(int x=0;x<vetor.length;x++){
resposta[aux[vetor[x]-1]-1]=vetor[x];
aux[vetor[x] -1]-=1;
}
vetor = resposta;
}[/code]
Mas não está dando certo …
Alguém poderia me ajudar ?
Obrigado.