Dígitos leídos
Movimientos
Pasada

  • Cubeta en uso
  • Recién movida
  • Copiadas de vuelta
  • En su sitio

Más sobre el ordenamiento radix

Ordenamiento radix

El ordenamiento radix ordena números enteros sin comparar nunca dos de ellos. Ordena la lista por el dígito de las unidades, luego por el de las decenas, luego por el de las centenas, y cada vez mueve los valores a diez cubetas y los copia de vuelta en orden. Mira cómo se llenan las cubetas en la fila bajo la lista, movimiento a movimiento, y cómo la lista queda ordenada por cada vez más dígitos. Pulsa Reproducir para ver la ordenación, o Paso y Atrás para avanzar de movimiento en movimiento. Arrastra el control de pasos para saltar a cualquier punto. Las cubetas del 0 al 9 están una junto a otra en la fila bajo la lista. Los recuadros cuentan dígitos leídos, movimientos y pasadas. Elige cuántas barras hay, cómo empiezan, o escribe tus propios números hasta 999. Con el tablero seleccionado, las flechas avanzan paso a paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.

Cómo funciona

  1. Elige cuántas barras hay y cómo empiezan, o escribe tus propios números enteros hasta 999 para ver la pasada de las centenas.
  2. Pulsa Reproducir, o usa Paso y Atrás para avanzar de valor en valor. Arrastra el control de pasos para saltar a cualquier punto de la ordenación.
  3. Observa cada pasada: se cuentan los dígitos, se mueve cada valor a su cubeta y luego se copian las cubetas de vuelta.

Cómo funciona el ordenamiento radix

Mira solo el último dígito de cada número y ordena la lista por él: pon cada número en una de diez cubetas, del 0 al 9, en el orden en que llegan, y luego copia las cubetas de vuelta una tras otra. Haz lo mismo con el dígito de las decenas y luego con el de las centenas. Como cada pasada mantiene el orden de los números que comparten un dígito, las pasadas anteriores siguen decidiendo su orden, y tras la última pasada toda la lista está ordenada.

Sin ninguna comparación

Los ordenamientos por comparación necesitan al menos unas n log₂ n comparaciones en el peor caso, usen el truco que usen. El ordenamiento radix esquiva ese límite leyendo dígitos: cada pasada lee un dígito de cada valor y mueve cada valor dos veces, así que d dígitos requieren d pasadas y el trabajo crece con n · d. Con listas largas de claves cortas compensa: un millón de números hasta 999 requiere tres pasadas, mientras que un ordenamiento por comparación necesita unos 20 millones de comparaciones. El precio es que solo funciona con claves formadas por dígitos o caracteres, y necesita espacio para las cubetas.

Preguntas frecuentes

¿Cómo funciona el ordenamiento radix?

Ordena los números por su último dígito, luego por el dígito anterior, y así hasta el primero. Cada pasada reparte los números en diez cubetas según ese dígito, manteniendo su orden, y copia las cubetas de vuelta. Tras la pasada del dígito más significativo, la lista está ordenada.

¿Por qué empezar por el último dígito?

Porque cada pasada es estable: los números con el mismo dígito mantienen el orden que les dieron las pasadas anteriores. Así, la última pasada, la del primer dígito, decide el orden, y los empates se resuelven con los dígitos ya ordenados. Esto se llama ordenamiento radix LSD (least significant digit, dígito menos significativo).

¿Es el ordenamiento radix más rápido que quicksort?

Puede serlo con muchas claves cortas: su trabajo crece con el número de valores por el número de dígitos, sin n log n. Con pocos valores, claves muy largas o datos que no están formados por dígitos, quicksort y merge sort suelen ser más rápidos y sencillos.

¿Qué relación tiene con el ordenamiento por cuentas?

Cada pasada del ordenamiento radix es un ordenamiento por cuentas sobre un dígito: cuenta cuántos valores tienen cada dígito, calcula dónde empieza cada cubeta y mueve ahí los valores en orden.

¿Se envían mis números a algún sitio?

No. La ordenación se hace en tu navegador, y tus últimos ajustes se guardan en el almacenamiento local de este navegador.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Ir al editor