Tri par comptage

Le tri par comptage ne trie pas du tout en comparant des valeurs. Si vous savez que chaque valeur est un entier compris, disons, entre 1 et 40, vous pouvez simplement compter combien il y en a de chaque, et en déduire où chacune doit aller. Sur un petit intervalle, un tri ne peut guère être plus rapide.

Les barres d'une liste, une bande de compteurs indiquant combien de fois chaque valeur apparaît, et une rangée tampon où chaque valeur a son propre bloc
Les barres d'une liste, une bande de compteurs indiquant combien de fois chaque valeur apparaît, et une rangée tampon où chaque valeur a son propre bloc

Compter

Trouvez la plus petite et la plus grande valeur et créez un compteur pour chaque valeur entre les deux, tous à zéro. Lisez la liste une fois du début à la fin et ajoutez un au compteur de chaque valeur rencontrée. Les compteurs forment maintenant un histogramme : combien de 1, combien de 2, et ainsi de suite. Avec n valeurs et k compteurs, cela prend n étapes.

Additionner

Les valeurs égales à la plus petite viennent en premier, donc leur bloc commence à la place 1. Le bloc de la valeur suivante commence juste après, et ainsi de suite : chaque bloc commence après la somme de tous les comptes qui le précèdent. Ces totaux cumulés, appelés sommes préfixes, transforment l'histogramme en plan de la liste triée. Cela prend k étapes.

Placer

Lisez la liste une seconde fois et déplacez chaque valeur à la prochaine place libre de son bloc. Comme les valeurs sont déplacées dans leur ordre d'apparition, les valeurs égales gardent leur ordre d'origine : le tri par comptage est stable. Recopiez le tampon, et la liste est triée. L'appli montre chaque compteur redescendre à mesure que ses valeurs sont placées.

Un exemple

Prenons 4, 1, 3, 4, 2, 1, 4. Les compteurs de 1 à 4 finissent à 2, 1, 1 et 3. L'addition donne les blocs : les 1 aux places 1 et 2, le 2 à la place 3, le 3 à la place 4 et les 4 aux places 5 à 7. Placer les valeurs dans l'ordre de la liste donne 1, 1, 2, 3, 4, 4, 4 : 7 valeurs comptées, 14 déplacements, 4 compteurs et aucune comparaison.

Quand l'utiliser

Le travail total croît avec n + k. Quand k est petit par rapport à n, comme mille notes d'examen de 0 à 100, le tri par comptage est plus rapide que tout tri par comparaison, qui demande environ n log₂ n comparaisons. Quand l'intervalle est large, il est coûteux : quelques valeurs allant jusqu'à un million demandent un million de compteurs. Le tri par base règle ce problème en faisant un tri par comptage par chiffre, si bien que chaque passage n'a besoin que de dix compteurs. Harold Seward a décrit le tri par comptage, avec le tri par base, en 1954.

À vous d'essayer

Ouvrez l'appli et appuyez sur Étape. La bande entre la liste et la rangée tampon montre un compteur par valeur. Regardez les compteurs se remplir pendant la lecture de la liste, les blocs apparaître dans le tampon quand les comptes sont additionnés, puis les compteurs redescendre à mesure que les valeurs sont placées. Choisissez peu de valeurs distinctes pour voir de grands blocs, ou saisissez des nombres très éloignés pour voir combien de compteurs demande un large intervalle.

Questions fréquemment posées

Quelle est la complexité en temps du tri par comptage ?

O(n + k) pour n valeurs et k valeurs possibles, et O(n + k) de mémoire supplémentaire pour les compteurs et le tampon.

Pourquoi le tri par comptage n'est-il pas toujours le plus rapide ?

Parce que son coût dépend de l'intervalle des valeurs, pas seulement de leur nombre. Si l'intervalle est bien plus grand que la liste, la plupart des compteurs restent à zéro, et le temps et la mémoire sont gaspillés.

Le tri par comptage gère-t-il les nombres négatifs ?

Oui. Les compteurs vont de la plus petite valeur à la plus grande : soustrayez la plus petite valeur pour obtenir l'indice d'un compteur. L'appli fait de même.

Le tri par comptage est-il stable ?

Oui, tant que les valeurs sont déplacées dans l'ordre de la liste vers la prochaine place libre de leur bloc. Le tri par base en dépend.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Essayer le tri par comptage