A continuación se presenta un programa con tres ejemplos diferentes de algoritmos de ordenamiento Radix y se evalúa cuanto tarda cada uno en ordenar tres arreglos generados al azar. Este programa fue hecho en el IDE Netbeans 6.9.
EL CÓDIGO
public class Main {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
int[] arr = new int[10000];for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 1024);
}
int[] arr2 = new int[10000];
for (int i = 0; i < arr2.length; i++) {
arr2[i] = (int) (Math.random() * 1024);
}
int[] arr3 = new int[10000];
for (int i = 0; i < arr3.length; i++) {
arr3[i] = (int) (Math.random() * 1024);
}
System.out.println("Con un ejemplo Radix Sort: ");
pruebaTiempoEjecucion(arr, 1);
System.out.println("Con Radix Sort optimizado: ");
pruebaTiempoEjecucion(arr3, 3);
System.out.println("Con mi Radix Sort: ");
pruebaTiempoEjecucion(arr2, 2);
// System .out.print("original: ");
// for(int i=0;i<arr.length;i++){
// arr[i] = (int)(Math .random() * 1024);
// System .out.print(arr[i] + " ");
// }
// radixSort1(arr);
// System.out.println("El arreglo original");
// for (int i = 0; i < arr2.length; i++) {
// System.out.print(arr2[i] + " ");
// }
// System.out.println("");
// int[] ord = radixSort(arr2);
// System.out.println("El arreglo ordenado por radixSort");
// for (int i = 0; i < ord.length; i++) {
// System.out.print(ord[i] + " ");
// }
}switch (op) {
case 1:
double antes = System.currentTimeMillis();
radixSort1(arr);
double despues = System.currentTimeMillis();
System.out.println(despues - antes + " Milisegundos ");
break;
case 2:
double antes1 = System.currentTimeMillis();
int[] ord = radixSort(arr);
double despues1 = System.currentTimeMillis();
System.out.println(despues1 - antes1 + " Milisegundos ");
break;
case 3:
double antes2 = System.currentTimeMillis();
radixSortC(arr, arr.length);
double despues2 = System.currentTimeMillis();
System.out.println(despues2 - antes2 + " Milisegundos ");
break;
}
}
ArrayList<Integer> aux = new ArrayList<Integer>();
for (int k = 0; k < n; k++) {
for (int l = 0; l < m; l++) {
if (x[k][l] != 0) {
aux.add(x[k][l]);
} else {
l = m;
}
}
}
int[] ord = new int[aux.size()];
for(int i=0;i<aux.size();i++){
ord[i]=aux.get(i);
}
return ord;
}
/*
* Operaciones Elementales OE=38
* Complejidad O:6+4n(8n(4n)+3n+3+4n(6n))=O(n^3)
*/
public static int[] radixSort(int[] aux) {
/*LSD es la matriz donde se ordenaran los datos de acuerdo
*al digito que se esté analizando, bien sea el primero, los
*de la mitad o el último*/
int[][] lsd = new int[10][aux.length];//3OEint[] x = aux;//2OE//Vector donde se organizarán los datos
for (int d = 1; d < 5; d++){//4OE //Máximo 4 dígitos
for (int i = 0; i < x.length; i++) {//4OE//Analiza el número en la posición i
int pos = 0;//1OE
int digit = digito(x[i], d);//3OE//Extrae el dígito que se necesita
while (lsd[digit][pos] != 0){ //2OE
pos++;//2OE
}
lsd[digit][pos] = x[i];//3OE//Ubica el número de acuerdo al dígito analizado
}
x = aVector(lsd, 10, x.length);//3OE//Ordena la matriz LSD en el vector
/*Se reinicia la matriz LSD para que no haya redundancia de datos*/
for (int i = 0; i < 10; i++) {//4OEfor (int j = 0; j < x.length; j++) {//4OE
lsd[i][j] = 0;//2OE
}
}
}
return x;//1OE
/*
* Extraído de:
* http://es.wikipedia.org/wiki/Ordenamiento_Radix
* Y transformado a Java
* Operaciones Elementales OE=98
* Complejidad O:7+10n+9+4n(8n+22n+7n+2+1n(8n)+7n+3)+9n=O(n^3)
*/
public static void radixSortC(int x[], int n) {int[] front = new int[10];//2OE
int[] rear = new int[10];//2OE
int[][] node = new int[n][2];//2OE
int exp, first, i, j, k, p = 0, q, y;//1OE
/* Inicializar una lista vinculada */
for (i = 0; i < n - 1; i++) {//4OEnode[i][0] = x[i];//3OE
node[i][1] = i + 1;//3OE
} /* fin del for */
node[n - 1][0] = x[n - 1];//5OE
node[n - 1][1] = -1;//3OE
first = 0;//1OE /* first es la cabeza de la lista vinculada */
for (k = 1; k < 5; k++) {//4OE
/* Suponer que tenemos números de cuatro dígitos */
for (i = 0; i < 10; i++) {//4OE
/*Inicializar colas */
rear[i] = -1;//2OEfront[i] = -1;//2OE
} /*fin del for */
/* Procesar cada elemento en la lista */
while (first != -1) {//1OEp = first;//1OE
first = node[first][1];//2OE
y = node[p][0];//2OE
/* Extraer el kâsimo dÁgito */
exp = (int) Math.pow(10, k - 1);//4OE /* elevar 10 a la (k-1)ésima potencia */j = (y / exp) % 10;//3OE
/* Insertar y en queue[j] */
q = rear[j];//2OEif (q == -1) {//1OE
front[j] = p;//2OE
} else {
node[q][1] = p;//2OE
}
rear[j] = p;//2OE
} /*fin del while */
/* En este punto, cada registro está en su cola basándose en el dígito k
Ahora formar una lista única de todos los elementos de la cola.
Encontrar el primer elemento. */
for (j = 0; j < 10 && front[j] == -1; j++);//7OE;
first = front[j];//2OE
/* Vincular las colas restantes */
while (j <= 9) {//1OE /* Verificar si se ha terminado */
/*Encontrar el elemento siguiente */
for (i = j + 1; i < 10 && front[i] == -1; i++);//8OE;
if (i <= 9) {//1OE
p = i;//1OE
node[rear[j]][1] = front[i];//4OE
} /* fin del if */
j = i;//1OE
} /* fin del while */
node[rear[p]][1] = -1;//3OE
} /* fin del for */
/* Copiar de regreso al archivo original */
for (i = 0; i < n; i++) {//4OEx[i] = node[first][0];//3OE
first = node[first][1];//2OE
} /*fin del for */
} /* fin de radixsort*/
/**
* http://foro.elhacker.net/java/algoritmo_radix_sort_en_java-t276529.0.html
* @param arr
*/
public static void radixSort1(int[] arr) {if (arr.length == 0) {
return;
}
int[][] np = new int[arr.length][2];
int[] q = new int[0x100];
int i, j, k, l, f = 0;
for (k = 0; k < 4; k++) {
for (i = 0; i < (np.length - 1); i++) {
np[i][1] = i + 1;
}
np[i][1] = -1;
for (i = 0; i < q.length; i++) {
q[i] = -1;
}
for (f = i = 0; i < arr.length; i++) {
j = ((0xFF << (k << 3)) & arr[i]) >> (k << 3);
if (q[j] == -1) {
l = q[j] = f;
} else {
l = q[j];
while (np[l][1] != -1) {
l = np[l][1];
}
np[l][1] = f;
l = np[l][1];
}
f = np[f][1];
np[l][0] = arr[i];
np[l][1] = -1;
}
for (l = q[i = j = 0]; i < 0x100; i++) {
for (l = q[i]; l != -1; l = np[l][1]) {
arr[j++] = np[l][0];
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(x[i][j] + " ");
}
System.out.println("");
}
}
for (int i = 0; i < digito - 1; i++) {
x = x / 10;
}
return x % 10;
}
}