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, la ordenación por radix también se ha denominado ordenación por cubo y ordenación digital .
La ordenación Radix se puede aplicar a los datos que se pueden ordenar lexicográficamente , ya sean números enteros, palabras, tarjetas perforadas, naipes o el correo .
Radix sort se remonta a 1887 con el trabajo de Herman Hollerith sobre las máquinas tabuladoras . [1] Los algoritmos de clasificación Radix comenzaron a ser de uso común como una forma de clasificar tarjetas perforadas ya en 1923. [2]
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 utilizar un escaneo lineal para determinar de antemano los tamaños de cubeta y las compensaciones requeridas, lo que permitió una sola 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 clasificaciones 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. [3] [4] [5]
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).
