Ordenamientos sin comparación: counting, radix, bucket

De qué trata este capítulo

Hay un teorema que dice que ningún ordenamiento puede bajar de O(n log n). Y es cierto —para los ordenamientos que funcionan comparando elementos. Este capítulo trata del hueco en esa regla: si en lugar de comparar elementos usas sus valores como índices de un array, puedes ordenar en O(n). Counting sort cuenta cuántos hay de cada valor; radix sort lo hace dígito por dígito; bucket sort reparte por rangos. Los tres corren en tiempo lineal con los datos adecuados, y counting sort, en el duelo de este capítulo, de hecho le gana al sorted de Python optimizado en C —una de las raras veces en que el código hecho a mano escala mejor que la librería. El precio es la generalidad: esto solo funciona con enteros de rango acotado.

Un poco de historia

Radix sort es más viejo que la computadora. En 1890 Herman Hollerith construyó máquinas tabuladoras eléctricas para procesar el censo de Estados Unidos, y sus clasificadoras de tarjetas funcionaban por radix: ordenaban una pila de tarjetas perforadas por una columna, luego por la siguiente, repartiendo físicamente las tarjetas dígito por dígito —exactamente el radix sort por dígito menos significativo de este capítulo, hecho con metal y cartón. Esa maquinaria fundó la empresa que se convirtió en IBM. Counting sort lo describió Harold Seward en 1954, junto con el radix sort construido encima, en uno de los primeros tratamientos sistemáticos del ordenamiento en una computadora de programa almacenado. Así que estos algoritmos enmarcan el nacimiento de la computación: radix sort corría en tabuladoras de 1890, y counting sort estuvo entre las primeras cosas escritas para las máquinas de los cincuenta. Son anteriores a quicksort, y nunca los han superado en lo suyo: ordenar enteros acotados en tiempo lineal.

La intuición

Todos los ordenamientos por comparación hacen la misma pregunta una y otra vez: ¿este elemento es mayor que aquel? Counting sort hace una pregunta distinta: ¿cuántos elementos son iguales a cada valor? Si tus valores son enteros de 0 a k, arma un array de k+1 contadores, recorre la entrada incrementando el contador de cada valor que veas, y ya sabes exactamente cuántos hay de cada uno. Lee los contadores de vuelta en orden —count[0] ceros, luego count[1] unos, y así— y eso es la salida ordenada. No ocurrió ni una sola comparación; ordenaste contando.

Counting sort necesita un contador por cada valor posible, así que solo es práctico cuando el rango k es chico. Radix sort quita ese límite: ordena por el último dígito (un counting sort sobre apenas diez cubetas), luego por el penúltimo, hasta el más significativo y —como cada pasada es estable— el array queda completamente ordenado después de d pasadas. Bucket sort lo aborda por otro lado: parte el rango de valores en cubetas, deja caer cada elemento en la suya, ordena las cubetas chiquitas y las concatena. Cuando los datos están repartidos parejo, cada cubeta es diminuta y todo el proceso es lineal. Tres formas de ordenar sin comparar, cada una cambiando generalidad por velocidad.

Complejidad: cómo escala

Counting sort es $O(n + k)$: una pasada sobre los n elementos para contar, una pasada sobre los k contadores para emitir. Cuando k es comparable a n (o menor), eso es $O(n)$ —lineal. Radix sort es $O(d \cdot (n + b))$ para d dígitos en base b; con b fijo en 10 y d chico (un entero de 32 bits son 10 dígitos decimales), es lineal en n. Bucket sort es $O(n)$ esperado cuando los datos están distribuidos uniformemente entre sus cubetas, y se degrada hacia el costo de su ordenamiento interno cuando no lo están. La gráfica ordena enteros acotados y muestra a counting sort quedando por debajo incluso de Timsort:

Con 160000 enteros en el rango 0–1000, counting sort tardó unos 3.9 ms contra los 12.8 ms de Timsort —3.3 veces más rápido que el sort en C de la librería, desde Python puro, porque hace un solo conteo lineal donde Timsort hace n log n comparaciones. Ese es el premio de usar la herramienta especializada correcta.

En qué es bueno y en qué no

Estos ordenamientos son la opción correcta cuando tus llaves son enteros acotados —y eso es más común de lo que suena. Edades, días del año, valores de byte, IDs chicos, calificaciones de examen, prioridades: todos son enteros acotados, todos ordenables en tiempo lineal. Counting sort además es el bloque estable que vive dentro de radix sort, y es el ordenamiento más rápido posible cuando k es chico. Cuando los datos encajan con sus supuestos, nada les gana.

Pero esos supuestos son estrictos, y violarlos es una trampa. El costo de counting sort es $O(n + k)$, así que un rango amplio es fatal —ordenar un puñado de valores que llegan hasta mil millones reservaría mil millones de contadores. Solo ordenan enteros (o llaves que puedas mapear a enteros), así que nada de objetos arbitrarios, ni comparadores personalizados, ni flotantes en general. Y el tiempo lineal de bucket sort asume distribución pareja; dale datos amontonados y se degrada. Para ordenar cosas comparables arbitrarias de propósito general, un ordenamiento por comparación sigue siendo la respuesta. Estos son especialistas.

