Ouverture hors programme de terminale NSI. Le tri rapide n’est pas exigible au baccalauréat ; il illustre le paradigme diviser pour régner et se compare au tri fusion, qui est, lui, au programme.
Prérequis : diviser pour régner , récursivité
À l’issue de ce chapitre, vous saurez :
- expliquer le principe du tri rapide (choix du pivot, partition, appels récursifs) ;
- analyser sa complexité dans le meilleur cas (O(n log n)) et dans le pire cas (O(n²)) ;
- comparer le tri rapide au tri fusion en termes de complexité, stabilité et performances pratiques ;
- implémenter le tri rapide en Python.
Principe du tri rapide
Le tri rapide fonctionne selon le principe suivant :
- On choisit un élément du tableau appelé pivot.
- On réorganise le tableau de sorte que tous les éléments plus petits que le pivot soient à sa gauche et tous les éléments plus grands soient à sa droite.
- On applique récursivement le tri rapide sur les deux sous-tableaux (gauche et droite).
Exemple : soit le tableau [7, 2, 1, 6, 8, 5, 3, 4]. Si on choisit 4 comme pivot :
- la liste des nombres inférieurs à 4 est
[2, 1, 3]; - celle des nombres égaux au pivot est
[4]; - et celle des nombres supérieurs à 4 est
[7, 6, 8, 5].
En concaténant les trois listes, on obtient [2, 1, 3, 4, 7, 6, 8, 5] puis on trie récursivement [2, 1, 3] et [7, 6, 8, 5].
Diviser pour régner
Exercice : le paradigme diviser pour régner
Rappelez en quelques lignes le principe du paradigme diviser pour régner.
En quoi le tri rapide utilise-t-il ce paradigme ?
Quelle est la principale différence entre la façon dont le tri fusion et le tri rapide divisent le problème ?
Solution
Le paradigme diviser pour régner consiste à diviser le problème en sous-problèmes plus petits, régner en résolvant récursivement ces sous-problèmes, puis combiner les solutions pour obtenir la solution du problème initial.
Le tri rapide l’utilise ainsi : diviser en partitionnant le tableau autour d’un pivot ; régner en triant récursivement chacun des deux sous-tableaux ; combiner en concaténant les résultats (petits triés + pivot + grands triés).
Le tri fusion divise toujours le tableau en deux parties égales (au milieu), tandis que le tri rapide divise selon les valeurs des éléments par rapport au pivot (la division n’est donc pas nécessairement équilibrée).
Analyse de la complexité
Complexité dans le meilleur cas
Dans le meilleur cas, le pivot divise toujours le tableau en deux parties à peu près égales.
Exercice : meilleur cas
Si on divise toujours le tableau en deux parties égales, combien de niveaux de récursivité y aura-t-il pour un tableau de taille \(n\) ?
À chaque niveau, quelle est la complexité totale pour partitionner tous les sous-tableaux ?
Quelle est donc la complexité dans le meilleur cas ? Comparez avec le tri fusion.
Solution
Il y aura \(\log_2(n)\) niveaux de récursivité (on divise par 2 à chaque fois jusqu’à obtenir des tableaux de taille 1).
À chaque niveau, on doit parcourir tous les éléments du tableau pour effectuer les partitionnements. La complexité totale à chaque niveau est donc \(O(n)\).
La complexité dans le meilleur cas est \(O(n \log n)\). C’est la même complexité que le tri fusion dans tous les cas.
Cas particuliers défavorables
Exercice : pire cas
Considérez le tableau déjà trié :
[1, 2, 3, 4, 5, 6, 7, 8]. Si on choisit systématiquement le premier élément comme pivot, que se passe-t-il à chaque étape ?Combien de niveaux de récursivité y aura-t-il dans ce cas ?
Quelle est la complexité dans le pire cas du tri rapide ?
Donnez d’autres exemples de tableaux qui conduisent au pire cas (selon le choix du pivot).
Solution
Le pivot sera toujours le plus petit élément. La partition donnera un sous-tableau vide à gauche et un sous-tableau de taille \(n-1\) à droite. On ne réduit la taille que de 1 à chaque étape.
Il y aura \(n\) niveaux de récursivité.
La complexité dans le pire cas est \(O(n^2)\) car on a \(n\) niveaux et à chaque niveau \(i\) on traite \(i\) éléments : \(1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} = O(n^2)\).
Autres exemples : tableau trié en ordre inverse si on choisit le premier élément comme pivot ; tout tableau où le pivot choisi est systématiquement le minimum ou le maximum.
Comparaison avec le tri fusion
Exercice : tri rapide vs tri fusion
- Complétez le tableau suivant :
| Critère | Tri fusion | Tri rapide |
|---|---|---|
| Meilleur cas | ||
| Cas moyen | ||
| Pire cas | ||
| Complexité spatiale | ||
| Stabilité |
Le tri fusion est dit stable. Qu’est-ce que cela signifie ? Le tri rapide est-il stable ?
Dans quelles situations préférerait-on le tri fusion au tri rapide ?
Malgré son pire cas en \(O(n^2)\), pourquoi le tri rapide est-il souvent utilisé en pratique ?
Solution
- Tableau comparatif :
| Critère | Tri fusion | Tri rapide |
|---|---|---|
| Meilleur cas | \(O(n \log n)\) | \(O(n \log n)\) |
| Cas moyen | \(O(n \log n)\) | \(O(n \log n)\) |
| Pire cas | \(O(n \log n)\) | \(O(n^2)\) |
| Complexité spatiale | \(O(n)\) | \(O(n)\) |
| Stabilité | Stable | Stable (avec cette implémentation) |
Un tri est dit stable s’il préserve l’ordre relatif des éléments égaux. Avec l’implémentation par compréhensions de liste, le tri rapide est stable car on conserve l’ordre des éléments dans les listes créées.
On préférerait le tri fusion lorsqu’on a besoin d’une complexité garantie \(O(n \log n)\) dans tous les cas, ou lorsqu’on trie des données déjà partiellement triées (risque de pire cas pour le tri rapide).
Le tri rapide est souvent utilisé en pratique car en moyenne il est très efficace, et avec un bon choix de pivot (médiane, randomisé), le pire cas est très rare.
Implémentation en Python
Exercice : compléter le code
Voici une implémentation simple du tri rapide à compléter :
def tri_rapide(tab):
if len(tab) <= 1:
return tab
pivot = tab[0]
petits = [x for x in tab[1:] if .........]
egaux = [x for x in tab if ...]
grands = [x for x in tab[1:] if .........]
return ..................... + egaux + .....................
Complétez les trois compréhensions de liste pour séparer les éléments selon leur valeur par rapport au pivot.
Complétez la dernière ligne pour combiner les résultats des appels récursifs.
Testez votre implémentation sur les tableaux
[3, 6, 8, 10, 1, 2, 1],[1, 2, 3, 4, 5]et[5, 4, 3, 2, 1].
Solution
def tri_rapide(tab):
if len(tab) <= 1:
return tab
pivot = tab[0]
petits = [x for x in tab[1:] if x < pivot]
egaux = [x for x in tab if x == pivot]
grands = [x for x in tab[1:] if x > pivot]
return tri_rapide(petits) + egaux + tri_rapide(grands)
Pour aller plus loin
Exercice : optimisations
Comment pourrait-on améliorer le choix du pivot pour éviter le pire cas ?
Recherchez ce qu’est le tri rapide randomisé. En quoi cela améliore-t-il les performances ?
Pour de petits tableaux (taille < 10), le tri rapide n’est pas optimal. Quelle optimisation peut-on envisager ?
Solution
Pour améliorer le choix du pivot : choisir la médiane de trois éléments (premier, milieu, dernier) ; choisir un pivot aléatoire ; utiliser la médiane réelle (mais coûteux à calculer).
Le tri rapide randomisé choisit le pivot de manière aléatoire à chaque étape. Cela garantit une complexité moyenne \(O(n \log n)\) quelle que soit l’entrée, évite les pires cas systématiques et rend les performances indépendantes de l’ordre initial des données.
Pour de petits tableaux, on peut utiliser le tri par insertion qui est plus efficace sur de petites tailles car il a moins de surcoût dû à la récursivité. On combine les deux algorithmes : tri rapide pour diviser jusqu’à des tableaux de petite taille, puis tri par insertion pour terminer.
- Le tri rapide suit le paradigme diviser pour régner : il partitionne le tableau autour d’un pivot, puis trie récursivement chaque partie.
- Sa complexité est O(n log n) en moyenne et dans le meilleur cas, mais O(n²) dans le pire cas (pivot systématiquement mal choisi).
- Contrairement au tri fusion , le travail principal se fait lors de la division (partition) et non lors de la combinaison.
- En pratique, le tri rapide est souvent très performant ; un choix aléatoire ou médian du pivot rend le pire cas extrêmement improbable.