Clasificación de raíz

En informática, radix sort es un algoritmo de clasificación no comparativo. Evita la comparación al crear y distribuir elementos en cubos de acuerdo con su raíz. Para elementos con más de un dígito significativo, este proceso de agrupamiento se repite para cada dígito, conservando el orden del paso anterior, hasta que se hayan considerado todos los dígitos. Por esta razón, radix sort también ha sido llamado bucket sort y digital sort.

La clasificación 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

Radix sort se remonta a 1887 con el trabajo de Herman Hollerith en las máquinas tabuladoras. Los algoritmos de clasificación Radix comenzaron a ser de uso común como una forma de clasificar tarjetas perforadas ya en 1923.

El primer algoritmo informático eficiente en memoria para este método de clasificación fue desarrollado en 1954 en el MIT por Harold H. Seward. Las clasificaciones radix computarizadas anteriormente se habían descartado como poco prácticas debido a la necesidad percibida de una asignación variable de cubos de tamaño desconocido. La innovación de Seward fue usar un escaneo lineal para determinar de antemano los tamaños de depósito y las compensaciones requeridas, lo que permitió una única asignación estática de memoria auxiliar. El escaneo lineal está estrechamente relacionado con el otro algoritmo de Seward: clasificación por conteo.

En la era moderna, las ordenaciones de raíz 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 uso más general, a veces entre un 50 % y tres veces más rápido.

Un clasificador de tarjetas IBM ejecutando un radio 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 cestas de salida de la máquina, sobre la base de los datos perforados en una columna en las tarjetas. La manivela cerca de la tolva de entrada se utiliza para mover la cabeza de lectura a la siguiente columna mientras el tipo progresa. El bastidor en la parte posterior tiene tarjetas del pase de clasificación anterior.

Orden de dígitos

Las clasificaciones 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, uno podría comenzar con 1 (MSD) o 4 (LSD).

Las clasificaciones radix de LSD generalmente usan el siguiente orden de clasificación: las claves cortas vienen antes que las claves más largas, y luego las claves de la misma longitud se clasifican lexicográficamente. Esto coincide con el orden normal de las representaciones de enteros, como la secuencia [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]. Las clases de LSD son generalmente clases estables.

Las clasificaciones de base de MSD son más adecuadas para clasificar cadenas o representaciones de 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 clasificar 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 teclas más cortas estuvieran justificadas a la izquierda y rellenadas a la derecha con caracteres en blanco para que las teclas más cortas fueran tan largas como la tecla más larga. Las clasificaciones MSD no son necesariamente estables si siempre se debe mantener el orden original de las claves duplicadas.

Aparte del orden transversal, las clasificaciones MSD y LSD difieren en el manejo de la entrada de longitud variable. Las clasificaciones de LSD pueden agruparse por longitud, clasificar por radix cada grupo y luego concatenar los grupos en orden de tamaño. Las clasificaciones 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, las clasificaciones MSD se prestan más a la subdivisión y recursividad. Cada cubo creado por un paso de MSD se puede ordenar por radix utilizando el siguiente dígito más significativo, sin referencia a ningún otro cubo creado en el paso anterior. Una vez que se alcanza el último dígito, concatenar los cubos es todo lo que se requiere para completar la ordenación.

Ejemplos

Dígito menos significativo

Lista de entrada:

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

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

[{17]0, 90} {2, 802, 2}, {45, 75}, {66}

Ordenar por el siguiente dígito de la izquierda:

[ {}02, 802, 02} {45}66}, {170, 75}9#

Note que un dígito implícito 0 está preparado para los dos 2 para que 802 mantenga su posición entre ellos.

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

[ {}002, 002, 045, 066, 075, 090170} {802}

Note que 0 está prepended a todos los números de 1 o 2 dígitos.

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

Algunas implementaciones de clasificación por radix asignan espacio para 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 aparece cada dígito se almacena en una matriz.

Aunque siempre es posible predeterminar los límites de la cubeta 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 corchetes que indican cubos:

[ {}045, 075, 025, 002, 024, 066}, {}170} {802}

Observe que 170 y 802 ya están completos porque son todos los que permanecen en sus cubos, por lo que no se necesita más recidiva

Siguiente dígito:

[{ {0}02}, {025, 024}, {045}, {0}66}, {0}75}, 170, 802]

Dígito final:

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

Todo lo que queda es la concatenación:

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

Complejidad y rendimiento

El tipo Radix funciona en O()nw){displaystyle O(nw)} tiempo, donde n{displaystyle n} es el número de llaves, y w{displaystyle w} es la longitud clave. Las variantes LSD pueden alcanzar un límite inferior para w{displaystyle w} de 'la longitud de la llave media' al dividir las teclas de longitud variable en grupos como se discutió anteriormente.

Las clasificaciones 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 dificultar las implementaciones de LSD cuando el número de pases inducidos se convierte en el cuello de botella.

Variantes especializadas