Los datos, o las entradas

El duelo ordena enteros con un rango de llaves deliberadamente chico (0–1000) para que el O(n + k) de counting sort sea genuinamente O(n), más un rango más amplio (hasta un millón) para radix sort. La animación cuenta doce enteros chicos, para que puedas ver el histograma de conteos construirse elemento por elemento y comprobar que no se comparan dos elementos en ningún momento.

Constrúyelo, una función a la vez

Counting sort es la base: cuenta por valor y luego lee los conteos de vuelta en orden:

def counting_sort(a, probe=None):
    """O(n + k) for integers in [0, k): sort by COUNTING, not comparing. Tally how
    many of each value there are, then read the tallies back out in order. There is
    not a single comparison between elements — which is exactly how it dodges the
    O(n log n) comparison bound."""
    if not a:
        return []
    k = max(a) + 1
    count = [0] * k
    for x in a:
        count[x] += 1                    # the whole sort is this tally
        if probe is not None:
            probe.append({"counts": list(count), "current": x})
    out = []
    for value in range(k):
        out.extend([value] * count[value])
    return out

Radix sort apila counting sorts estables, uno por dígito, empezando por el menos significativo, para manejar un rango amplio con solo diez cubetas por pasada:

def radix_sort(a):
    """O(d * (n + b)) for non-negative integers: sort digit by digit, least-
    significant first, using a STABLE counting sort on each digit. With d digits in
    base b (10 here), it's linear when d is small — how you sort large integers or
    fixed-width keys without a huge count array."""
    if not a:
        return []
    out = list(a)
    place = 1
    while max(out) // place > 0:
        out = _counting_by_digit(out, place)
        place *= 10
    return out


