Exercices de programmation pour classes préparatoires
Écrire une fonction tri_comptage(lst) qui trie une liste d'entiers positifs ou nuls en utilisant l'algorithme du tri par comptage (counting sort) et renvoie une nouvelle liste triée.
Le principe du tri par comptage est le suivant :
1. Trouver la valeur maximale max_val de la liste.
2. Créer un tableau de compteurs de taille max_val + 1, initialisé a zéro.
3. Parcourir la liste et incrémenter le compteur correspondant a chaque valeur.
4. Reconstruire la liste triée a partir des compteurs.
Cet algorithme ne compare pas les éléments entre eux. Sa complexité est O(n + k) ou k est la valeur maximale. Il ne fonctionne que pour des entiers positifs ou nuls.
| Appel | Résultat attendu |
|---|---|
| tri_comptage([4, 2, 2, 8, 3, 3, 1]) | [1, 2, 2, 3, 3, 4, 8] |
| tri_comptage([0, 0, 1]) | [0, 0, 1] |
Connectez-vous pour soumettre du code.