Lorsque votre tâche de tri implique de grands tableaux de petits entiers – comme les grades, les âges ou les codes catégoriques – les algorithmes classiques basés sur la comparaison comme QuickSort ou MergeSort peuvent se sentir comme trop kill. Ces algorithmes fonctionnent dans le temps O(n log n), mais si la plage de valeurs possibles est limitée, vous pouvez trier en temps linéaire O(n + k) avec .Counting Tri. Cet algorithme de tri non-comparaison permet de calculer les occurrences plutôt que de comparer des éléments, fournissant un type stable qui est à la fois simple et rapide pour les entrées correctes.

Comment fonctionne le tri de comptage

Compter Tri exploite la connaissance que les valeurs d'entrée sont des entiers tirés d'une petite plage . Au lieu de comparer par paires, il construit un histogramme de fréquence des valeurs et utilise ensuite cet histogramme pour placer chaque élément dans sa position triée correcte.

L'approche de base : la reconstruction directe

La version la plus simple de Compter Tri fonctionne en deux passes :

  1. Count frequences – Itérer à travers le tableau d'entrée et incrémenter un compteur pour chaque valeur que vous voyez.
  2. – Passez par le tableau de comptoir de la plus petite à la plus grande et, pour chaque valeur, écrivez-le dans le tableau d'entrée autant de fois que son nombre.

Cela donne une sortie triée mais ne [ conserve l'ordre relatif des duplicata (il n'est pas stable). La stabilité est importante lorsque vous triez sur une clé tout en conservant l'ordre original des enregistrements avec des clés égales. La variante stable, décrite ci-dessous, est celle qui est la plus couramment utilisée en pratique.

La variante stable : les comptes cumulatifs

Pour rendre le tri de comptage stable, nous ajoutons un troisième passe :

  1. Comptez les fréquences comme avant.
  2. Transformer le tableau de fréquence en tableau cumulatif de comptage. Après cette étape, détient le nombre d'éléments ≤ i.
  3. Iterate the entry array in backback (de la dernière à la première partie). Pour chaque élément, utilisez son cumul pour trouver sa position dans le tableau de sortie, le placer et diminuer le nombre.

Parce que nous traversons en sens inverse, l'ordre relatif des éléments égaux est préservé. Le tableau de sortie est séparé de l'entrée, donc cette version utilise l'espace supplémentaire O(n) pour la sortie, alors que la version de base peut trier en place en écraser l'entrée.

Mise en oeuvre du tri de comptage en C#

Voici deux implémentations C# : la version en place de base (pour les scénarios où la stabilité est inutile) et la version stable qui utilise un tableau auxiliaire.

Tri de comptage de base (non-stable)

Cette variante trie le tableau d'entrée directement sans tampon de sortie supplémentaire. Il est efficace en mémoire mais pas stable.

public static void CountingSortBasic(int[] array, int maxValue)
{
 int[] counts = new int[maxValue + 1];

 // Count each element's frequency
 for (int i = 0; i < array.Length; i++)
 {
 counts[array[i]]++;
 }

 // Overwrite the original array in sorted order
 int index = 0;
 for (int value = 0; value <= maxValue; value++)
 {
 while (counts[value]-- > 0)
 {
 array[index++] = value;
 }
 }
}

Tri de comptage stable

La version stable nécessite un tableau de sortie de la même taille que l'entrée. Il utilise également des comptages cumulatifs pour positionner correctement les éléments.

public static int[] CountingSortStable(int[] array, int maxValue)
{
 int[] counts = new int[maxValue + 1];
 int[] output = new int[array.Length];

 // Step 1: Count occurrences
 foreach (int num in array)
 {
 counts[num]++;
 }

 // Step 2: Transform counts to cumulative counts
 for (int i = 1; i <= maxValue; i++)
 {
 counts[i] += counts[i - 1];
 }

 // Step 3: Build the output array (iterate input in reverse for stability)
 for (int i = array.Length - 1; i >= 0; i--)
 {
 int value = array[i];
 output[counts[value] - 1] = value;
 counts[value]--;
 }

 return output;
}

Dans les deux implémentations, est le plus grand entier qui apparaît dans le tableau. Si le vrai maximum est inconnu, vous pouvez le calculer avec un scan préparatoire (O(n)). La version stable retourne un nouveau tableau trié, laissant l'original inchangé.

Analyse de complexité

Que n soit le nombre d'éléments et k = max – min + 1 (la plage des valeurs possibles).

  • Time: Compter Tri fonctionne dans O(n + k) time. La phase de comptage est O(n), le préfixe cumulatif est O(k), et la reconstruction est O(n). Lorsque k est O(n), l'algorithme est linéaire.
  • Espace: La version de base utilise O(k) espace supplémentaire pour le tableau de comptage. La version stable utilise O(n + k) car elle alloue également le tableau de sortie. Cela rend le comptage Tri inapproprié lorsque la plage est grande par rapport au nombre d'éléments.
  • Comparaison avec d'autres types : Les types de comparaison comme QuickSort et MergeSort nécessitent au moins des comparaisons O(n log n). Pour les petits k (p. ex. k < 10 000 et n > 100 000), le tri de comptage peut être plus rapide.

