Radix

1 ESTRUCTURA DE DATOS (ING.)

UNIDAD 6. ORDENACION INTERNA

M.C. ROSA MARIA MICHEL NAVA

6.2 ALGORITMOS DE ORDENAMIENTO POR DISTRIBUCION. 6.2.1 RADIX. A este método también se le llama “ordenamiento de raíz”. Este ordenamiento se basa en los valores de los dígitos reales en las representaciones de posiciones de los números que se ordenan. Por ejemplo, el número 235 en notación decimal se escribe con un 2 en la posición de centenas, un 3 en la posición de decenas y un 5 en la posición de unidades. 1. Tome cada número en el orden en el cual aparecen en el archivo y colóquelos en una de las diez colas (0...9) dependiendo del valor del dígito que es procesado. 2. Empezando con la cola de los números con dígito 0 y terminando con la cola de números con dígito 9. Retorne los números al archivo original en el orden en el cual fueron colocados en la cola, (empezar con el dígito menos significativo y concluir con el más significativo). Reglas para ordenar: El más grande de dos enteros de igual longitud se determina del modo siguiente: 1. Empezar en el dígito más significativo y avanzar por los dígitos menos significativos mientras coinciden los dígitos correspondientes en los dos números. 2. El número con el dígito más grande en la primera posición en la cual los dígitos de los dos números no coinciden es el mayor de los dos (por supuesto sí coinciden todos los dígitos de ambos números, son iguales). Características y análisis de eficiencia de este método: 1. Debido a que el ciclo for (k = 1; k <= m; k++) externo se recorre m veces (una para cada dígito) y el ciclo interior n veces (una para cada elemento en el archivo) el ordenamiento es de aproximadamente (m*n). Es decir, los requerimientos del tiempo para el método depende del número de dígitos (m) y el número de elementos del archivo (n). El ordenamiento es de O(m*n). 2. Si las llaves son complejas (es decir, si casi cada número que puede ser una llave lo es en realidad) m se aproxima a log n, por lo que (m*n) se aproxima a (n log n). 3. Si la cantidad de dígitos es grande, en ocasiones es más eficiente ordenar el archivo aplicando primero el ordenamiento de raíz a los dígitos más significativos y después utilizando inserción simple sobre el archivo ya reorganizado. En casos donde la mayoría de los registros del archivo tengan diferente número de dígitos significativos, este proceso elimina pasos innecesarios en los dígitos menos significativos. Ventajas: 1. El ordenamiento es razonablemente eficiente si el número de dígitos en las llaves no es demasiado grande. 2. Si las máquinas tienen la ventaja de ordenar los dígitos (sobre todo si están en binario) lo ejecutarían con mucho mayor rapidez de lo que ejecutan una comparación de dos llaves completas. Desventajas: 1. Se requiere conocer la cantidad de dígitos del valor máximo (para saber cuando el método ya acomodó

2 ESTRUCTURA DE DATOS (ING.)

UNIDAD 6. ORDENACION INTERNA

M.C. ROSA MARIA MICHEL NAVA

todos los elementos). 2. Se requiere de espacio para almacenar los punteros del frente y de la parte posterior de la cola, además de un campo adicional en cada registro que se utiliza como puntero a la lista encadenada. Suponiendo que se quiere ordenar n números, cada uno de ellos compuesto de k dígitos. El siguiente es un ejemplo con n = 10 y k = 5 (número de dígitos por número). 73895 93754 82149 99046 04853 94171 54963 70471 80564 66496 Imaginando que estos dígitos forman parte de una matriz, podemos decir que a [i, j] es el j-ésimo del iésimo elemento del conjunto. Es fácil, en una pasada, ordenar el conjunto de la llave de ordenación es un solo dígito, por ejemplo el tercero de izquierda a derecha: 99046 82149 94171 70471 66496 80564 93754 73895 04853 54963 Para ordenar un conjunto de llaves completas, repetimos el proceso dígito por dígito, en cada pasada separando los elementos según el valor del dígito respectivo, luego recolectándolos para formar una sola cola, y realimentando el proceso con esos mismos datos. El conjunto completo queda finalmente ordenado si los dígitos se van tomando de derecha a izquierda. Como hay que realizar k pasadas y cada una de ellas toma tiempo O(N), el tiempo total es O(k N), que es el tamaño del archivo de entrada (en bytes). Por lo tanto, la ordenación tomó un tiempo lineal en el tamaño de los datos. A continuación, se muestra el procedimiento que se sigue para este ordenamiento: // Se define un arreglo de N registros o estructuras que contengan un campo de información y uno como puntero para almacenar la dirección del nodo siguiente. // FRENTE y POSTERIOR son arreglos auxiliares

3 ESTRUCTURA DE DATOS (ING.)

UNIDAD 6. ORDENACION INTERNA

M.C. ROSA MARIA MICHEL NAVA

// X es el arreglo original con los valores a ordenar // EXP, PRIMERO, I, J, K, P, Q y Y son variables de tipo entero RADIX( X[ ], N) { Para I desde 0 y mientras I < N–1 Hacer{ NODO[ I ]. INFO = X[ I ] y NODO[ I ]. SIG = I + 1; } Hacer NODO[ N–1 ]. INFO = X[ N–1 ], NODO[ N–1 ]. SIG = -1 y PRIMERO = 0; Para K desde 1 y Mientras K sea menor o igual que el total de dígitos Hacer { Para I desde 0 hasta 9 Hacer { FRENTE[ I ] = -1 y POSTERIOR[ I ] = -1; } EXP = Elevar 10 a la K–1; Repetir Mientras (PRIMERO != -1) { Hacer P = PRIMERO, PRIMERO = NODO[ PRIMERO ]. SIG, Y = NODO[ P ]. INFO, J = Residuo de dividir ((Y entre EXP) entre 10) y Q = POSTERIOR[ J ]; Si (Q = -1) entonces Hacer FRENTE[ J ] = P; De lo contrario Hacer NODO[ Q ]. SIG = P; Hacer POSTERIOR[ J ] = P; } Para J desde 0 y Mientras J < 10 y FRENTE[ J ] = -1 Hacer Incrementar J; Hacer PRIMERO = FRENTE[ J ]; Repetir Mientras (J <= 9){ Para I desde J+1 y Mientras I < 10 y FRENTE[ I ] = -1 Hacer Incrementar I; Si (I <= 9) entonces { Hacer P=I y NODO[ POSTERIOR[ J ] ]. SIG = FRENTE[ I ]; } Hacer J = I; } Si (POSTERIOR[P] != -1) Hacer NODO[ POSTERIOR[ P ] ]. SIG = -1; } Para I desde 0 hasta N–1 Hacer { X[ I ]= NODO[ PRIMERO ]. INFO y PRIMERO = NODO[ PRIMERO ]. SIG; } }