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!!