Last active
August 29, 2015 14:22
-
-
Save marcelocmenezes/1c5dcf9c10e1e7fed00f to your computer and use it in GitHub Desktop.
Radix Sort em Java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Radix { | |
public static int[] lista = { 110, 420, 565, 986, 101, 622, 383, 74, 233, 857 }; //Lista desordenada que utilizaremos. | |
public static int dec = 3; //Número máximo de cada numero inteiro. Pra não ficar infinito. | |
/** | |
* | |
* Método Main, método principal onde roda a aplicação. | |
* | |
*/ | |
public static void main(String[] args) throws Exception { | |
lista = radix(lista); | |
for (int i = 0; i < lista.length; i++) { | |
System.out.println(lista[i]); | |
} | |
} | |
/** | |
* | |
* Método Radix | |
* | |
* @retorna nossa lista ordenada | |
* | |
*/ | |
public static int[] radix(int[] in) { | |
for(int i = 0; i < dec; i++) { | |
in = sort(in, i+1); | |
} | |
return in; | |
} | |
/** | |
* | |
* Método Sort | |
* | |
* @retorna uma ordenação por posição. | |
* | |
*/ | |
public static int[] sort(int[] in, int pos) { | |
int[] contador = new int[10]; | |
int[] out = new int[in.length]; | |
for(int i = 0; i < in.length; i++) { | |
int digito = getDigito(in[i], pos); | |
contador[digito]++; | |
} | |
for (int i = 1; i < contador.length; i++) { | |
contador[i] += contador[i-1]; | |
} | |
for(int i = in.length - 1; i >= 0; i--) { | |
int digito = getDigito(in[i], pos); | |
out[contador[digito]-1] = in[i]; | |
contador[digito]--; | |
} | |
return out; | |
} | |
/** | |
* | |
* Método getDigito | |
* | |
* @retorna algarismo de uma determinada posição. | |
* | |
*/ | |
private static int getDigito(int digito, int posicao){ | |
if (posicao <= 1) { | |
return digito%10; | |
} else { | |
return getDigito(digito/10, posicao -1); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment