Ordenamiento por cuentas
El ordenamiento por cuentas no ordena comparando valores. Si sabes que cada valor es un número entero entre, por ejemplo, 1 y 40, puedes simplemente contar cuántos hay de cada uno y, a partir de las cuentas, saber dónde va cada uno. Con un rango pequeño, ordenar no puede ser mucho más rápido.
Contar
Busca el valor menor y el mayor y crea un contador para cada valor intermedio, todos empezando en cero. Lee la lista una vez de principio a fin y suma uno al contador de cada valor que veas. Ahora los contadores forman un histograma: cuántos 1, cuántos 2, y así sucesivamente. Con n valores y k contadores, esto lleva n pasos.
Sumar
Los valores iguales al menor van primero, así que su tramo empieza en el lugar 1. El tramo del siguiente valor empieza justo después, y así sucesivamente: cada tramo empieza tras la suma de todas las cuentas anteriores. Estos totales acumulados, llamados sumas de prefijos, convierten el histograma en un mapa de la lista ordenada. Esto lleva k pasos.
Colocar
Lee la lista por segunda vez y mueve cada valor al siguiente lugar libre de su tramo. Como los valores se mueven en el orden en que aparecen, los valores iguales conservan su orden original: el ordenamiento por cuentas es estable. Copia el búfer de vuelta y la lista queda ordenada. La aplicación muestra cómo cada contador vuelve a bajar a medida que se colocan sus valores.
Un ejemplo
Toma 4, 1, 3, 4, 2, 1, 4. Los contadores de 1 a 4 terminan en 2, 1, 1 y 3. Al sumar salen los tramos: los 1 en los lugares 1 y 2, el 2 en el lugar 3, el 3 en el lugar 4 y los 4 en los lugares 5 a 7. Al colocar los valores en el orden de la lista sale 1, 1, 2, 3, 4, 4, 4: 7 valores contados, 14 movimientos, 4 contadores y ninguna comparación.
Cuándo usarlo
El trabajo total crece con n + k. Cuando k es pequeño frente a n, como mil notas de examen de 0 a 100, el ordenamiento por cuentas es más rápido que cualquier ordenamiento por comparación, que necesita unas n log₂ n comparaciones. Cuando el rango es amplio, derrocha: unos pocos valores repartidos hasta un millón necesitan un millón de contadores. El ordenamiento radix lo resuelve aplicando el ordenamiento por cuentas una vez por dígito, así que cada pasada solo necesita diez contadores. Harold Seward describió el ordenamiento por cuentas, junto con el ordenamiento radix, en 1954.
Explóralo
Abre la aplicación y pulsa Paso. La franja entre la lista y la fila del búfer muestra un contador por valor. Observa cómo se llenan los contadores mientras se lee la lista, cómo aparecen los tramos en el búfer al sumar las cuentas y cómo los contadores vuelven a bajar a medida que se colocan los valores. Elige pocos valores distintos para ver tramos grandes, o escribe números muy separados para ver cuántos contadores necesita un rango amplio.
Preguntas frecuentes
¿Cuál es la complejidad temporal del ordenamiento por cuentas?
O(n + k) para n valores y k valores posibles, y O(n + k) de memoria extra para los contadores y el búfer.
¿Por qué el ordenamiento por cuentas no siempre es el más rápido?
Porque su coste depende del rango de los valores, no solo de cuántos hay. Si el rango es mucho mayor que la lista, la mayoría de los contadores se quedan en cero y el tiempo y la memoria se desperdician.
¿Puede el ordenamiento por cuentas manejar números negativos?
Sí. Los contadores van del valor menor al mayor, así que resta el valor menor para obtener el índice de un contador. La aplicación hace lo mismo.
¿Es estable el ordenamiento por cuentas?
Sí, siempre que los valores se muevan en el orden de la lista al siguiente lugar libre de su tramo. El ordenamiento radix depende de ello.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Prueba el ordenamiento por cuentas