Algoritmo counting sort

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.

“Não está dando certo” não ajuda muito.
Que tal você imprimir todos os vetores que você está usando, e ver se não há algum problema do tipo “oops, eu peguei um valor e ele está ficando FORA do array?”
Não se esqueça que um vetor, em Java, vai de [0] até [n-1], onde “n” é a dimensão do vetor.

Esse dois métodos

getIndiceDoMenorElemento(vetor, 0, vetor.length) e getIndiceDoMaiorElemento(vetor, 0, vetor.length);

são métodos auxiliares que retornam o indice do menor e do maior elemento do vetor passado como argumento. Os outros dois parametros são apenas
o intervalo em que o valor máximo ou mínimo está contido (nesse caso o intervalo é o vetor inteiro).

bezier curve, me desculpe pela descrição do erro…

O que está acontecendo é que quando eu mando imprimir o vetor, ele está inalterado …

Ou seja, com a mesma ordem que eu tinha passado.

Ah, eu sei que o vetor em Java vai de 0 até n-1… Inclusive essa é uma das razões pelo qual estou tendo dificuldade de implemntar esse método.

Você conhece essa abordagem de ordenação do counting sort ?

Hum… você nunca ouviu falar que o Java passa parâmetros por valor? Portanto, você quase acertou - faltava só um pouquinho. Fiquei com preguiça de ver se o resultado está certo. O resultado que deu para seu programa é:

1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 9, 9, 9,

Dê uma olhada se é isso mesmo.

import java.util.*;

class CountingSort {

     private static int getIndiceDoMaiorElemento (int[] vetor, int inicio, int fim) {
         int indice = -1;
         int maximo = Integer.MIN_VALUE;
         for (int i = inicio; i < fim; ++i) {
             if (vetor[i] > maximo) { 
                 maximo = vetor[i]; indice = i;
             }
         }
         return indice;
     }
     private static int getIndiceDoMenorElemento (int[] vetor, int inicio, int fim) {
         int indice = -1;
         int minimo = Integer.MAX_VALUE;
         for (int i = inicio; i < fim; ++i) {
             if (vetor[i] < minimo) { 
                 minimo = vetor[i]; indice = i;
             }
         }
         return indice;
     }

 /* =================================== 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;  
               
         }  
                   
         // Aqui está seu problema. Vamos corrigir para:
         System.arraycopy (resposta, 0, vetor, 0, vetor.length);
           
     } 

    public static void main (String[] args) {
        int[] vetor = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2};
        countingSort (vetor);
        for (int i = 0; i < vetor.length; ++i) {
            System.out.print (vetor[i] + ", ");
        }
        System.out.println ();
    }
}

Dica: acho mais fácil você retornar a resposta no valor de retorno. Portanto, seu método seria mais facilmente codificado se fosse:

public static int[] countingSort(int[] vetor) {

Sim, eu sei disso, mas no caso de tipos complexos ele passa por referencia, certo ?

Então achei que aquela linha vetor = resposta surtiria efeito fora do método (ou seja, na variável vetor passada ao método …)

De qualquer forma, eu deixei o método assim:

public static int[] 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=resposta.length-1;x>=0;x--){
			resposta[aux[vetor[x]-1]-1]=vetor[x];
			aux[vetor[x] -1]-=1;
			
		}
		
		return resposta;	
	}

Só que se houver um valor zero no vetor passado, acontece um erro por tentar acessar uma posição inválida do vetor ( a posição -1) …

Pensei em criar um vetor com um posição a mais e inutilizar a posição 0, assim eu não precisaria desse monte de -1 ( como na linha resposta[aux[vetor[x]-1]-1]=vetor[x] ).

O que você acha ?

Alguém conseguiria implementar o radixSort utilizando esse countingSort que está acima ?