Orden de radix - Radix sort

Orden de radix
Clase Algoritmo de clasificación
Estructura de datos Formación
Rendimiento en el peor de los casos , donde n es el número de claves y w es la longitud de la clave.
Complejidad espacial en el peor de los casos

En informática , la ordenación por radix es un algoritmo de ordenación no comparativo . Evita la comparación creando y distribuyendo elementos en cubos de acuerdo con su base . Para 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 esta razón, la ordenación por radix también se ha denominado ordenación por cubeta y ordenación digital .

La clasificación por radix se puede aplicar a los datos que se pueden clasificar lexicográficamente , ya sean números enteros, palabras, tarjetas perforadas, naipes o el correo .

Historia

La ordenación por radix se remonta a 1887 con el trabajo de Herman Hollerith en las máquinas de tabulación . Los algoritmos de clasificación por radix se hicieron de uso común como una forma de clasificar tarjetas perforadas ya en 1923.

El primer algoritmo informático de memoria eficiente fue desarrollado en 1954 en el MIT por Harold H. Seward . Anteriormente, los tipos de radix computarizados se habían descartado como poco prácticos debido a la necesidad percibida de una asignación variable de cubos de tamaño desconocido. La innovación de Seward fue utilizar un escaneo lineal para determinar de antemano los tamaños de cubeta y las compensaciones requeridas, lo que permite una única asignación estática de memoria auxiliar. El escaneo lineal está estrechamente relacionado con el otro algoritmo de Seward: el tipo de conteo .

En la era moderna, los tipos de radix se aplican más comúnmente a colecciones de cadenas binarias y enteros . Se ha demostrado en algunos puntos de referencia que es más rápido que otros algoritmos de clasificación de propósito más general, a veces entre un 50% y tres veces más rápido.

Un clasificador de tarjetas de IBM que realiza una clasificación de base en un gran conjunto de tarjetas perforadas . Las tarjetas se introducen en una tolva debajo de la barbilla del operador y se clasifican en una de las 13 canastas de salida de la máquina, según los datos perforados en una columna de las tarjetas. La manivela cerca de la tolva de entrada se usa para mover el cabezal de lectura a la siguiente columna a medida que avanza la clasificación. El estante en la parte posterior contiene tarjetas de la pasada de clasificación anterior.

Orden de dígitos

Los ordenamientos de radix se pueden implementar para comenzar en el dígito más significativo (MSD) o en el dígito menos significativo (LSD). Por ejemplo, con 1234 , se podría comenzar con 1 (MSD) o 4 (LSD).

Las clasificaciones de LSD radix suelen utilizar el siguiente orden de clasificación: las claves cortas aparecen 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 tipos de LSD son generalmente tipos estables .

Los ordenamientos de base de MSD son los más adecuados para ordenar cadenas o representaciones enteras 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 usa el orden lexicográfico para ordenar 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 el las claves más cortas se justificaron a la izquierda y se rellenaron a la derecha con caracteres en blanco para hacer que las claves más cortas fueran tan largas como la clave más larga. Las clasificaciones de MSD no son necesariamente estables si siempre se debe mantener el orden original de las claves duplicadas.

Aparte del orden transversal, los tipos MSD y LSD difieren en su manejo de la entrada de longitud variable. Los tipos de LSD pueden agruparse por longitud, ordenar por base a cada grupo y luego concatenar los grupos en orden de tamaño. Las clasificaciones de MSD deben "extender" 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, los tipos de MSD son más susceptibles de subdivisión y recursión. Cada segmento creado por un paso de MSD puede ordenarse por sí mismo utilizando el siguiente dígito más significativo, sin referencia a ningún otro segmento creado en el paso anterior. Una vez que se alcanza el último dígito, concatenar los depósitos es todo lo que se requiere para completar la clasificación.

Ejemplos de

Dígito menos significativo

Lista de entrada (base 10):

[170, 45, 75, 90, 2, 802, 2, 66]

Comenzando por el (último) dígito más a la derecha, ordene los números según ese dígito:

[{17 0 , 9 0 }, { 2 , 80 2 , 2 }, {4 5 , 7 5 }, {6 6 }]

Ordenar por el siguiente dígito de la izquierda:

[{ 0 2, 8 0 2, 0 2}, { 4 5}, { 6 6}, {1 7 0, 7 5}, { 9 0}]
Observe que se antepone un dígito 0 implícito a los dos 2 para que 802 mantenga su posición entre ellos.

