Counting sort (ordenamiento por conteo): cómo funciona, código y complejidad

Qué problema resuelve counting sort

Cualquier ordenamiento que solo compare pares de elementos necesita Ω(n log n) comparaciones en el peor caso. Counting sort evita este límite al no comparar nada: usa la propia clave como índice de un arreglo. Cuando las claves son enteros pequeños, como notas de examen de 0 a 100, edades, bytes de 0 a 255 o valoraciones de estrellas, es más rápido que cualquier ordenamiento por comparación.

El precio es una memoria proporcional al rango de las claves. Ordenar un puñado de enteros de 64 bits repartidos por todo el rango requeriría un arreglo de conteo imposiblemente grande.

La idea y un ejemplo resuelto

Ordena [4, 2, 2, 8, 3, 3, 1], cuyos valores están en el rango de 0 a 8 (k = 9).

1. Contar cada valor: count[v] es el número de veces que aparece v.
2. Sumas de prefijos: sustituye cada conteo por el número de elementos menores o iguales que ese valor. Entonces count[v] es una posición más allá de la última donde corresponde v.
3. Colocar los elementos: recorre la entrada de derecha a izquierda; para cada valor v, decrementa count[v] y escribe v en esa posición. Recorrer de derecha a izquierda mantiene los valores iguales en su orden original.

Así, el 1 va al índice 0, los dos 2 a los índices 1 y 2, los dos 3 a los índices 3 y 4, el 4 al índice 5 y el 8 al índice 6. Resultado: [1, 2, 2, 3, 3, 4, 8].

Implementación en Python

Esta versión estable ordena cualquier objeto por una clave entera entre 0 y k - 1.

def counting_sort(items, k, key=lambda x: x):
    """Stable sort of items by integer key in range(k)."""
    count = [0] * k
    for x in items:
        count[key(x)] += 1
    for v in range(1, k):                # prefix sums
        count[v] += count[v - 1]
    out = [None] * len(items)
    for x in reversed(items):            # right to left: stable
        count[key(x)] -= 1
        out[count[key(x)]] = x
    return out

print(counting_sort([4, 2, 2, 8, 3, 3, 1], k=9))
# [1, 2, 2, 3, 3, 4, 8]
people = [("Ana", 3), ("Bo", 1), ("Cy", 3), ("Di", 2)]
print(counting_sort(people, k=4, key=lambda p: p[1]))
# [('Bo', 1), ('Di', 2), ('Ana', 3), ('Cy', 3)]

Cuando solo ordenas enteros simples y no necesitas estabilidad, una versión más sencilla reconstruye la salida a partir de los conteos. Esta variante también maneja números negativos desplazando por el mínimo:

def counting_sort_ints(nums):
    if not nums:
        return []
    lo, hi = min(nums), max(nums)
    count = [0] * (hi - lo + 1)
    for x in nums:
        count[x - lo] += 1
    out = []
    for offset, c in enumerate(count):
        out.extend([offset + lo] * c)
    return out

print(counting_sort_ints([3, -1, 2, -1, 0]))   # [-1, -1, 0, 2, 3]

Complejidad temporal y espacial

Counting sort es lineal cuando k es O(n). Si k es mucho mayor que n, por ejemplo 1.000 valores en el rango de 0 a 10⁹, el arreglo de conteo domina y es mejor un ordenamiento por comparación o radix sort.

Cómo se compara counting sort con otros ordenamientos

Aquí k es el tamaño del rango de claves, d el número de dígitos y b la base que usa radix sort. Counting sort es estable cuando los elementos se colocan usando sumas de prefijos de derecha a izquierda. La versión simple que reconstruye a partir de los conteos produce el mismo resultado con enteros simples, pero no puede llevar otros datos junto con la clave.

Variantes y errores comunes

• Radix sort ejecuta un counting sort estable una vez por dígito, lo que extiende la idea a enteros grandes y cadenas de longitud fija.
• Bucket sort reparte los valores en cubetas por rango y ordena cada cubeta; es rápido cuando los valores están distribuidos de forma uniforme.
• Contar sin ordenar: a menudo solo necesitas los conteos, por ejemplo para construir un histograma o encontrar la moda. collections.Counter lo hace directamente.

Cuándo usar counting sort

Úsalo cuando las claves sean enteros de un rango pequeño en comparación con el número de elementos: calificaciones, edades, días del mes, bytes, valores de canales de color de 0 a 255 o valores pequeños de enumeraciones. También es el paso interno de radix sort y de los algoritmos de construcción de arreglos de sufijos. En las entrevistas aparece en preguntas como sort colors (valores 0, 1, 2), ordenar por frecuencia y el índice H, y en la clásica pregunta de cómo superar el límite O(n log n) de los ordenamientos por comparación.