ORDENAMIENTO RADIX (RADIX SORT)
HISTORIA
En ciencias de la computación , la ordenación de radix es un algoritmo de clasificación
de enteros no comparativos que ordena datos con claves enteras agrupando las claves por
los dígitos individuales que comparten la misma posición y
valor significativos . Se requiere una notación posicional , pero debido a que los enteros
pueden representar cadenas de caracteres (por ejemplo, nombres o fechas) y números de
coma flotante formateados especialmente, la ordenación de radix no está limitada a
enteros. El género Radix se remonta hasta 1887 al trabajo de Herman Hollerith en
las máquinas de tabulación .
La mayoría de las computadoras digitales representan internamente todos sus datos como
representaciones electrónicas de números binarios, por lo que es más conveniente
procesar los dígitos de las representaciones enteras por grupos de representaciones de
dígitos binarios. Los géneros Radix pueden implementarse para comenzar en el dígito
más significativo (MSD) o en el dígito menos significativo (LSD). Por ejemplo, al
ordenar el número 1234 en una lista, uno podría comenzar con el 1 o el 4.
Las clases de LSD radix generalmente usan el siguiente orden de clasificación: las teclas
cortas vienen antes de las teclas más largas, y luego las claves de la misma longitud se
clasifican lexicográficamente . Esto coincide con el orden normal de las representaciones
enteras, como la secuencia 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11.
Los tipos de raíz de MSD usan un orden lexicográfico, que es adecuado para ordenar
cadenas, como palabras o representaciones enteras de longitud fija. Una secuencia como
"b, c, d, e, f, g, h, i, j, ba" se clasificaría lexicográficamente como "b, ba, c, d, e, f, g, h, i,
j ". Si el ordenamiento lexicográfico se usa para ordenar representaciones enteras de
longitud variable, entonces las representaciones de los números del 1 al 10 se mostrarán
como 1, 10, 2, 3, 4, 5, 6, 7, 8, 9, como si el las teclas más cortas se justificaron a la
izquierda y se rellenaron a la derecha con caracteres en blanco para hacer las teclas más
cortas siempre que la clave más larga para determinar el orden ordenado.
En informática, el ordenamiento Radix (radix sort en inglés) es un algoritmo de
ordenamiento que ordena enteros procesando sus dígitos de forma individual. Como los
enteros pueden representar cadenas de caracteres (por ejemplo, nombres o fechas) y,
especialmente, números en punto flotante especialmente formateados, radix sort no está
limitado sólo a los enteros.
La mayor parte de los ordenadores digitales representan internamente todos sus datos
como representaciones electrónicas de números binarios, por lo que procesar los dígitos
de las representaciones de enteros por representaciones de grupos de dígitos binarios es
lo más conveniente. Existen dos clasificaciones de radix sort: el de dígito menos
significativo (LSD) y el de dígito más significativo (MSD). Radix sort LSD procesa las
representaciones de enteros empezando por el dígito menos significativo y moviéndose
hacia el dígito más significativo. Radix sort MSD trabaja en sentido contrario.
Las representaciones de enteros que son procesadas por los algoritmos de ordenamiento
se les llama a menudo "claves", que pueden existir por sí mismas o asociadas a otros
datos. Radix sort LSD usa típicamente el siguiente orden: claves cortas aparecen antes
que las claves largas, y claves de la misma longitud son ordenadas de forma léxica. Esto
coincide con el orden normal de las representaciones de enteros, como la secuencia "1, 2,
3, 4, 5, 6, 7, 8, 9, 10". Radix sorts MSD usa orden léxico, que es ideal para la ordenación
de cadenas de caracteres, como las palabras o representaciones de enteros de longitud fija.
Una secuencia como "b, c, d, e, f, g, h, i, j, ba" será ordenada léxicamente como "b, ba, c,
d, e, f, g, h, i, j". Si se usa orden léxico para ordenar representaciones de enteros de
longitud variable, entonces la ordenación de las representaciones de los números del 1 al
10 será "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 espacios en blanco, para hacerlas tan largas
como la clave más larga, para el propósito de este ordenamiento, cabe destacar que este
método no funciona para la estructura de datos debido a que los ciclos for que se
implementaran marcaran error debido a las matrices bidimencionales.
DEFINICION
En informática, el ordenamiento Radix (radix sort en inglés) es un algoritmo de
ordenamiento que ordena enteros procesando sus dígitos de forma individual. Como los
enteros pueden representar cadenas de caracteres (por ejemplo, nombres o fechas) y,
especialmente, números en punto flotante especialmente formateados, radix sort no está
limitado sólo a los enteros.
