Counting sort

COUNTING SORT

Ordenamiento por cuentas (Counting sort) es un algoritmo de ordenamiento en el que se cuenta el número de elementos de cada clase para luegoordenarlos.
Sólo puede ser utilizado por tanto para ordenar elementos que sean contables como los números enteros en un determinado intervalo.
El primer paso consisteen 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 tantoselementos 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 aordenar 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 loselementos ordenados.
Vector sin ordenar: 2 5 3 2 7 5 3 2
Buscamos el minimo y maximo
Mínimo = 2 Máximo = 7
Crear el vector auxiliar
vaux = nuevo vector[2..7] deenteros
Recorremos la lista de números y contamos los elementos.
Al final, vaux = [3, 2, 0, 2, 0, 1]
vaux[2] = 3 porque el valor 2 aparece 3 veces vaux[6] = 0porque el valor 6 no aparece en la secuencia a ordenar
Recorriendo el vector auxiliar obtenemos la lista de números ordenada
Vector ordenado = 2 2 2 3 3 5 5 7COMPLEJIDAD 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)
Si este último intervalo esmuy amplio, el algoritmo es ineficiente, ya que el vector auxiliar tiene un tamaño excesivamente grande, lo que supondría un gran coste en memoria y también en tiempo.