En informática , el ordenamiento por radix es un algoritmo de ordenamiento no comparativo . Evita la comparación creando y distribuyendo elementos en grupos según su radix . Para los elementos con más de un dígito significativo , este proceso de agrupamiento se repite para cada dígito, mientras se conserva el orden del paso anterior, hasta que se hayan considerado todos los dígitos. Por este motivo, el ordenamiento por radix también se ha denominado ordenamiento por grupos y ordenamiento digital .
La ordenación por radix se puede aplicar a datos que se pueden ordenar lexicográficamente , ya sean números enteros, palabras, tarjetas perforadas, naipes o el correo .
El origen de la clasificación por radix se remonta a 1887, gracias al trabajo de Herman Hollerith sobre las máquinas tabuladoras . [1] Los algoritmos de clasificación por radix comenzaron a usarse comúnmente como una forma de clasificar tarjetas perforadas ya en 1923. [2]
El primer algoritmo informático que hace un uso eficiente de la memoria para este método de ordenación fue desarrollado en 1954 en el MIT por Harold H. Seward . Las ordenaciones por radix computarizadas habían sido descartadas anteriormente por ser poco prácticas debido a la necesidad percibida de una asignación variable de contenedores de tamaño desconocido. La innovación de Seward fue utilizar un escaneo lineal para determinar de antemano los tamaños y desplazamientos de los contenedores requeridos, lo que permite una única asignación estática de memoria auxiliar. El escaneo lineal está estrechamente relacionado con el otro algoritmo de Seward: la ordenación por conteo .
En la era moderna, las ordenaciones por base se aplican más comúnmente a colecciones de cadenas binarias y números enteros . Se ha demostrado en algunos puntos de referencia que es más rápido que otros algoritmos de ordenación de propósito más general, a veces entre un 50 % y tres veces más rápido. [3] [4] [5]
Las ordenaciones por base se pueden implementar para comenzar con el dígito más significativo (MSD) o el dígito menos significativo (LSD). Por ejemplo, con 1234 , se podría comenzar con 1 (MSD) o 4 (LSD).
Los ordenamientos por radix LSD suelen utilizar el siguiente orden de clasificación: las claves cortas van antes que las claves más largas y, a continuación, las claves de la misma longitud se ordenan lexicográficamente . Esto coincide con el orden normal de las representaciones de números enteros, como la secuencia [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] . Los ordenamientos LSD son, por lo general, ordenamientos estables .
Los ordenamientos de base MSD son los más adecuados para ordenar cadenas o representaciones de números enteros de longitud fija. Una secuencia como [b, c, e, d, f, g, ba] se ordenaría como [b, ba, c, d, e, f, g] . Si se utiliza el ordenamiento lexicográfico para ordenar números enteros de longitud variable en base 10, los números del 1 al 10 se generarían como [1, 10, 2, 3, 4, 5, 6, 7, 8, 9] , como si las claves más cortas estuvieran justificadas a la izquierda y rellenadas a la derecha con caracteres en blanco para hacer que las claves más cortas sean tan largas como la clave más larga. Los ordenamientos MSD no son necesariamente estables si siempre se debe mantener el ordenamiento original de las claves duplicadas.
Aparte del orden de recorrido, las ordenaciones MSD y LSD difieren en su manejo de la entrada de longitud variable. Las ordenaciones LSD pueden agrupar por longitud, ordenar por base cada grupo y luego concatenar los grupos en orden de tamaño. Las ordenaciones MSD deben "extender" efectivamente todas las claves más cortas al tamaño de la clave más grande y ordenarlas en consecuencia, lo que puede ser más complicado que la agrupación requerida por LSD.
Sin embargo, las ordenaciones MSD son más fáciles de subdividir y recursar. Cada contenedor creado por un paso MSD puede ordenarse por radio utilizando el siguiente dígito más significativo, sin referencia a ningún otro contenedor creado en el paso anterior. Una vez que se llega al último dígito, concatenar los contenedores es todo lo que se necesita para completar la ordenación.
Lista de entrada:
Comenzando por el dígito más a la derecha (el último), ordene los números según ese dígito:
Ordenar por el siguiente dígito a la izquierda:
Y finalmente por el dígito más a la izquierda:
Cada paso requiere sólo una pasada sobre los datos, ya que cada elemento puede colocarse en su contenedor sin comparación con ningún otro elemento.
Algunas implementaciones de ordenamiento por base asignan espacio para los contenedores contando primero la cantidad de claves que pertenecen a cada contenedor antes de mover las claves a esos contenedores. La cantidad de veces que aparece cada dígito se almacena en una matriz .
Si bien siempre es posible predeterminar los límites de los depósitos mediante conteos, algunas implementaciones optan por utilizar la asignación de memoria dinámica en su lugar.
Lista de entrada, cadenas numéricas de ancho fijo con ceros a la izquierda:
Primer dígito, entre paréntesis que indican los depósitos:
Siguiente dígito:
Dígito final:
Lo único que queda es la concatenación:
La ordenación por radix funciona en función del tiempo, donde es el número de claves y es la longitud de la clave. Las variantes de LSD pueden alcanzar un límite inferior para la "longitud de clave promedio" al dividir las claves de longitud variable en grupos, como se explicó anteriormente.
Los ordenamientos por radix optimizados pueden ser muy rápidos cuando se trabaja en un dominio que les conviene. [6] Están limitados a datos lexicográficos, pero para muchas aplicaciones prácticas esto no es una limitación. Los tamaños de clave grandes pueden dificultar las implementaciones de LSD cuando el número inducido de pasadas se convierte en el cuello de botella. [2]
La ordenación por radix binaria MSD, también llamada ordenación rápida binaria, se puede implementar en el lugar dividiendo la matriz de entrada en dos contenedores: el contenedor de 0 y el contenedor de 1. El contenedor de 0 se hace crecer desde el principio de la matriz, mientras que el contenedor de 1 se hace crecer desde el final de la matriz. El límite del contenedor de 0 se coloca antes del primer elemento de la matriz. El límite del contenedor de 1 se coloca después del último elemento de la matriz. Se examina el bit más significativo del primer elemento de la matriz. Si este bit es un 1, entonces el primer elemento se intercambia con el elemento delante del límite del contenedor de 1 (el último elemento de la matriz), y el contenedor de 1 se hace crecer en un elemento disminuyendo el índice de la matriz del límite de 1. Si este bit es un 0, entonces el primer elemento permanece en su ubicación actual, y el contenedor de 0 se hace crecer en un elemento. El siguiente elemento de la matriz examinado es el que está delante del límite del contenedor de 0 (es decir, el primer elemento que no está en el contenedor de 0 o en el contenedor de 1). Este proceso continúa hasta que el contenedor de 0 y el contenedor de 1 se alcanzan entre sí. Luego, el contenedor de 0 y el contenedor de 1 se ordenan de forma recursiva según el siguiente bit de cada elemento de la matriz. El procesamiento recursivo continúa hasta que se haya utilizado el bit menos significativo para la ordenación. [7] [8] El manejo de números enteros con signo en complemento a dos requiere tratar el bit más significativo con el sentido opuesto, seguido del tratamiento sin signo del resto de los bits.
La ordenación por base binaria MSD in situ se puede ampliar a bases mayores y conservar la capacidad in situ. La ordenación por conteo se utiliza para determinar el tamaño de cada bin y su índice inicial. El intercambio se utiliza para colocar el elemento actual en su bin, seguido de la expansión del límite del bin. A medida que se escanean los elementos de la matriz, se omiten los bins y solo se procesan los elementos entre bins, hasta que se haya procesado toda la matriz y todos los elementos terminen en sus respectivos bins. La cantidad de bins es la misma que la base utilizada, por ejemplo, 16 bins para 16 bases. Cada pasada se basa en un solo dígito (por ejemplo, 4 bits por dígito en el caso de 16 bases), comenzando desde el dígito más significativo . Luego, cada bin se procesa de forma recursiva utilizando el siguiente dígito, hasta que se hayan utilizado todos los dígitos para la ordenación. [9] [10]
Ni el ordenamiento de base binaria en el lugar ni el ordenamiento de base de n bits, analizados en los párrafos anteriores, son algoritmos estables .
El ordenamiento por radix MSD puede implementarse como un algoritmo estable, pero requiere el uso de un búfer de memoria del mismo tamaño que la matriz de entrada. Esta memoria adicional permite escanear el búfer de entrada desde el primer elemento de la matriz hasta el último, y mover los elementos de la matriz a los contenedores de destino en el mismo orden. Por lo tanto, los elementos iguales se colocarán en el búfer de memoria en el mismo orden en que estaban en la matriz de entrada. El algoritmo basado en MSD utiliza el búfer de memoria adicional como salida en el primer nivel de recursión, pero intercambia la entrada y la salida en el siguiente nivel de recursión, para evitar la sobrecarga de copiar el resultado de salida de nuevo al búfer de entrada. Cada uno de los contenedores se procesa de forma recursiva, como se hace para el ordenamiento por radix MSD en el lugar. Una vez que se ha completado el ordenamiento por el último dígito, se verifica el búfer de salida para ver si es la matriz de entrada original, y si no lo es, se realiza una sola copia. Si el tamaño del dígito se elige de modo que el tamaño de la clave dividido por el tamaño del dígito sea un número par, se evita la copia al final. [11]
La ordenación por radix, como el método de dos pasadas en el que se utiliza la ordenación por conteo durante la primera pasada de cada nivel de recursión, tiene una gran sobrecarga constante. Por lo tanto, cuando los contenedores se hacen pequeños, se deben utilizar otros algoritmos de ordenación, como la ordenación por inserción . Una buena implementación de la ordenación por inserción es rápida para matrices pequeñas, estable, in situ y puede acelerar significativamente la ordenación por radix.
Este algoritmo de ordenamiento recursivo tiene una aplicación particular en la computación paralela , ya que cada uno de los contenedores se puede ordenar de forma independiente. En este caso, cada contenedor se pasa al siguiente procesador disponible. Se utilizaría un solo procesador al principio (el dígito más significativo). Para el segundo o tercer dígito, probablemente se utilizarían todos los procesadores disponibles. Lo ideal sería que, a medida que cada subdivisión se ordena por completo, se utilizarían cada vez menos procesadores. En el peor de los casos, todas las claves serán idénticas o casi idénticas entre sí, con el resultado de que habrá poca o ninguna ventaja en utilizar la computación paralela para ordenar las claves.
En el nivel superior de recursión, la oportunidad de paralelismo está en la parte de ordenamiento por conteo del algoritmo. El conteo es altamente paralelo, se presta al patrón parallel_reduce y divide bien el trabajo entre múltiples núcleos hasta alcanzar el límite de ancho de banda de memoria. Esta parte del algoritmo tiene paralelismo independiente de los datos. Sin embargo, el procesamiento de cada contenedor en los niveles de recursión subsiguientes depende de los datos. Por ejemplo, si todas las claves tuvieran el mismo valor, entonces solo habría un contenedor con cualquier elemento en él y no habría paralelismo disponible. Para entradas aleatorias, todos los contenedores estarían poblados casi por igual y habría una gran cantidad de oportunidad de paralelismo disponible. [12]
Hay algoritmos de ordenamiento paralelo más rápidos disponibles, por ejemplo, la complejidad óptima O(log( n )) son los de los Tres Húngaros y Richard Cole [13] [14] y el ordenamiento por fusión bitónica de Batcher tiene una complejidad algorítmica de O(log 2 ( n )), todos los cuales tienen una complejidad de tiempo algorítmica menor que el ordenamiento por radix en una CREW- PRAM . Los ordenamientos PRAM más rápidos conocidos fueron descritos en 1991 por David MW Powers con un ordenamiento rápido paralelizado que puede operar en tiempo O(log(n)) en una CRCW-PRAM con n procesadores realizando particiones implícitamente, así como un ordenamiento por radix que opera usando el mismo truco en O( k ), donde k es la longitud de clave máxima. [15] Sin embargo, ni la arquitectura PRAM ni un solo procesador secuencial pueden construirse de manera que se escalen sin que el número de retardos de compuerta de abanico constante por ciclo aumente como O(log( n )), de modo que, en efecto, una versión segmentada del ordenamiento por fusión bitónico de Batcher y los ordenamientos PRAM O(log( n )) son todos O(log 2 ( n )) en términos de ciclos de reloj, y Powers reconoce que el de Batcher tendría constantes más bajas en términos de retardos de compuerta que su ordenamiento rápido paralelo y ordenamiento por radix, o el ordenamiento por fusión de Cole , para una red de ordenamiento independiente de la longitud de clave de O(nlog 2 ( n )). [16]
La ordenación por radix también se puede lograr construyendo un árbol (o árbol de radix ) a partir del conjunto de entrada y haciendo un recorrido previo al orden . Esto es similar a la relación entre la ordenación por heap y la estructura de datos del montón . Esto puede ser útil para ciertos tipos de datos, consulte la ordenación por ráfagas .
