Counting Sort


Antecedentes
Harold H. Seward


(Julio 24,1930 a junio 19, 2012)
Fue un científico de la computación, ingeniería, e inventor. Seward desarrolló radix sort y counting sort ambos algoritmos en 1954 en el MIT (Instituto Tecnológico deMassachusetts).
El algoritmo de ordenamiento Counting Sort (Ordenamiento por Cuentas en español) es un algoritmo de ordenamiento en el que se cuenta el número de elementos de cada clase para luego ordenarlos.El algoritmo utiliza tres array:
Inicia
Matriz de entrada: A [0...n] datos de entrada para desarrollar el algoritmo son un vector A con los números a organizar y una constante k que será el límite.Mantenimiento (Invariante)
Array temporal: C [0...k] almacena los datos temporalmente el único valor que no cambia dentro del desarrollo del algoritmo es el valor de K, puesto que es una constanteque nos dará el número de posiciones que tendrá el vector C.
Finalización
Matriz de salida: B [0...n] después que los datos de entrada han pasado por los diferentes ciclos de este algoritmo, finalizaracuando todos los valores de entrada estén en su posición correspondiente.

Ventajas
Este algoritmo está diseñado para ordenar un conjunto de números repetidos con rapidez.
El algoritmo tiene unacomplejidad de O(N+k), siendo “n” el número de elementos a ordenar y “k” el tamaño del vector auxiliar. La eficiencia del algoritmo esta entre el mejor y peor caso.
Desventajas
Observando el algoritmo,se puede notar tres listas que 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 sebasa 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...