def _counting_by_digit(a, place):
    count = [0] * 10
    for x in a:
        count[(x // place) % 10] += 1
    for d in range(1, 10):
        count[d] += count[d - 1]         # prefix sums → output positions
    out = [0] * len(a)
    for x in reversed(a):                # reversed keeps equal digits stable
        d = (x // place) % 10
        count[d] -= 1
        out[count[d]] = x
    return out

Y bucket sort reparte por rangos, ordena cada cubeta chiquita y las concatena:

def bucket_sort(a, num_buckets=16):
    """O(n) expected for evenly-spread data: scatter elements into buckets by value
    range, sort each (small) bucket, then concatenate. Fast when the input is
    roughly uniform, because each bucket ends up tiny."""
    if not a:
        return []
    lo, hi = min(a), max(a)
    if lo == hi:
        return list(a)
    span = (hi - lo) / num_buckets
    buckets = [[] for _ in range(num_buckets)]
    for x in a:
        idx = min(int((x - lo) / span), num_buckets - 1)
        buckets[idx].append(x)
    out = []
    for bucket in buckets:
        out.extend(sorted(bucket))       # each bucket is small → cheap
    return out

Míralo funcionar

Aquí está counting sort contando doce valores. Cada barra es un valor; su altura es cuántas veces se ha visto ese valor. Avanza paso a paso y observa cómo se construye el histograma: cada cuadro lee un elemento de entrada y sube su barra (naranja) en uno. Ese es todo el esfuerzo de ordenamiento —ninguna barra se compara nunca con otra, solo se acumulan. Cuando termina el recorrido, leer las barras de izquierda a derecha da la salida ordenada directamente: todos los 1, luego todos los 2, y así. Ordenar contando, no comparando:

El código completo

Ambas versiones en un solo lugar —cambia entre ellas. La pestaña desde cero tiene los tres ordenamientos lineales. La pestaña de librería es sorted —un ordenamiento por comparación, y la referencia a la que estos le ganan en su propia cancha. Este es el raro capítulo donde el código hecho desde cero puede escalar genuinamente mejor que la librería, porque explota un hecho sobre los datos (llaves enteras acotadas) que un sort general no puede aprovechar.

"""Non-comparison sorts — counting, radix, and bucket — that beat the O(n log n)
barrier by not comparing elements at all. Any sort that works by comparing pairs
needs at least n log n comparisons; these sidestep that lower bound entirely by using
the keys themselves as array indices. When the keys are bounded integers, they run in
linear time.

The catch is in the "when": they only work on integers (or things you can treat as
integers), and their speed depends on the key range, not just the count.
"""


# region: counting
def counting_sort(a, probe=None):
    """O(n + k) for integers in [0, k): sort by COUNTING, not comparing. Tally how
    many of each value there are, then read the tallies back out in order. There is
    not a single comparison between elements — which is exactly how it dodges the
    O(n log n) comparison bound."""
    if not a:
        return []
    k = max(a) + 1
    count = [0] * k
    for x in a:
        count[x] += 1                    # the whole sort is this tally
        if probe is not None:
            probe.append({"counts": list(count), "current": x})
    out = []
    for value in range(k):
        out.extend([value] * count[value])
    return out
# endregion


# region: radix
def radix_sort(a):
    """O(d * (n + b)) for non-negative integers: sort digit by digit, least-
    significant first, using a STABLE counting sort on each digit. With d digits in
    base b (10 here), it's linear when d is small — how you sort large integers or
    fixed-width keys without a huge count array."""
    if not a:
        return []
    out = list(a)
    place = 1
    while max(out) // place > 0:
        out = _counting_by_digit(out, place)
        place *= 10
    return out


def _counting_by_digit(a, place):
    count = [0] * 10
    for x in a:
        count[(x // place) % 10] += 1
    for d in range(1, 10):
        count[d] += count[d - 1]         # prefix sums → output positions
    out = [0] * len(a)
    for x in reversed(a):                # reversed keeps equal digits stable
        d = (x // place) % 10
        count[d] -= 1
        out[count[d]] = x
    return out
# endregion


# region: bucket
def bucket_sort(a, num_buckets=16):
    """O(n) expected for evenly-spread data: scatter elements into buckets by value
    range, sort each (small) bucket, then concatenate. Fast when the input is
    roughly uniform, because each bucket ends up tiny."""
    if not a:
        return []
    lo, hi = min(a), max(a)
    if lo == hi:
        return list(a)
    span = (hi - lo) / num_buckets
    buckets = [[] for _ in range(num_buckets)]
    for x in a:
        idx = min(int((x - lo) / span), num_buckets - 1)
        buckets[idx].append(x)
    out = []
    for bucket in buckets:
        out.extend(sorted(bucket))       # each bucket is small → cheap
    return out
# endregion

"""There's no non-comparison sort in Python's standard library — `sorted` is Timsort,
a comparison sort. That's the honest counterpart, and the point of the face-off is
that on bounded-integer data, a linear counting or radix sort can actually beat the
O(n log n) library sort — one of the few times hand-rolled code out-scales the
built-in, because it uses a fact about the data (integer keys, bounded range) that a
general comparison sort can't.
"""


# region: sort_builtin
def sort_builtin(a):
    """Timsort — an O(n log n) comparison sort. The general-purpose baseline the
    linear sorts are trying to beat on their home turf (bounded integers)."""
    return sorted(a)
# endregion

Desde cero vs librería

El triunfo de 3.3× de counting sort sobre Timsort es el titular, y es real: con enteros acotados, un conteo lineal le gana a un ordenamiento por comparación n log n incluso cruzando la brecha entre Python y C. Pero radix sort cuenta la otra mitad de la historia: con los mismos 160000 elementos sobre un rango amplio tardó unos 90 ms, más lento que los 12.8 ms de Timsort, a pesar de ser también lineal. ¿Por qué? Su constante. Radix hizo siete pasadas (una por cada dígito decimal de una llave de rango millón), cada una un counting sort completo en Python interpretado, y siete pasadas de Python pierden contra una pasada de C afinado. Es la lección del factor constante del primer capítulo, vista por ambos lados a la vez: counting sort gana porque su constante es diminuta y hace una sola pasada; radix pierde porque su constante —d pasadas de Python— pesa más que su mejor clase asintótica en este caso. Big-O te dice que counting y radix son ambos lineales; el benchmark te dice cuál lineal gana de verdad.

Dónde te lo vas a encontrar

Radix y counting sort corren dondequiera que las llaves sean enteros acotados y la velocidad importe. Las bases de datos aplican radix sort a columnas enteras y de ancho fijo; las GPUs usan radix sort como su primitiva fundamental porque paraleliza hermosamente (sin comparaciones, solo repartir en cubetas). Counting sort es la forma estándar de ordenar por una llave categórica pequeña —agrupar registros por estado, prioridad o día. Bucket sort está detrás de la construcción de histogramas y del particionamiento espacial. Y cualquier tarea de "ordena esto por un byte, un dígito o un enum chico" en código crítico de rendimiento es un counting o radix sort disfrazado. Los ordenamientos por comparación son la herramienta general; estos son los que hacen rápido el camino caliente.

Para llevar

Los ordenamientos sin comparación —counting, radix, bucket— rompen la barrera de O(n log n) usando las llaves como índices en vez de compararlas, corriendo en $O(n)$ sobre enteros acotados. Counting sort cuenta por valor ($O(n + k)$, así que cuidado con el rango k); radix ordena dígito por dígito para manejar rangos amplios con cubetas chicas; bucket sort reparte y concatena para datos repartidos parejo. Son especialistas —estrictos con su entrada, imbatibles dentro de ella— y counting sort es uno de los pocos lugares donde tu propio código puede ganarle de verdad a la librería.

Con esto se cierra el arco de ordenamientos: seis capítulos, desde los ordenamientos elementales O(n²) hasta los ordenamientos por comparación demostrablemente óptimos O(n log n) y estos especialistas O(n). Los dos capítulos restantes del nivel dejan de acomodar datos para encontrar dentro de ellos: búsqueda binaria, que necesita los datos ordenados (ya conoces seis maneras de dejarlos así), y quickselect, que encuentra el k-ésimo elemento más pequeño en O(n) usando la partición de quicksort —sin ordenar en absoluto.