Problemas com radix sort

1 resposta
zoso

eu tentei implementar um algoritmo radix sort com auxílio da interface Queue, mas quando eu tento executar, dá NullPointerException. Eu sei q essa exception é lançada qndo o programa tenta acessar um objeto nulo, mas eu não consigo ver de q outra forma referenciar uma Queue[]. aí vai o código:

import java.util.Queue;
import java.util.LinkedList;

public class RadixSort {
	

	private static final int MAXDEC = 6; //número máximo de algarismos
	
	
	//metodo que retorna o algarismo de uma determinada casa decimal.

	private int Alg(int n, int dec){

	    if(dec <= 1)

	        return n%10;

	    else
	        return Alg(n/10, dec-1);


	}
	
	public void radixSort(int[] arr){

	    int alg, j;
	    Queue[] queue = new LinkedList[10];
	    
	    for(int dec = 1; dec < MAXDEC; dec++){

                j = 0;
	    	
	    	for(int i = 0; i < arr.length; i++){
	    		
	    		alg = Alg(arr[i], dec);
		    	queue[alg].offer(arr[i]); /*o compilador aponta o erro pra essa linha. Aqui eu coloco o elemento do array na fila apropriada.
                                                              i.e. arr[i] == 12 vai para queue[2] quando o método Alg retorna o algarismo da 1a casa decimal*/
		    	
		    	for(int k = 0; k < 10; k++){
		    		
		    		if(queue[k].peek() != null) //verifica se a fila não está vazia para recolocar o elemento no array
		    			arr[j++] = (Integer)queue[k].poll();
		    		else
		    			continue;
		    	}
	    	}
	    }
	}
	
	public static void main(String[] args){
		
	int i;
        int[] arr = new int[15];
        RadixSort rdx = new RadixSort();
        System.out.print("original: ");
        for(i=0;i<arr.length;i++){
            arr[i] = (int)(Math.random() * 1024);
            System.out.print(arr[i] + " ");
        }
        System.out.println("\nstart:" + System.currentTimeMillis());
        rdx.radixSort(arr);
        //System.out.println("\nsorting time:" + Math.abs(count -= System.currentTimeMillis()));
        System.out.println("\nfinish:" + System.currentTimeMillis());
        System.out.print("\nsorted: ");
        for(i=0;i<arr.length;i++)
            System.out.print(arr[i] + " ");
        System.out.println("\nDone!");
	}
	
}

conceito do radix sort tirado da wikipedia: "- Least significant digit (LSD ? Dígito menos significativo) radix sort; - Most significant digit (MSD ? Dígito mais significativo) radix sort.

O radix sort LSD começa do dígito menos significativo até o mais significativo, ordenando tipicamente da seguinte forma: chaves curtas vem antes de chaves longas, e chaves de mesmo tamanho são ordenadas lexicograficamente. Isso coincide com a ordem normal de representação dos inteiros, como a seqüência "1, 2, 3, 4, 5, 6, 7, 8, 9, 10". Os valores processados pelo algoritmo de ordenação são frequentemente chamados de ?chaves?, que podem existir por si próprias ou associadas a outros dados. As chaves podem ser strings de caracteres ou números."

log do compilador:

Exception in thread "main" java.lang.NullPointerException
at radixsortqueue.RadixSort.radixSort(RadixSort.java:40)
at radixsortqueue.RadixSort.main(RadixSort.java:66)

eu suponho q a minha lógica esteja correta, qualquer ajuda é bem-vinda!!

1 Resposta

kabarret

Bom não tenho muita certeza, sou novato, mas vou tentar ajudar.
Não entendi muito bem oq o codigo faz.

Mas vamos por parte.
Quando ocorre erro de NullPointerException é porque esta tentando usar um metodo de um objeto que não foi inicializado.

seguindo esse conceito, e pelo ponto que ocorre o erro, suspeito que você deva inicializar antes a variavel queue[] , pois quando você cria um vetor de objeto, todos membros são inicializados como Null.

Dai o NullPointer.

Criado 13 de abril de 2011
Ultima resposta 13 de abr. de 2011
Respostas 1
Participantes 2