Variations et extensions

Manipulation des entiers négatifs

Le comptage Tri fonctionne nativement avec des entiers non négatifs. Pour gérer les valeurs négatives, décalez toute la plage de sorte que le minimum devient zéro. Par exemple, si les nombres vont de -1000 à 1000, compensez chaque élément par +1000. Le tableau de comptage a alors une taille .

public static int[] CountingSortWithNegative(int[] array)
{
 if (array.Length == 0) return array;

 int min = array.Min();
 int max = array.Max();
 int range = max - min + 1;

 int[] counts = new int[range];
 int[] output = new int[array.Length];

 foreach (int num in array)
 counts[num - min]++;

 for (int i = 1; i < range; i++)
 counts[i] += counts[i - 1];

 for (int i = array.Length - 1; i >= 0; i--)
 {
 int value = array[i];
 output[counts[value - min] - 1] = value;
 counts[value - min]--;
 }

 return output;
}

Cartographie des clés non-intégrales

Le comptage Tri nécessite des touches entières. Si vos données sont composées de caractères (octets), ou de dénombrements qui peuvent être placés sur des entiers, vous pouvez toujours les appliquer. Pour les objets plus grands, vous pouvez extraire une touche entière et trier les objets en conséquence – c'est exactement comment Radix Tri utilise souvent le comptage Tri comme sous-routine intérieure.

Tri radix Combo

Radix Tri traite les chiffres (ou bits) individuellement, et le Tri de comptage est le choix naturel pour chaque passe lorsque la base (p. ex. 10 ou 256) est petite. Cela permet le tri linéaire des entiers arbitraires, et non pas seulement des petits.

Considérations pratiques en C#

Empreinte de mémoire et grand k

Le plus grand piège est d'attribuer un tableau de nombre plus grand que la mémoire disponible. Par exemple, trier 1 000 éléments avec une plage de 1 000 000 déchets d'espace. Vérifiez toujours que k n'est pas des ordres de grandeur plus grands que n – autrement utiliser un tri de comparaison ou une approche hybride.

Parallélisme et Span< T>

Pour les tableaux extrêmement grands, vous pouvez paralléliser la phase de comptage en partitionnant l'entrée entre les threads. Chaque thread compte son segment dans un tableau privé, puis les résultats partiels sont agrégés. L'utilisation de et pour le tableau de comptage peut réduire les allocations de tas lorsque la plage est petite.

Cas de bord

  • Tableau d'empty – retour immédiatement.
  • Élément unique – le tri est trié de façon triée.
  • Toutes les valeurs identiques – le tableau de comptage a une entrée non nulle; la reconstruction est exécutée en O(n).
  • Plus grande plage de données mais peu de données[ – Le tri de comptage devient inefficace parce que la plupart des entrées de comptage sont nulles.

Recommandations de performance

Utilisez le système de comptage Triez lorsque vous connaissez les entiers d'entrées qui se trouvent dans une petite plage (p. ex., grades 0–100, âges 0–120, codes d'erreur 0–255). Pour les gammes plus grandes, considérez Radix Tri ou un hybride qui revient à QuickSort pour les partitions à haute portée.

Quand utiliser le tri de comptage (et quand ne pas faire)

SituationRecommendation
Small integer range (k ~ n)Excellent choice – linear time, simple code.
Large integer range (k >> n)Avoid – memory waste and O(k) overhead.
Need stabilityUse the stable variant (cumulative counts).
Strings or objectsConsider Radix Sort or a comparison sort.
Extremely large datasetsCounting Sort can be parallelized; but watch memory.

Analyse comparative et performance

Dans un référentiel typique avec n = 1.000.000 et k = 1.000, le tri de comptage complète dans environ 20-30% du temps pris par (qui utilise l'introsort). L'écart s'élargit comme k diminue. Ci-dessous est une comparaison approximative (temps d'exécution sur un CPU moderne avec .NET 8):

n = 1,000,000 | k = 1,000
Array.Sort (QuickSort variant) : 68 ms
CountingSortBasic : 12 ms
CountingSortStable : 18 ms

Lorsque la portée atteint 10 000, le nombre de tris gagne encore, mais la marge se rétrécit. Pour k = 100 000, le dépassement de mémoire (de 400 KB pour le nombre de tableau) commence à nuire au cache du CPU, et les performances peuvent se dégrader.

Conclusion

Pour les développeurs C# qui traitent de grands tableaux de petits entiers, c'est un outil précieux qui peut réduire considérablement le temps de tri. Gardez un œil sur la gamme de vos données : si elle est petite et connue, le tri de comptage dépassera toute alternative fondée sur la comparaison. Pour un tri plus général, utilisez le intégré, mais soyez toujours prêt à tomber dans le tri de comptage lorsque les nombres s'alignent – littéralement et figurativement.

Pour plus de détails, consultez l'article Wikipedia sur le tri de comptage, le Microsoft docs on Array.Sort, et un guide pratique de GeeksforGeeks.