Ordenamiento por Cuenta (Counting Sort)

1. Introducción

Este algoritmo es muy interesante porque no usa ninguna sentencia if, es decir, no hay ninguna condición, a excepción de los bucles. El algoritmo funciona mejor con una lista larga, de un solo elemento simple: no hay structs, y de números repetitivos. Es mejor que los números no se separen mucho entre sí; por ejemplo, el valor máximo sea de 10, y el mínimo de 1, aunque tengamos 10.000 entradas (o elementos). La desventaja de este algoritmo es la necesidad de almacenar muchos datos en memoria.

2. Pseudocódigo

El pseudocódigo es el siguiente:

Ordenamiento_por_Cuenta( A, B, k )
 1  for i <-- 1 to k
 2    do C[i] <-- 0
 3  for j <-- 1 to tamaño[A]
 4    do C[ A[j] ] <-- C[ A[j] ] + 1
 5  // C[i] contiene ahora el número de elementos igual a 'i'
 6  for i <-- 2 to k
 7    do C[i] <-- C[i] + C[i-1]
 8  // C[i] contiene ahora el número de elementos menor que o igual a 'i'
 9  for j <-- tamaño[A] downto 1
10    do B[ C[ A[j] ] ] <-- A[j]
11       C[ A[j] ] <-- C[ A[j] ] - 1

3. Acerca del pseudocódigo

Indentación es muy importante, pasos 10 y 11 son parte del bucle for (paso 9).

4. Ejemplo

Veamos un ejemplo:

0.  C es inicializada asignando todos elementos a cero (pasos 1-2).
1.  Empezamos con una lista desordenada, A, de números enteros que se repiten varias veces.
2.  C es asignada valores que representan la cuenta de cada elemento de A (pasos 3-4). El índice de C representa el elemento de A: 0 unos, 0 doses, 3 treses, y 2 cuatros.

3.  C es asignada a cada elemento la suma de su valor y el del elemento anterior (pasos 6-7); por ejemplo, C[3] = C[3] + C[2], etc.. Esto sirve para saber en qué índice acaba el bloque de números repetidos: C[3] = 3 => bloque de treses acaba en índice 3, C[4] = 5 => bloque de cuatros acaba en índice 5.
4.  B es la lista ordenada de A. Es asignada el primer número ordenada: 3 (pasos 9-10), con j = 5.

5.  El elemento de C usado para ordenar B es restado 1 (paso 11).
6.  B es asignada otro valor en orden (pasos 9-10), con j = 4.

7.  C es nuevamente restada 1 al elemento recién usado (paso 11).
8.  B es añadida otro número en su propio sitio, con j = 3.

9.  Se repite paso 11.
10. Pasos 9-10, con j = 2.

11. Paso 11.
12. Pasos 9-10, con j = 1.

13. Ningún elemento de C tendrá un valor negativo.

14. j = 0, por lo tanto se sale del bucle for. B da lugar al resultado, que es el ordenamiento de A:

5. Conclusión

Como se puede observar, no se usa ninguna condición, y es bastante rápido. Esto es posible ya que el tipo de elementos de la lista es limitado: números enteros positivos. Este algoritmo está diseñado para ordenar un conjunto de números repetidos con rapidez.

Observando el algoritmo, se puede notar cierto parecido con histogramas: lista del número de frecuencias que cierto valor o elemento produce. C es la lista de histogramas de los valores de A. Luego C es modificado para incluir los índices de cada frecuencia, y por último usando C y A se puede deducir la ordenación de los elementos, que serán almacenados en B.

Tres listas pueden ocasionar un problema al ser implementado, si se tiene una limitación de memoria. Dos de las listas (A y B) tienen la misma longitud, mientras que la tercera se basa en k, el elemento mayor de A. Añadiendo un elemento a la lista de entrada, significa un incremento doble de memoria. Sin embargo, añadiendo un elemento de mayor alcance que los restantes en la lista puede significar un incremento de memoria de diez o más veces. Por ejemplo, si A tiene elementos entre 1 y 10, C debe tener una longitud de diez, pero si se añade un elemento más a A, de valor 100, entonces C ha de extender la longitud a cien: diez veces más que anteriormente.

6. Bibliografía

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest. Introduction to Algorithms. New York, McGraw-Hill Book Company, 1990.