Tri par Comptage (Counting Sort)
Algorithmique classique
Enonce
Trier une liste d'entiers positifs par l'algorithme du tri par comptage. Retourner la liste triée.
Signature attendue
def tri_comptage(L: list) -> list:Exemples
tri_comptage([4, 2, 2, 8, 3, 3, 1])→[1, 2, 2, 3, 3, 4, 8]tri_comptage([5, 5, 5])→[5, 5, 5]
📖 Rappel de cours
On compte les occurrences de chaque valeur dans un tableau indexé par la valeur elle-même, puis on reconstruit la liste triée en parcourant ce tableau.
⚠ Le piège : Ce tri échappe à la borne n log n parce qu'il ne compare jamais deux éléments. En contrepartie il exige des entiers dans un intervalle connu et borné.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Tri par Sélection
- Tri Fusion (Merge Sort)
- Tri Rapide (Quicksort)
- Vérifier si Liste Triée Décroissante
- Exponentiation Rapide
- Suite de Syracuse
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.