Cómo funciona
Counting Sort no compara números entre sí. Prepara un contador por cada valor
posible (k contadores, uno por tubo) y trabaja en tres fases:
1. Contar: cada número cae en el tubo de su valor; la altura de la pila es la cuenta.
2. Acumular: cada contador suma los anteriores, y así dice dónde acaba en la salida
el bloque de su valor. 3. Colocar: se recorre el array de derecha a izquierda y cada
número sale de lo alto de su tubo hacia la última posición libre de su bloque.
Paso a paso con [4, 1, 3, 4, 1, 0, 3, 1]
Valores del 0 al 4, así que k = 5. Las letras distinguen los repetidos: 1a es el primer 1.
- 01Contar:
C = [1, 3, 0, 2, 2] para los valores 0…4. El tubo del 2 se queda vacío, pero existe.
- 02Acumular:
C = [1, 4, 4, 6, 8]. El bloque de cada valor acaba en C[v]: el 0 ocupa la posición 0; los 1, de la 1 a la 3; los 3, la 4 y la 5; los 4, la 6 y la 7.
- 03Colocar de derecha a izquierda: el 1c va a la posición 3, el 3b a la 5, el 0 a la 0… Resultado:
[0, 1a, 1b, 1c, 3a, 3b, 4a, 4b]. Los iguales conservan su orden.
- ΣTotal: 0 comparaciones y 8 incrementos + 4 sumas + 8 colocaciones = 20 operaciones (2n + k − 1). Bubble Sort, con el mismo array, haría 27 comparaciones.
¿Más rápido que n·log n?
Cualquier algoritmo que ordene comparando necesita en el peor caso unas n·log₂ n
comparaciones: es un límite matemático. Counting Sort lo esquiva porque no compara, usa el valor como
índice. El precio: solo sirve para enteros (o claves que se puedan convertir en enteros) en un rango
pequeño. Ordenar 10 números entre 0 y un millón exigiría un millón de contadores.
Por qué de derecha a izquierda
Dentro de cada tubo, el último número que entró es el último de su valor en el array. Al recorrer de
derecha a izquierda, ese sale primero y ocupa el final de su bloque; el siguiente igual, la posición de
delante. Así los iguales quedan en su orden original: es estable. Radix Sort depende
de esto, porque repite Counting Sort por cada dígito.
Complejidad
- Tiempo
- O(n + k)
- Comparaciones
- 0
- Espacio extra
- O(n + k)
- Estable
- Sí
- Requisito
- Enteros en rango k
- In situ
- No