Ordenamiento por cuentas
# Ordenamiento por cuentas

El ordenamiento por cuentas (counting sort en inglés) es un algoritmo de ordenamiento en el que se cuenta el número de elementos de cada clase para luego ordenarlos. Solo puede ser utilizado por tanto para ordenar elementos que sean contables (como los números enteros en un determinado intervalo, pero no los números reales, por ejemplo).

El primer paso consiste en averiguar cuál es el intervalo dentro del que están los datos a ordenar (valores mínimo y máximo). Después se crea un vector de números enteros con tantos elementos como valores haya en el intervalo [mínimo, máximo], y a cada elemento se le da el valor 0 (0 apariciones). Tras esto se recorren todos los elementos a ordenar y se cuenta el número de apariciones de cada elemento (usando el vector que hemos creado). Por último, basta con recorrer este vector para tener todos los elementos ordenados.

## Ejemplo

Considérese la siguiente lista de números:

Para ordenarla con este algoritmo, seguimos estos pasos:

* Buscar el mínimo y el máximo
* Crear el vector auxiliar
* Recorrer la lista de números y contar elementos, debe fijarse como el valor en la lista de entrada se usa como índice en el vector auxiliar
* Recorriendo el vector auxiliar obtenemos la lista de números ordenada

## Características

Se trata de un algoritmo estable cuya complejidad computacional es O(n+k), siendo n el número de elementos a ordenar y k el tamaño del vector auxiliar (máximo - mínimo).

La eficiencia del algoritmo es independiente de lo casi ordenado que estuviera anteriormente. Es decir no existe un mejor y peor caso, todos los casos se tratan iguales.

El algoritmo counting, no se ordena in situ, sino que requiere de una memoria adicional.

### Limitaciones

El algoritmo posee una serie de limitaciones que obliga a que solo pueda ser utilizado en determinadas circunstancias.

Solo ordena números enteros, no vale para ordenar cadenas y es desaconsejable para ordenar números decimales. Teóricamente se puede, pero debería recrear en la matriz auxiliar tantas posiciones como decimales quepan entre 2 números consecutivos, si se restringe a 1 o 2 decimales podría ser asequible un número mayor de decimales puede llegar a suponer una memoria auxiliar impracticable.

Otra limitación (por ineficiencia) incluso con números enteros es cuando el rango entre el mayor y el menor es muy grande. Imaginemos una lista de 1000 elementos, donde el menor es el 0 y el mayor 123456789. Ordenar esta lista supondría crear una matriz auxiliar de 123456790 elementos. Una cantidad muy elevada de memoria para ordenar solo 1000 elementos. También supondría un desperdicio de tiempo pues la matriz auxiliar para trasvasar a la lista ordenada debe recorrerse entera, aunque solo se reasignarán 1000 valores de los 123456790 elementos.

Con lenguajes de programación que no permitan definir vectores cuyo primer índice sea un valor distinto de 0 o 1 es necesario realizar una traducción de los valores. Por ejemplo, si el intervalo es (4,10) y el vector auxiliar comprende el rango (1-7), para cada elemento se deberá incrementar el contador de la posición en 3.

Un modo de hacer este algoritmo más práctico, es guardar varios elementos en un índice de la matriz, pero en este caso la matriz ya no es de valores enteros sino que contiene algún tipo de estructura de datos. Así es posible por ejemplo ordenar números con decimales. Por ejemplo si en la matriz auxiliar en el índice 5, metemos todas las apariciones de la lista cuyo valor está en el rango 5.0 - 5.99. Luego con cada elemento en cada índice se realiza un nuevo ordenamiento. cuando se usan este tipo de técnicas, el algoritmo ya se considera otro, denominado: bucket sort.

## Pseudocódigo

Se han añadido los comentarios pertinentes para aclarar las partes que fueren más dudosas.

