Ordenamiento radix

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 13 de marzo de 2019; las comprobaciones requieren 12 ediciones .
ordenamiento radix
Autor Hollerith, Herman
objetivo Algoritmo de clasificación
Estructura de datos formación
peor momento , donde w es el número de bits necesarios para almacenar cada clave.
costo de memoria
 Archivos multimedia en Wikimedia Commons

La clasificación bit a bit ( eng.  radix sort ) es un algoritmo de clasificación que se ejecuta en tiempo lineal. Hay opciones estables .

Algoritmo

Inicialmente destinado a ordenar números enteros escritos como dígitos. Pero dado que en la memoria de las computadoras cualquier información se registra como números enteros, el algoritmo es adecuado para clasificar cualquier objeto, cuyo registro se puede dividir en "dígitos" que contienen valores comparables. Por ejemplo, de esta manera puede ordenar no solo números escritos como un conjunto de números, sino también cadenas que son un conjunto de caracteres y, en general, valores arbitrarios en la memoria, representados como un conjunto de bytes.

La comparación se realiza poco a poco: primero se comparan los valores de un dígito extremo y se agrupan los elementos según los resultados de esta comparación, luego se comparan los valores del dígito siguiente, adyacente, y los elementos se ordenan por los resultados de comparar los valores de este dígito dentro de los grupos formados en el paso anterior, o se reordenan como un todo, pero conservando el orden relativo logrado por el ordenamiento anterior. Luego se hace lo mismo para la siguiente descarga, y así hasta el final.

Dado que es posible alinear los registros comparados entre sí en diferentes direcciones, en la práctica existen dos opciones para esta clasificación. En el caso de los números, se denominan en función del significado de los dígitos del número, y resulta así: puede alinear las entradas de los números hacia los dígitos menos significativos (en el lado derecho, hacia las unidades, el dígito menos significativo, LSD ) o dígitos más significativos (en el lado izquierdo, de dígitos más significativos, dígito más significativo, MSD).

Con la clasificación LSD (clasificación con alineación por el dígito menos significativo, a la derecha, a unos), se obtiene el orden apropiado para los números. Por ejemplo: 1, 2, 9, 10, 21, 100, 200, 201, 202, 210. Es decir, aquí los valores primero se ordenan por unidades, luego se ordenan por decenas, manteniendo la ordenación por unidades dentro decenas, luego por centenas, manteniendo la ordenación por decenas y unidades dentro de las centenas, etc.

La clasificación MSD (orden alto, alineado a la izquierda) da como resultado un orden alfabético, que es apropiado para clasificar líneas de texto. Por ejemplo, "b, c, d, e, f, g, h, i, j, ba" se ordenará como "b, ba, c, d, e, f, g, h, i, j". Si se aplica MSD a los números dados en el ejemplo, obtenemos la secuencia 1, 10, 100, 2, 200, 201, 202, 21, 210, 9.

Puede acumular información sobre grupos en cada paso de diferentes maneras, por ejemplo, en listas, en árboles, en matrices, escribiendo los elementos en sí o sus índices, etc.

Existe una versión inestable de la clasificación bit a bit recursiva, que se realiza directamente en la matriz ordenada: en la primera pasada, el movimiento va uno hacia el otro, al comienzo de la matriz, se busca un elemento con 1 en el primer dígito de bit, al final de la matriz, se busca un elemento con 0 en el mismo dígito. Los elementos encontrados se intercambian, y así sucesivamente hasta que los índices en cuestión coincidan. Así, al comienzo de la matriz, antes del punto de encuentro de los índices, se recopilan todos los elementos con un bit igual a 0, y después de este índice, todos los elementos con un bit igual a 1. Luego, de forma recursiva, puede de manera completamente similar iterar a través de los subrangos resultantes de la matriz, comparando los valores del segundo bit y los subsiguientes, y reorganizando los lugares de los elementos.

Solicitud de filas en la variante de clasificación de la cesta

La ordenación de canasta se puede usar para ordenar por rango . Cada categoría se corre dos veces. En el primer pase, se cuenta el número de ciertos valores en esta categoría. Luego, para cada valor posible, se preparan arreglos para almacenar los elementos con ese valor. Durante el segundo paso, los propios elementos se escriben en estas matrices. Es posible una implementación eficiente mediante el uso de una matriz de referencias de cadena en lugar de las propias cadenas, y una matriz adicional de "tamaños de contenedor" inicializados en el primer paso con el número de elementos en cada "contenedor".

La segunda y posteriores pasadas se realizan por separado sobre cada cesta obtenida en la pasada anterior, dividiéndola en "subcestas" y comparando el segundo y siguientes caracteres de las cadenas, respectivamente.

La operación finaliza cuando se alcanza la longitud máxima de la cadena o cuando todas las "subcanastas" tienen una longitud de 1.

Notas

Literatura

Enlaces

 Algoritmos de clasificación
Teoría Complejidad O notación relación de orden Ordenar tipos sostenible Interno Externo
Intercambio
Elección
inserciones
fusión
sin comparaciones
híbrido
Otro
poco práctico