algorithm
Comptage tri

Compter les informations de base du tri

Le tri par comptage est un algorithme de tri d'entiers pour une collection d'objets qui trie en fonction des clés des objets.

Pas

1. Construisez un tableau de travail C dont la taille est égale à la plage du tableau d'entrée A.
2. Itérer via A , en assignant C [x] en fonction du nombre de fois que x est apparu dans A.
3. Transformer C dans un tableau où C [x] désigne le nombre de valeurs ≤ x par itération à travers le réseau, en attribuant à chaque C [x] , la somme de sa valeur précédente et toutes les valeurs de C qui lui sont soumises.
4. Itérer en arrière à travers A , en plaçant chaque valeur dans un nouveau tableau trié B à l'index enregistré en C. Ceci est fait pour un A [x] donné en assignant B [ C [ A [x]]] à A [x] et en décrémentant C [ A [x]] au cas où il y aurait des valeurs en double dans le tableau non trié original.

Exemple de tri par comptage

Espace auxiliaire: O(n+k)
Complexité temporelle: pire cas: O(n+k) , meilleur cas: O(n) , cas moyen O(n+k)

Implémentation de Psuedocode

Contraintes:

1. Entrée (un tableau à trier)
2. Nombre d'éléments dans l'entrée (n)
3. Touches dans la gamme de 0..k-1 (k)
4. Count (un tableau de nombre)

Pseudocode:

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

Implémentation 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;
    }
}