Tri Rapide (Quicksort)
Partition et pivot — cas moyen O(n log n)
Enonce
Implémenter le tri rapide. Utiliser le dernier élément comme pivot. Retourner une nouvelle liste triée.
⚠ Question : Quel est le pire cas ? Comment l'éviter ?
Signature attendue
def tri_rapide(T: list) -> list:Exemples
tri_rapide([10, 7, 8, 9, 1, 5])→[1, 5, 7, 8, 9, 10]tri_rapide([3, 3, 3])→[3, 3, 3]tri_rapide([])→[]
📖 Rappel de cours
Le tri rapide choisit un pivot, partitionne le tableau en éléments $\leq$ pivot et $>$ pivot, puis trie récursivement.
⚖️ Analogie — Le douanier :
Imaginez un douanier (le pivot) à la frontière. Il regarde chaque personne dans la file et dit : « Toi à gauche (plus petit), toi à droite (plus grand) ». Une fois tout le monde réparti, un nouveau douanier est placé dans chaque groupe pour recommencer. Au final, tout le monde est dans le bon ordre !
Complexité :
Cas moyen : $O(n\log n)$ | Pire cas : $O(n^2)$ (pivot mal choisi)
$T_{\text{moy}}(n) = 2\,T\!\left(\frac{n}{2}\right) + O(n) = O(n\log n)$
Le pire cas survient quand le pivot est toujours le min ou le max (tableau déjà trié).
← Exercices d'algorithmique en Python — tris, dichotomie, récursivité
Exercices du meme theme
- Tri par Insertion
- Tri par Sélection
- Tri Fusion (Merge Sort)
- Exponentiation Rapide
- Recherche dans une Liste Chaînée
- Pile et File
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.