Radix sort (ordenamiento por residuos): cómo funciona, código y complejidad

Qué problema resuelve radix sort

Counting sort es lineal, pero necesita un arreglo de conteo tan grande como todo el rango de claves, lo que es imposible con enteros de 32 o 64 bits. Radix sort divide cada clave en dígitos pequeños y ejecuta counting sort una vez por dígito, de modo que cada pasada necesita un arreglo de conteo de solo b entradas (10 para dígitos decimales, 256 para bytes).

Funciona con cualquier clave que se pueda descomponer en una secuencia fija de símbolos pequeños: enteros no negativos, fechas escritas como YYYYMMDD, códigos de longitud fija como los códigos postales, direcciones IP y cadenas de ancho fijo.

Ejemplo resuelto: radix sort LSD en base 10

Ordena [170, 45, 75, 90, 802, 24, 2, 66]. El número mayor tiene 3 dígitos, así que hay 3 pasadas. Cada pasada es un ordenamiento estable por un dígito: los dígitos iguales conservan el orden de la pasada anterior.

Tras la pasada 2, los números están ordenados por sus dos últimos dígitos. En la pasada 3, 2, 24, 45, 66, 75 y 90 tienen todos el dígito de las centenas 0, y la estabilidad los mantiene en el orden que produjo la pasada 2. Por eso cada pasada debe ser estable.

Implementación en Python

def counting_pass(nums, exp, base):
    """Stable counting sort of nums by the digit at exp."""
    count = [0] * base
    for x in nums:
        count[(x // exp) % base] += 1
    for d in range(1, base):
        count[d] += count[d - 1]
    out = [0] * len(nums)
    for x in reversed(nums):
        d = (x // exp) % base
        count[d] -= 1
        out[count[d]] = x
    return out

def radix_sort(nums, base=10):
    """LSD radix sort for non-negative integers."""
    if not nums:
        return []
    exp, biggest = 1, max(nums)
    while biggest // exp > 0:
        nums = counting_pass(nums, exp, base)
        exp *= base
    return nums

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]
print(radix_sort([3, 0, 1, 0], base=256))   # [0, 0, 1, 3]

Usar base 256 significa que cada pasada examina un byte, así que los enteros de 32 bits necesitan solo 4 pasadas. Para incluir números negativos, ordena por separado los valores negativos y los no negativos y únelos, o desplaza todas las claves por el mínimo. Para cadenas de longitud fija, usa el código del carácter en la posición i como dígito y recorre de la última posición a la primera.

Complejidad temporal y espacial

Cuando d es una constante (claves de ancho fijo) y b se elige cercano a n o un valor fijo como 256, el tiempo es O(n). Para n claves todas distintas, d debe ser al menos log_b n, así que radix sort no supera a O(n log n) con claves de tamaño arbitrario; es rápido porque cada paso es una operación simple sobre un arreglo.

Cómo se compara radix sort con otros ordenamientos

En la tabla, n es el número de claves, k el rango de claves de counting sort, d el número de dígitos y b la base. Radix sort LSD es estable siempre que cada pasada por dígito sea estable. Necesita claves con una estructura fija, mientras que los ordenamientos por comparación como merge sort y quicksort funcionan con cualquier orden, incluidas las funciones de comparación personalizadas.

LSD frente a MSD y errores comunes

Cuándo usar radix sort

Radix sort encaja bien con arreglos grandes de enteros o claves de ancho fijo, como identificadores de 32 bits, marcas de tiempo, direcciones IPv4 o cadenas de longitud fija, sobre todo en GPU y en bibliotecas de alto rendimiento, donde su acceso regular a la memoria compensa. Se usa en la construcción de arreglos de sufijos y en algunas cargas de bases de datos y gráficos. Para listas normales de Python, sorted() casi siempre es más rápido en la práctica porque se ejecuta en código C optimizado. En las entrevistas, radix sort aparece cuando se pregunta cómo ordenar en tiempo lineal, por ejemplo en el problema Maximum Gap.