Implementaciones de ordenación radix de MSD in situ

La ordenación 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 contenedor de 0 crece desde el principio de la matriz, mientras que el contenedor de 1 crece desde el final de la matriz. El límite del contenedor 0s 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 que se encuentra frente al límite del contenedor de 1s (el último elemento de la matriz), y el contenedor de 1s aumenta en un elemento al disminuir el índice del arreglo del límite de 1s. Si este bit es un 0, entonces el primer elemento permanece en su ubicación actual y el contenedor de 0s crece en un elemento. El siguiente elemento de la matriz que se examina es el que se encuentra frente al límite del contenedor de 0 (es decir, el primer elemento que no está en el contenedor de 0 ni en el contenedor de 1). Este proceso continúa hasta que el contenedor de 0 y el contenedor de 1 se encuentran. El contenedor de 0 y el contenedor de 1 se ordenan recursivamente en función del siguiente bit de cada elemento de la matriz. El procesamiento recursivo continúa hasta que se utiliza 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 de un tratamiento sin signo del resto de los bits.

La ordenación de base binaria de MSD in situ se puede extender a una base más grande y retener la capacidad en el lugar. La ordenación por conteo se utiliza para determinar el tamaño de cada contenedor y su índice inicial. El intercambio se utiliza para colocar el elemento actual en su contenedor, seguido de la expansión del límite del contenedor. A medida que se escanean los elementos de la matriz, los contenedores se saltan y solo se procesan los elementos entre contenedores, hasta que se haya procesado toda la matriz y todos los elementos terminen en sus contenedores respectivos. El número de contenedores es el mismo que el radix utilizado, p. 16 contenedores para 16 radix. Cada pase 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. Luego, cada contenedor se procesa recursivamente utilizando el siguiente dígito, hasta que se hayan utilizado todos los dígitos para la clasificación.

Ni la ordenación de raíz binaria in situ ni la ordenación de raíz de n bits, discutidas en los párrafos anteriores, son algoritmos estables.

Implementaciones estables de clasificación por radix de MSD

MSD radix sort 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 recursividad, pero intercambia la entrada y la salida en el siguiente nivel de recursividad, para evitar la sobrecarga de copiar el resultado de salida nuevamente en el búfer de entrada. Cada uno de los contenedores se procesa recursivamente, como se hace para la ordenación radix MSD in situ. Una vez completada 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 sola 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 clasificación Radix, como el método de dos pases en el que se usa la clasificación por conteo durante el primer pase de cada nivel de recursividad, tiene una gran sobrecarga constante. 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 ordenación por inserción es rápida para arreglos pequeños, estable, en el lugar y puede acelerar significativamente la ordenación radix.

Aplicación a la computación paralela

Este algoritmo de clasificación recursivo tiene una aplicación particular para la computación paralela, ya que cada uno de los contenedores se puede clasificar de forma independiente. En este caso, cada bin se pasa al siguiente procesador disponible. Se usaría un solo procesador al principio (el dígito más significativo). Para el segundo o tercer dígito, todos los procesadores disponibles probablemente estarían activados. Idealmente, a medida que cada subdivisión está completamente clasificada, 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 computación paralela para ordenar las claves.

En el nivel superior de recursividad, la oportunidad para el paralelismo se encuentra en la parte de clasificación de conteo del algoritmo. El conteo es altamente paralelo, compatible con el patrón de reducción paralela y divide bien el trabajo entre 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 recurrencia posteriores depende de los datos. Por ejemplo, si todas las claves tuvieran el mismo valor, entonces habría un solo contenedor con elementos en él y no habría paralelismo disponible. Para entradas aleatorias, todos los contenedores estarían casi igualmente poblados y estaría disponible una gran cantidad de oportunidades de paralelismo.

Hay disponibles algoritmos de ordenación en paralelo más rápidos, por ejemplo, la complejidad óptima O(log(n)) son los de los Tres Húngaros y Richard Cole y la ordenación por fusión bitónica de Batcher tiene un algoritmo complejidad de O(log²(n)), todos los cuales tienen una menor complejidad de tiempo algorítmico para ordenar radix en un COCHECITO DE TRIPULACIÓN. Las ordenaciones de 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 procesadores n mediante la realización de particiones implícitamente, también como un radixsort 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 pueden construirse de una manera que se escale sin que el número de retrasos constantes de la compuerta de salida por ciclo aumente como O(log(n)), de modo que, en efecto, una versión segmentada del mergesort bitónico de Batcher y las ordenaciones de PRAM O(log(n)) son todas O(log²( 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 retrasos de puerta que su ordenación rápida paralela y ordenación radix, o la ordenación de combinación de Cole, para un red de clasificación independiente de la longitud de clave de O(nlog²(n)).

Ordenación radix basada en árbol

La clasificación de Radix también se puede lograr creando un árbol (o árbol de Radix) a partir del conjunto de entrada y haciendo un recorrido de pedido previo. 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.