Radix Sort y su complejidad temporal.

"En informática, el ordenamiento Radix (radix sort en inglés) es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual. Como los enteros pueden representar cadenas de caracteres (por ejemplo, nombres o fechas) y, especialmente, números en punto flotante especialmente formateados, radix sort no está limitado sólo a los enteros." (Extraído de http://es.wikipedia.org/wiki/Ordenamiento_Radix).

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] + " ");

//        }

    }

    public static void pruebaTiempoEjecucion(int[] arr, int op) {

        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;
        }

    }

    public static int[] aVector(int[][] x, int n, int m) {//Paso una matriz a vector
        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];//3OE
        int[] 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++) {//4OE
                for (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++) {//4OE
            node[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;//2OE
                front[i] = -1;//2OE
            } /*fin del for */

            /* Procesar cada elemento en la lista */

            while (first != -1) {//1OE
                p = 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];//2OE
                if (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++) {//4OE
            x[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];
                }
            }
        }
    }

    public static void mostrar(int[][] x, int n, int m) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(x[i][j] + " ");
            }
            System.out.println("");
        }
    }

    public static int digito(int x, int digito) {
        for (int i = 0; i < digito - 1; i++) {
            x = x / 10;
        }
        return x % 10;
    }
}