Vous pouvez télécharger :

Ci-dessous se trouvent quelques compléments au cours.

Tri

Dans cette exemple de tri par comptage, nous disposons au départ d'un ensemble de 8 étoiles déjà triées par couleur : rouge, vert puis bleu. Nous souhaitons les trier par nombre de branches par étoiles : 3 (triangle), 4, 5, …

Il faut commencer par déterminer le nombre minimum et maximum de branche pour déterminer combiens de compteurs nous auront besoin. A titre indicatif vois la taille des tableau de compteur en fonction de leur nombre :

taille du tableau nombre max de compteur taille des compteurs mémoire nécessaire
8 bits 256 8 bits 1/4 ko
8 bits 256 16 bits 1 ko
16 bits 65 536 16 bits 128 Mo
16 bits 65 536 32 bits 256 Mo
32 bits 4 294 967 296 32 bits 16 Go
> 32 bits pas raisonable

Voici un comparatif d'exécution entre le tri rapide (le plus utilisé au monde) et le tri par comptage. Il n'y a pas photo sur l'efficacité d'une complexité en O(n) par rapport à O(n*log(n)). Cependant sont usage est limité en fonction de la diversité des valeurs des éléments à triés.