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 :
Le tri rapide fonctionne selon le principe suivant :
Exemple : soit le tableau [7, 2, 1, 6, 8, 5, 3, 4]. Si on choisit 4 comme pivot :
[2, 1, 3] ;[4] ;[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].
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 ?
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).
Dans le meilleur cas, le pivot divise toujours le tableau en deux parties à peu près égales.
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.
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.
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).
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.
| 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 ?
| 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)\) en moyenne, \(O(n^2)\) dans le pire cas (avec cette implémentation) |
| 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.
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].
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)
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 ?
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.