Vous pouvez télécharger :
- le support de cours
- les gif animés qui accompagnent le support de cours
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.
Outils de la page
