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.

Barras de una lista, una franja de contadores que muestra cuántas veces aparece cada valor y una fila de búfer donde cada valor tiene su propio tramo
Barras de una lista, una franja de contadores que muestra cuántas veces aparece cada valor y una fila de búfer donde cada valor tiene su propio tramo

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