Pergunta de Java
Para entender como o Método de Ordenação Radix Sort funciona, veja a descrição de um exemplo abaixo:
Considere um vetor contendo N elementos inteiros de 3 algarismos que se deseja ordenar:
IMAGEM 1
0 1 2 3 4 5 6 7 8 9
784 124 255 454 233 687 728 831 221 450
Na primeira iteração, deve ser criada uma matriz 10 x 10, indexada de 0.. 9 nas linhas e nas colunas. Cada elemento do vetor será inserido na coluna da matriz cujo valor seja igual ao seu algarismo menos significativo. Por exemplo: o valor 784 será inserido na coluna 4. A matriz resultante para o vetor inicialmente mostrado é:
0 1 2 3 4 5 6 7 8 9
450 831 233 784 255 678
221 124 728
454
Após isso, o vetor original é reconstruído, respeitando essa nova ordem. Assim, teremos:
IMAGEM 3
0 1 2 3 4 5 6 7 8 9
450 831 221 233 784 124 454 255 678 728
O algoritmo se repete, analisando agora o algarismo do meio. Para o exemplo do valor 784, o número 8 indica que ele deva ser inserido na coluna 8. A nova matriz ficará:
IMAGEM 4
0 1 2 3 4 5 6 7 8 9
221 831 450 678 784
124 233 454
728 255
Reconstroi-se novamente a lista original:
IMAGEM 5
0 1 2 3 4 5 6 7 8 9
221 124 728 831 233 450 454 255 678 784
O algoritmo se repete, analisando agora o algarismo mais significativo. Para o exemplo do valor 784, o número 7 indica que ele deva ser inserido na coluna 7. A nova matriz ficará:
IMAGEM 6
0 1 2 3 4 5 6 7 8 9
124 221 450 678 728 831
233 454 784
255
Com a reconstrução da lista original, tem-se o vetor ordenado. Veja:
IMAGEM 7
0 1 2 3 4 5 6 7 8 9
124 221 233 255 450 454 678 728 784 831
Implemente um programa em Java que realize este método de ordenação. Vamos considerar que o vetor original será gerado randomicamente e que não possui mais do que 3 algarismos (valores < 1000). Com isso, garantimos que o número de iterações será 3, pois o algoritmo deve ser repetido considerando o total de algarismos que o maior valor do vetor possui.
Considere um vetor contendo N elementos inteiros de 3 algarismos que se deseja ordenar:
IMAGEM 1
0 1 2 3 4 5 6 7 8 9
784 124 255 454 233 687 728 831 221 450
Na primeira iteração, deve ser criada uma matriz 10 x 10, indexada de 0.. 9 nas linhas e nas colunas. Cada elemento do vetor será inserido na coluna da matriz cujo valor seja igual ao seu algarismo menos significativo. Por exemplo: o valor 784 será inserido na coluna 4. A matriz resultante para o vetor inicialmente mostrado é:
0 1 2 3 4 5 6 7 8 9
450 831 233 784 255 678
221 124 728
454
Após isso, o vetor original é reconstruído, respeitando essa nova ordem. Assim, teremos:
IMAGEM 3
0 1 2 3 4 5 6 7 8 9
450 831 221 233 784 124 454 255 678 728
O algoritmo se repete, analisando agora o algarismo do meio. Para o exemplo do valor 784, o número 8 indica que ele deva ser inserido na coluna 8. A nova matriz ficará:
IMAGEM 4
0 1 2 3 4 5 6 7 8 9
221 831 450 678 784
124 233 454
728 255
Reconstroi-se novamente a lista original:
IMAGEM 5
0 1 2 3 4 5 6 7 8 9
221 124 728 831 233 450 454 255 678 784
O algoritmo se repete, analisando agora o algarismo mais significativo. Para o exemplo do valor 784, o número 7 indica que ele deva ser inserido na coluna 7. A nova matriz ficará:
IMAGEM 6
0 1 2 3 4 5 6 7 8 9
124 221 450 678 728 831
233 454 784
255
Com a reconstrução da lista original, tem-se o vetor ordenado. Veja:
IMAGEM 7
0 1 2 3 4 5 6 7 8 9
124 221 233 255 450 454 678 728 784 831
Implemente um programa em Java que realize este método de ordenação. Vamos considerar que o vetor original será gerado randomicamente e que não possui mais do que 3 algarismos (valores < 1000). Com isso, garantimos que o número de iterações será 3, pois o algoritmo deve ser repetido considerando o total de algarismos que o maior valor do vetor possui.
Edmilson Guimarães
Curtidas 0