Y finalmente por el dígito más a la izquierda:

[{ 0 0 2, 0 0 2, 0 45, 0 66, 0 75, 0 90}, { 1 70}, { 8 02}]
Observe que se antepone un 0 a todos los números de 1 o 2 dígitos.

Cada paso requiere una sola pasada sobre los datos, ya que cada elemento se puede colocar en su contenedor sin compararlo con ningún otro elemento.

Algunas implementaciones de ordenación de radix asignan espacio para los depósitos contando primero la cantidad de claves que pertenecen a cada depósito antes de mover las claves a esos depósitos. El número de veces que ocurre cada dígito se almacena en una matriz .

Aunque siempre es posible predeterminar los límites del depósito mediante recuentos, algunas implementaciones optan por utilizar la asignación de memoria dinámica en su lugar.

Dígito más significativo, recursivo hacia adelante

Lista de entrada, cadenas numéricas de ancho fijo con ceros a la izquierda:

[170, 045, 075, 025, 002, 024, 802, 066]

Primer dígito, con paréntesis que indican cubos:

[{ 0 45, 0 75, 0 25, 0 02, 0 24, 0 66}, { 1 70}, { 8 02}]
Tenga en cuenta que 170 y 802 ya están completos porque son todo lo que queda en sus depósitos, por lo que no se necesita más recursividad

Siguiente dígito:

[{{0 0 2}, {0 2 5, 0 2 4}, {0 4 5}, {0 6 6}, {0 7 5}}, 170, 802]

Dígito final:

[002, {{02 4 }, {02 5 }}, 045, 066, 075, 170, 802]

Todo lo que queda es la concatenación:

[002, 024, 025, 045, 066, 075, 170, 802]

Complejidad y rendimiento

La ordenación por radix opera en tiempo O ( nw ), donde n es el número de claves yw es la longitud de la clave. Las variantes de LSD pueden lograr un límite inferior para w de 'longitud promedio de clave' al dividir claves de longitud variable en grupos como se discutió anteriormente.

Las clasificaciones de radix optimizadas pueden ser muy rápidas cuando se trabaja en un dominio que les conviene. Están restringidos a datos lexicográficos, pero para muchas aplicaciones prácticas esto no es una limitación. Los tamaños de clave grandes pueden obstaculizar las implementaciones de LSD cuando el número inducido de pasadas se convierte en el cuello de botella.

Variantes especializadas

Implementaciones de ordenación de radix de MSD in situ

La ordenación por radix MSD binaria, 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 bin de 0s crece desde el principio de la matriz, mientras que el bin de 1s crece desde el final de la matriz. El límite del contenedor de ceros se coloca antes del primer elemento de la matriz. El límite de bin 1s 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 frente al límite del grupo de 1s (el último elemento de la matriz), y el grupo de 1s aumenta en un elemento al disminuir el índice de la matriz de límite de 1s. Si este bit es un 0, entonces el primer elemento permanece en su ubicación actual y el intervalo de ceros aumenta en un elemento. El siguiente elemento de la matriz examinado es el que está delante del límite del intervalo de ceros (es decir, el primer elemento que no está en el intervalo de ceros ni en el intervalo de 1). Este proceso continúa hasta que el contenedor de 0 y el contenedor de 1 se encuentran entre sí. El bin de 0s y el bin de 1s se ordenan de forma recursiva basándose en 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 clasificación. El manejo de enteros con signo requiere tratar el bit más significativo con el sentido opuesto, seguido del tratamiento sin signo del resto de los bits.

La clasificación de base binaria de MSD en el lugar se puede extender a una base más grande y mantener la capacidad en el lugar. La clasificación por recuento se utiliza para determinar el tamaño de cada contenedor y su índice inicial. El intercambio se usa para colocar el elemento actual en su contenedor, seguido de expandir el límite del contenedor. A medida que se escanean los elementos de la matriz, se omiten los contenedores y solo se procesan los elementos entre los contenedores, hasta que se haya procesado toda la matriz y todos los elementos terminen en sus respectivos contenedores. El número de bins es el mismo que el de la base utilizada, por ejemplo, 16 bins para 16 radix. Cada pasada se basa en un solo dígito (por ejemplo, 4 bits por dígito en el caso de 16 radix), comenzando desde el dígito más significativo . A continuación, cada contenedor se procesa de forma recursiva utilizando el siguiente dígito, hasta que se hayan utilizado todos los dígitos para la clasificación.

