Voici un algorithme de tri à utiliser pour un tableau d'entiers ou de structures dont la clé est un entier. Particulièrement utile lorsque la plage d'entiers est de l'ordre de la taille de l'entrée.

L'idée principale est de déterminer la fréquence d'apparition des entiers et de l'utiliser pour déterminer l'ordre de tri.

Un exemple : disons que nous obtenons le tableau {1,3,1,2}.

Déterminez d'abord la plage des nombres entiers, max et min, 1 et 3 pour cette entrée.

Créez ensuite un tableau, appelez-le le tableau des comptes, c'est-à-dire la taille de la plage d'entiers 1, donc 3 (3-1 1) dans ce cas.
Parcourez le tableau d'entrée, en incrémentant l'entrée appropriée en nombre. Le nombre d'une valeur d'entrée donnée sera placé à counts[value - min]. Pour l'entrée donnée, counts[0] contiendra le décompte pour la valeur 1.

Il en résulte le tableau de nombres : {2,1,1}

Déterminez maintenant les comptes cumulés, qui sont essentiellement des comptes[i] = des comptes[i-1] des comptes[i].

Il en résulte le tableau des comptes cumulés : {2,3,4}

Créez un tableau de sortie pour l'entrée triée.

Maintenant, parcourez l'entrée dans l'ordre inverse.

À chaque étape, récupérez le nombre cumulé de la valeur dans le tableau d'entrée. La valeur sera placée à l'index du tableau de sortie correspondant au nombre récupéré - 1. Décrémentez ensuite la valeur du nombre cumulé.

Dans la première étape, la valeur 2 est récupérée et un décompte cumulé de 3. La valeur doit être placée à l'index 2 (3-1) dans la sortie.

Dans l'itération suivante, la valeur 1 et le nombre cumulé 2 ; donc ce '1' est placé à l'index 1 (2-1) de la sortie.

En continuant, la valeur 3 et le nombre cumulé 4 ; en le plaçant à l'index 3 de la sortie.

Enfin, la valeur 1 pour la deuxième fois et un décompte cumulé de 1 (puisque le décompte a été décrémenté la première fois qu'il a été vu) ; donc ce '1' est placé à l'index 0 de la sortie.

, découvrez comment l'itération inverse préserve l'ordre des éléments égaux, rendant le tri "stable"

Le tableau trié résultant est {1,1,2,3}

func CountingSort(in []int) []int {
    // find the min/max values
    min := slices.Min(in)
    max := slices.Max(in)
    // create the count array
    counts := make([]int, max-min 1)
    for _, v := range in {
        counts[v-min]  
    }
    // determine cumulative counts
    for i := 1; i 



Peut-il être rendu plus efficace ? Laissez vos commentaires et suggestions ci-dessous.

Merci!

Le code de cet article et de tous les articles de cette série peut être trouvé ici