Introduction au tri de comptage

Compter Tri est un algorithme de tri non-comparaison qui excelle lors du tri d'entiers sur une petite gamme connue. Contrairement aux types de comparaison tels que Quicksort ou Mergesort, qui reposent sur des comparaisons d'éléments appariés, Compter Tri détermine l'ordre trié en comptant la fréquence de chaque valeur distincte. Cette approche donne une complexité temporelle linéaire dans des conditions favorables, ce qui en fait un choix pour de nombreuses applications critiques en termes de performances où le domaine d'entrée est limité.

L'algorithme a été décrit par Harold H. Seward en 1954 et reste une technique fondamentale en informatique. Sa simplicité et son efficacité le rendent idéal pour les tâches comme le tri des âges étudiants, les grades, ou toute donnée entière à une diffusion modeste. En tirant parti du stockage auxiliaire proportionnel à la plage de valeurs, le Compte Tri évite la limite inférieure de tri de comparaison O(n log n), atteignant O(n + k) le temps où k est la plage de valeurs d'entrée.

Comment fonctionne le tri de comptage

Le mécanisme de base de la méthode de comptage de tri est simple : il compte combien de fois chaque valeur apparaît dans le tableau d'entrée, puis utilise ce nombre pour calculer la position finale de chaque élément. Le processus se compose de trois phases distinctes :

  1. Counting:[ Créez un tableau de nombre de taille k (la plage de valeurs d'entrée), initialisé à zéro. Itérer à travers le tableau d'entrée et incrémenter le nombre de chaque valeur.
  2. Computing prefixes:[ Transformer le tableau de nombre en tableau de somme de préfixe, où chaque élément à l'index i détient le nombre cumulatif d'éléments inférieur ou égal à i. Cette étape détermine les positions de départ pour chaque valeur distincte dans la sortie triée.
  3. Éléments de positionnement:[ Traverser le tableau d'entrée de droite à gauche (pour la stabilité), utiliser le tableau de comptage pour trouver l'index correct dans le tableau de sortie, placer l'élément là, et diminuer le nombre. La sortie finale est une copie triée de l'entrée.

L'algorithme renvoie un nouveau tableau trié, laissant l'original inchangé. Une variante appelée in-place Compter Tri[ existe mais est rarement utilisée parce qu'elle compromet la stabilité ou l'efficacité de l'espace.

Exemple d'étape par étape

Envisager de trier le tableau [4, 2, 2, 8, 3, 3, 1] où les valeurs varient de 0 à 8.

  1. Count:[ Taille du tableau de comptage 9 (0–8) → [0,1,2,2,0,1,0,0,0,1]. (L'indice 1 apparaît une fois, index 2 deux fois, index 3 deux fois, index 4 une fois, index 8 une fois.)
  2. Préfixer les sommes:[ Transformer en cumulatif → [0,1,3,5,6,6,6,7]. Chaque valeur nous indique maintenant la position de départ pour ce nombre dans la sortie triée.
  3. Sortie:[ Variante du tableau original de la fin: premier élément lu est 1 → position = count[1] - 1 = 0 → sortie[0]=1, nombre de diminution[1] à 0. Ensuite, 3 → position = count[3] - 1 = 4 → sortie[4]=3, count[3]=4. Continuer jusqu'à ce que tous les éléments soient placés. Sortie finale: [1,2,2,3,4,8].

Cet exemple montre comment le comptage Tri évite les comparaisons en se basant uniquement sur les opérations arithmétiques.

Complexité informatique

Complexité temporelle

  • Best, moyen et pire cas:[ O(n + k), où n est le nombre d'éléments et k est la plage des valeurs d'entrée. Lorsque k est petit par rapport à n, l'algorithme tourne en temps linéaire.
  • Comparaison aux types de comparaison :[ Quicksort et Mergesort ont une complexité moyenne O(n log n). Pour n = 106 et k = 1000, le tri de comptage (= 1 001 000 opérations) est environ 13 fois plus rapide qu'un tri typique O(n log n).

Complexité spatiale

  • Prioral: O(k) pour le tableau de comptage, plus O(n) pour le tableau de sortie. Ce survol de mémoire peut être prohibitif si k est grand (par exemple, trier des entiers 32 bits où k = 232).
  • Variante stable: Nécessite un tableau de sortie auxiliaire de la taille n; les variantes en place sacrifient la stabilité ou utilisent une manipulation complexe de l'index.

Quand utiliser le tri de comptage

Le tri de comptage est plus efficace dans les conditions suivantes :

  • L'entrée se compose d'entiers (ou de données qui peuvent être cartographiées sur une petite plage entière, comme des caractères ou des catégories discrètes).
  • La plage k n'est pas significativement plus grande que n. Une règle courante du pouce est k ≤ O(n).
  • La mémoire n'est pas fortement limitée, car le tableau de comptage et le tampon de sortie nécessitent un espace supplémentaire.
  • La stabilité est requise (par exemple, trier par plusieurs clés). L'implémentation standard est stable lorsque les éléments sont placés de droite à gauche.

Les cas d'utilisation excellents comprennent le tri des grades (0–100), des âges (0–120), des catégories de produits (jusqu'à quelques centaines d'UGS), ou comme sous-routine dans Radix Tri.

Limites et considérations

Malgré sa vitesse, le Compter Tri présente des inconvénients qui limitent son applicabilité :

  • Intégré seulement:[ Il ne peut pas trier directement des nombres ou des chaînes de points flottants à moins qu'ils ne soient convertis en un ensemble entier contigu.
  • Grande plage:[ Si k nains n – par exemple trier 100 nombres avec des valeurs entre 1 et 107 – le tableau de comptage consomme une mémoire énorme tout en triant seulement quelques éléments.
  • Non-adaptatif:[ Compter Tri nécessite toujours de scanner l'ensemble de l'entrée et de construire le tableau de comptage, même si les données sont déjà triées ou presque triées.
  • Valeurs négatives : Classe de comptage standard suppose des nombres entiers non négatifs. Pour gérer les valeurs négatives, vous pouvez déplacer les valeurs en soustrayant le minimum (en faisant la plage 0 à max – min).

Ces limites signifient le comptage Tri est un outil spécialisé, et non un remplacement universel des algorithmes à usage général.

Comparaison avec les algorithmes de tri associés

Tri de comptage vs Radix Tri

Radix Tri étend l'idée en triant les chiffres les moins significatifs aux plus significatifs, en utilisant un tri stable (souvent le tri de comptage) à chaque chiffre. Alors que le tri de comptage fonctionne sur une passe sur toute la gamme k, Radix Tri effectue plusieurs passages sur une gamme de chiffres plus petite (par exemple, base 256), réduisant l'utilisation de la mémoire pour les grands k. Par exemple, le tri des entiers 32 bits avec le tri de comptage nécessiterait un tableau de comptage de 232 entrées, tandis que Radix Tri avec des chiffres 8 bits nécessite 256 entrées par passe et seulement quatre passes.

Tri de comptage vs. Tri de seau

Le seau Tri distribue les éléments dans un certain nombre de seaux et trie chaque seaux individuellement (souvent avec le tri d'insertion). Le seau Tri de comptage peut être vu comme un cas spécial du seau Tri où chaque seau correspond à une seule valeur distincte.

Mise en œuvre d'un tri de comptage stable

La stabilité est importante lors du tri par une clé tout en préservant l'ordre relatif des éléments égaux d'une autre clé. L'algorithme de comptage standard est intrinsèquement stable lorsque la boucle de placement de sortie traverse l'entrée de droite à gauche. Voici un aperçu textuel de la variante stable:

  1. Calculer le tableau de nombre comme décrit.
  2. Convertir en montants préfixés (positions de chaque valeur dans la sortie triée).
  3. Iterer le tableau d'entrée en ordre inverse. Pour chaque élément, placer à la position indiquée par son nombre, puis diminuer ce nombre.

Comme nous traitons des éléments à partir de la fin, la dernière occurrence d'une valeur donnée entre dans l'index le plus élevé possible, en préservant l'ordre relatif. Cette version stable est essentielle pour que Radix Tri fonctionne correctement sur chaque chiffre.

Applications pratiques

  • Systèmes de classement éducatif :[ Tri de centaines de notes d'examen (intervalle 0–100) en temps O(n).
  • Bioinformatique:[ Tri des nombres entiers de lecture ou des fréquences k‐mer de l'ADN lorsque la taille de l'alphabet est petite (A, C, G, T).
  • Maintenance de l'index de la base de données: Tri d'identificateurs entiers uniques dans une plage suffisamment petite pour s'adapter en mémoire.
  • Traitement d'image :[ Tri des bacs d'histogramme ou des intensités de couleur (0–255) lors de la construction de tables de recherche.
  • Trier par la clé secondaire:[ Utilisé à l'intérieur de Radix Tri, qui est le cheval de travail pour un tri efficace dans de nombreuses bibliothèques et langues (par exemple, le .NET runtime utilise un mélange adaptatif d'algorithmes, y compris le comptage Tri pour de petites gammes).

Pour plus d'informations sur la théorie et les variantes, consultez des références faisant autorité telles que Wikipedia: Componing Tri et GeeksforGeeks: Componing Tri. Des comparaisons pratiques avec d'autres algorithmes peuvent être trouvées dans Brilliant „s Componing Tri article.

Tri de comptage optimal pour les grandes gammes

Lorsque k est grand mais n est aussi grand, le tri de comptage pur devient une source de mémoire.

  • Smallness comprimé:[ Utilisez une carte de hachage au lieu d'un tableau contigu lorsque la plage de valeurs utilisées est grande mais le nombre de valeurs distinctes est faible. Ceci trade l'indexation à temps constant pour le hachage en hauteur mais réduit la consommation de mémoire.
  • Approches hybrides :[ Combiner le comptage Tri avec d'autres algorithmes. Par exemple, si la plage dépasse 106, utilisez Radix Tri avec une base qui maintient les plages de chiffres petites.
  • Variantes en place:[ Certaines optimisations réduisent l'espace supplémentaire à O(k) sans tableau de sortie, mais elles sacrifient généralement la stabilité ou exigent des cycles pour localiser les positions.

Conclusion

Compter Tri se distingue par un algorithme remarquablement efficace pour le tri des entiers lorsque la plage de valeurs est petite par rapport au nombre d'éléments. Sa complexité de temps O(n + k) et sa performance linéaire le rendent indispensable dans des scénarios tels que le tri de grade, les sous-routines Radix Tri et les applications avec des touches entières limitées. Cependant, l'algorithme dépend de l'entrée d'entier et de sa mémoire pour les grandes gammes nous rappellent qu'aucun type unique n'est optimal pour toutes les situations.