Tri Rapide (Quicksort)
Algorithmique classique
Enonce
Trier une liste par l'algorithme du tri rapide (version récursive). Retourner une nouvelle liste triée.
Signature attendue
def tri_rapide(L: list) -> list:Exemples
tri_rapide([5, 3, 8, 1, 2])→[1, 2, 3, 5, 8]tri_rapide([4, 4, 1, 3])→[1, 3, 4, 4]
📖 Rappel de cours
On choisit un pivot, on répartit les éléments de part et d'autre, puis on trie récursivement chaque côté.
⚠ Le piège : Le cas défavorable est O(n²) — typiquement une liste déjà triée avec le premier élément comme pivot. C'est la question classique : le tri rapide n'est rapide qu'en moyenne.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Conversion Décimal → Binaire
- Tri par Sélection
- Tri Fusion (Merge Sort)
- Tri par Comptage (Counting Sort)
- Vérifier si Liste Triée Décroissante
- Exponentiation Rapide
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.