Ni la ordenación de base binaria en el lugar ni la ordenación de base de n bits, discutidas en los párrafos anteriores, son algoritmos estables .

Implementaciones estables de ordenación de radix de MSD

La ordenación por radix de MSD se puede implementar 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 usa el búfer de memoria adicional como salida en el primer nivel de recursividad, pero intercambia la entrada y la salida en el siguiente nivel de recursividad, para evitar la sobrecarga de copiar el resultado de salida en el búfer de entrada. Cada uno de los contenedores se procesa de forma recursiva, como se hace para la clasificación de base MSD in situ. Una vez que se ha completado la clasificación por el último dígito, se comprueba el búfer de salida para ver si es la matriz de entrada original y, si no lo es, se realiza una única copia. Si el tamaño del dígito se elige de manera 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.

Enfoques híbridos

La ordenación por radix, como el método de dos pasadas donde se usa la ordenación por conteo durante la primera pasada de cada nivel de recursividad, tiene una sobrecarga constante grande. Por lo tanto, cuando los contenedores se vuelven pequeños, se deben usar otros algoritmos de clasificación, como la clasificación por inserción . Una buena implementación de la ordenación por inserción es rápida para arreglos pequeños, estable, en el lugar y puede acelerar significativamente la ordenación por base.

Aplicación a la computación paralela

Tenga en cuenta que este algoritmo de clasificación recursiva tiene una aplicación particular a la computación en paralelo , ya que cada uno de los contenedores se puede clasificar de forma independiente. En este caso, cada bandeja se pasa al siguiente procesador disponible. Se utilizaría un solo procesador al principio (el dígito más significativo). En el segundo o tercer dígito, es probable que todos los procesadores disponibles estén conectados. Idealmente, como cada subdivisión está completamente ordenada, 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 el uso de la computación paralela para ordenar las claves.

En el nivel superior de recursividad, la oportunidad de paralelismo está en la parte de ordenación de conteo del algoritmo. El conteo es muy paralelo, compatible con el patrón paralelo_reduce y divide bien el trabajo en varios núcleos hasta alcanzar el límite de ancho de banda de la memoria. Esta parte del algoritmo tiene un paralelismo independiente de los datos. Sin embargo, el procesamiento de cada contenedor en niveles de recursividad posteriores 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 las entradas aleatorias, todos los contenedores estarían casi igualmente poblados y estaría disponible una gran cantidad de oportunidades de paralelismo.

Tenga en cuenta que hay disponibles algoritmos de clasificación en paralelo más rápidos, por ejemplo, la complejidad óptima O (log ( n )) son los de los tres húngaros y la clasificación de fusión bitónica de Richard Cole y Batcher tiene una complejidad algorítmica de O (log 2 ( n )) , todos los cuales tienen una complejidad de tiempo algorítmica más baja para ordenar por radix en un CREW- PRAM . Las clasificaciones PRAM más rápidas conocidas fueron descritas en 1991 por David Powers con una ordenación rápida paralelizada que puede operar en tiempo O (log (n)) en una CRCW-PRAM con n procesadores realizando particiones implícitamente, así como una ordenación radical que opera usando el mismo truco en O ( k ), donde k es la longitud de clave máxima. Sin embargo, ni la arquitectura PRAM ni un solo procesador secuencial se pueden construir de una manera que se escale sin que el número de retrasos constantes de la puerta de salida por ciclo aumente como O (log ( n )), por lo que, en efecto, una versión canalizada del mergesort bitónico de Batcher y el O (log ( n )) PRAM son todos O (log 2 ( n )) en términos de ciclos de reloj, con Powers reconociendo que Batcher's tendría una constante más baja en términos de retardos de puerta que su Quicksort Parallel y ordenación por radix, o ordenación por fusión de Cole , para una red de ordenación de O (nlog 2 ( n )) independiente de la longitud de clave .

Ordenación por radix basada en Trie

La clasificación de radix también se puede lograr construyendo un trie (o árbol de radix ) a partir del conjunto de entrada y haciendo un recorrido de preorden . Esto es similar a la relación entre heapsort y la estructura de datos del montón . Esto puede ser útil para ciertos tipos de datos, consulte burstsort .

Ver también

Referencias

enlaces externos