algorithm
Orden de conteo

Información básica de orden de conteo

La ordenación de conteo es un algoritmo de clasificación de enteros para una colección de objetos que se ordenan según las claves de los objetos.

Pasos

1. Construya una matriz de trabajo C que tenga un tamaño igual al rango de la matriz de entrada A.
2. Iterar a través de A , asignando C [x] en función del número de veces que x apareció en A.
3. Transforme C en una matriz donde C [x] se refiere al número de valores ≤ x mediante la iteración a través de la matriz, asignando a cada C [x] la suma de su valor anterior y todos los valores en C que le preceden.
4. Iterar hacia atrás a través de A , colocando cada valor en una nueva matriz ordenada B en el índice registrado en C. Esto se hace para un A [x] dado asignando B [ C [ A [x]]] a A [x], y disminuyendo C [ A [x]] en caso de que hubiera valores duplicados en la matriz original sin clasificar.

Ejemplo de clasificación de conteo

Espacio auxiliar: O(n+k)
Complejidad temporal: Peor caso: O(n+k) , Mejor caso: O(n) , Caso promedio O(n+k)

Implementacion Psuedocode

Restricciones:

1. Entrada (una matriz a ordenar)
2. Número de elemento en la entrada (n)
3. Teclas en el rango de 0..k-1 (k)
4. Cuenta (una matriz de números)

Pseudocódigo

for x in input:
    count[key(x)] += 1
total = 0
for i in range(k):
    oldCount = count[i]
    count[i] = total
    total += oldCount
for x in input:
    output[count[key(x)]] = x
    count[key(x)] += 1
return output

Implementación de C #

public class CountingSort
{
    public static void SortCounting(int[] input, int min, int max)
    {
        var count = new int[max - min + 1];
        var z = 0;

        for (var i = 0; i < count.Length; i++)
            count[i] = 0;

        foreach (int i in input)
            count[i - min]++;

        for (var i = min; i <= max; i++)
        {
            while (count[i - min]-- > 0)
            {
                input[z] = i;
                ++z;
            }
        }
    }

    public static int[] Main(int[] input)
    {
        SortCounting(input, input.Min(), input.Max());
        return input;
    }
}