Chapitre 10 — Tri rapide
Partitionner autour d’un pivot pour trier efficacement en moyenne en O(n log n)
| Idée directrice — Le tri rapide transforme un problème de tri en deux sous-problèmes en plaçant un pivot à sa position définitive, puis en triant récursivement les parties gauche et droite. |
| Schéma conceptuel |
| 1. Tableau initial 2. Choisir un pivot 3. Partitionner : [valeurs <= pivot] | pivot | [valeurs > pivot] 4. Trier récursivement la partie gauche 5. Trier récursivement la partie droite 6. Obtenir le tableau entièrement trié |
Fiche pédagogique du chapitre
Objectifs d’apprentissage
À la fin de ce chapitre, l’étudiant devra être capable de :
- expliquer le rôle du pivot et l’objectif d’une partition ;
- distinguer les éléments placés à gauche et à droite du pivot ;
- réaliser manuellement une partition complète ;
- utiliser plusieurs stratégies de choix du pivot ;
- écrire un tri rapide récursif avec un cas de base correct ;
- analyser le meilleur cas, le cas moyen et le pire cas ;
- relier la qualité des partitions à la profondeur de récursion ;
- expliquer le caractère en place et non stable du tri rapide classique ;
- choisir une stratégie de pivot adaptée aux données ;
- comparer le tri rapide au tri fusion et aux tris élémentaires.
Prérequis
- Tableaux, indices et échanges de valeurs.
- Fonctions, procédures et paramètres.
- Récursivité et pile des appels.
- Complexités O(n), O(log n), O(n log n) et O(n²).
- Principe « diviser pour régner ».
- Tri fusion et notions de stabilité.
Organisation proposée
Partie | Contenu | Durée indicative |
|---|---|---|
| 10.1 | Principe, pivot et partitionnement | 1 h 30 |
| 10.2 | Méthodes de partition et choix du pivot | 2 h |
| 10.3 | Récursivité et tri des sous-tableaux | 1 h 30 |
| 10.4 | Analyse des performances et tri en place | 1 h 30 |
| Applications | Cas d’usage et choix de la méthode | 1 h |
| TD | Traces, correction et analyse | 2 h |
| TP | Instrumentation et comparaison des pivots | 2 h 30 |
| Positionnement dans le parcours — Le tri rapide est un algorithme très performant en pratique, mais sa complexité dépend fortement de la qualité des partitions. L’étudiant doit donc comprendre le mécanisme de partition, et non seulement mémoriser le pseudo-code. |
Introduction
Le tri rapide, appelé quicksort en anglais, est un algorithme de tri fondé sur le paradigme « diviser pour régner ». Contrairement au tri fusion, il ne divise pas d’abord le tableau en deux moitiés de tailles fixes. Il choisit une valeur particulière appelée pivot, puis réorganise le tableau afin de placer les petites valeurs d’un côté et les grandes valeurs de l’autre.
Une fois le pivot placé à sa position définitive, il ne reste plus qu’à appliquer le même procédé aux deux sous-tableaux. Lorsque les partitions sont équilibrées, la profondeur de récursion est logarithmique et le coût total est de l’ordre de n log n. Lorsque les partitions sont très déséquilibrées, le coût peut devenir quadratique.
| Invariant central — Après une partition correcte, le pivot se trouve à la position qu’il occupera dans le tableau final trié. Les éléments situés à gauche respectent la relation choisie avec le pivot, et ceux situés à droite respectent la relation complémentaire. |
10.1 Principe
10.1.1 Choix d’un pivot
Le pivot est une valeur de référence utilisée pour répartir les autres éléments. Il peut être pris au début, à la fin, au centre ou à une position aléatoire. Le pivot n’est pas nécessairement la médiane réelle du tableau ; il sert uniquement à construire une partition.
- Un bon pivot produit deux sous-tableaux de tailles comparables.
- Un mauvais pivot produit une partie presque vide et une partie presque aussi grande que le tableau initial.
- La position initiale du pivot ne détermine pas sa position finale après partition.
- Le choix du pivot influence les performances, mais pas le résultat final si l’algorithme est correct.
Stratégie | Avantage principal | Risque principal |
|---|---|---|
| Premier élément | Très simple à programmer | Mauvais sur un tableau déjà trié |
| Dernier élément | Compatible avec la partition de Lomuto | Mauvais sur certaines entrées ordonnées |
| Élément central | Réduit certains cas pathologiques simples | La valeur centrale peut rester extrême |
| Pivot aléatoire | Rend les mauvais cas systématiques très improbables | Nécessite un générateur aléatoire |
| Médiane de trois | Bon compromis pratique | Calcul légèrement plus coûteux |
10.1.2 Partitionnement
Partitionner consiste à réorganiser l’intervalle étudié autour du pivot. Une partition classique garantit qu’après son exécution, toutes les valeurs situées dans une première zone sont inférieures ou égales au pivot et toutes les valeurs d’une seconde zone sont supérieures au pivot. D’autres conventions sont possibles, notamment pour gérer les doublons.
| Exemple de partition autour du pivot 29 |
| Tableau initial : [18, 45, 12, 29, 33, 7, 26] Pivot choisi : 29 Une partition possible : [18, 12, 7, 26] 29 [33, 45] gauche pivot droite Le contenu de chaque zone est correct, mais il n’est pas encore trié. |
| Attention — Une partition ne trie pas complètement les deux zones. Elle impose seulement une relation entre leurs éléments et le pivot. |
10.1.3 Éléments inférieurs et supérieurs au pivot
La convention de comparaison doit être définie précisément. Avec la convention « gauche ≤ pivot, droite > pivot », les valeurs égales au pivot rejoignent la zone gauche. Avec la convention « gauche < pivot, droite ≥ pivot », elles rejoignent la zone droite. Une mauvaise cohérence entre la partition et les appels récursifs peut provoquer des boucles ou des oublis.
Convention | Zone gauche | Zone droite | Remarque |
|---|---|---|---|
| A | valeur ≤ pivot | valeur > pivot | Simple avec Lomuto |
| B | valeur < pivot | valeur ≥ pivot | Équivalente si appliquée partout |
| Trois zones | valeur < pivot | valeur > pivot | Une zone centrale regroupe les valeurs égales |
10.1.4 Invariant de partition
Pour prouver et tracer une partition, on identifie les zones déjà traitées et la zone encore inconnue. Dans la partition de Lomuto avec pivot à la fin, un indice i sépare les éléments déjà reconnus comme inférieurs ou égaux au pivot des autres éléments parcourus.
| Invariant de la partition de Lomuto — Avant chaque comparaison avec T[j] : les cases de gauche à i contiennent des valeurs ≤ pivot ; les cases de i + 1 à j - 1 contiennent des valeurs > pivot ; les cases de j à droite - 1 ne sont pas encore traitées ; le pivot reste en T[droite]. |
| PSEUDO-CODE — Vue abstraite du tri rapide |
| Procédure TriRapide(T, gauche, droite) Si gauche < droite Alors positionPivot ← Partitionner(T, gauche, droite) TriRapide(T, gauche, positionPivot - 1) TriRapide(T, positionPivot + 1, droite) FinSi FinProcédure |
| Remarque — La procédure Partitionner place le pivot à sa position définitive et retourne son indice. |
10.2 Méthodes de partition
10.2.1 Pivot à la fin : partition de Lomuto
La partition de Lomuto place le pivot dans la dernière case. Un indice i représente la fin de la zone des valeurs inférieures ou égales au pivot. L’indice j parcourt les autres éléments. Chaque fois que T[j] respecte la relation, la zone gauche est agrandie par un échange.
| PSEUDO-CODE — Partition de Lomuto — pivot à la fin |
| Fonction PartitionLomuto(T, gauche, droite) : Entier pivot ← T[droite] i ← gauche - 1 Pour j allant de gauche à droite - 1 Faire Si T[j] ≤ pivot Alors i ← i + 1 Échanger(T[i], T[j]) FinSi FinPour Échanger(T[i + 1], T[droite]) Retourner i + 1 FinFonction |
| Trace résumée — T = [9, 4, 8, 3, 1, 2, 5], pivot = 5 |
| Départ : i = -1 j=0 : 9 > 5 → aucune modification j=1 : 4 ≤ 5 → i=0, échange 9 et 4 : [4, 9, 8, 3, 1, 2, 5] j=2 : 8 > 5 → aucune modification j=3 : 3 ≤ 5 → i=1, échange 9 et 3 : [4, 3, 8, 9, 1, 2, 5] j=4 : 1 ≤ 5 → i=2, échange 8 et 1 : [4, 3, 1, 9, 8, 2, 5] j=5 : 2 ≤ 5 → i=3, échange 9 et 2 : [4, 3, 1, 2, 8, 9, 5] Final : échange T[4] et pivot : [4, 3, 1, 2, 5, 9, 8] Indice retourné : 4 |
10.2.2 Pivot au début
Une version simple consiste à déplacer temporairement le premier élément vers la fin, puis à utiliser la partition de Lomuto. Une autre possibilité est d’adapter directement les indices. Déplacer le pivot permet de réutiliser une partition déjà validée et réduit le risque d’erreur.
| PSEUDO-CODE — Partition avec pivot initial au début |
| Fonction PartitionPivotDebut(T, gauche, droite) : Entier Échanger(T[gauche], T[droite]) Retourner PartitionLomuto(T, gauche, droite) FinFonction |
| Remarque — Le premier élément devient le pivot placé à la fin avant le partitionnement. |
10.2.3 Pivot central et partition de Hoare
La partition de Hoare utilise généralement une valeur centrale comme pivot. Deux indices avancent depuis les extrémités : l’indice gauche cherche une valeur trop grande et l’indice droit cherche une valeur trop petite. Ces deux valeurs sont échangées jusqu’au croisement des indices.
| PSEUDO-CODE — Partition de Hoare — pivot central |
| Fonction PartitionHoare(T, gauche, droite) : Entier pivot ← T[(gauche + droite) div 2] i ← gauche - 1 j ← droite + 1 TantQue Vrai Faire Répéter i ← i + 1 Jusqu’à T[i] ≥ pivot Répéter j ← j - 1 Jusqu’à T[j] ≤ pivot Si i ≥ j Alors Retourner j FinSi Échanger(T[i], T[j]) FinTantQue FinFonction |
| Remarque — L’indice retourné sépare les deux partitions ; il ne représente pas nécessairement la position définitive d’un pivot matériellement déplacé. |
| PSEUDO-CODE — Tri rapide associé à la partition de Hoare |
| Procédure TriRapideHoare(T, gauche, droite) Si gauche < droite Alors séparation ← PartitionHoare(T, gauche, droite) TriRapideHoare(T, gauche, séparation) TriRapideHoare(T, séparation + 1, droite) FinSi FinProcédure |
| Erreur classique — Les bornes récursives de Lomuto et de Hoare ne sont pas identiques. Mélanger la partition d’une méthode avec les bornes de l’autre peut provoquer une récursion infinie ou laisser des éléments non triés. |
10.2.4 Pivot aléatoire
Le choix aléatoire du pivot ne supprime pas le pire cas théorique, mais il empêche une organisation prévisible des données de provoquer systématiquement ce pire cas. La probabilité d’obtenir de mauvaises partitions à tous les niveaux devient très faible.
| PSEUDO-CODE — Partition randomisée |
| Fonction PartitionAleatoire(T, gauche, droite) : Entier indice ← EntierAleatoire(gauche, droite) Échanger(T[indice], T[droite]) Retourner PartitionLomuto(T, gauche, droite) FinFonction |
10.2.5 Médiane de trois
La stratégie de la médiane de trois compare le premier élément, l’élément central et le dernier élément, puis choisit leur valeur médiane comme pivot. Elle évite souvent de sélectionner une valeur extrême sur des données déjà partiellement ordonnées.
| PSEUDO-CODE — Choix du pivot par médiane de trois |
| Fonction IndiceMedianeTrois(T, gauche, droite) : Entier milieu ← (gauche + droite) div 2 Si T[gauche] > T[milieu] Alors Échanger(T[gauche], T[milieu]) FinSi Si T[gauche] > T[droite] Alors Échanger(T[gauche], T[droite]) FinSi Si T[milieu] > T[droite] Alors Échanger(T[milieu], T[droite]) FinSi Retourner milieu FinFonction |
Méthode | Coût de sélection | Comportement pratique | Remarque |
|---|---|---|---|
| Début / fin | O(1) | Très dépendant de l’ordre initial | Pédagogique mais fragile |
| Centre | O(1) | Souvent meilleur sur des données ordonnées | La valeur peut rester extrême |
| Aléatoire | O(1) | Robuste face aux entrées adverses | Performance probabiliste |
| Médiane de trois | O(1) | Très bon compromis fréquent | Quelques comparaisons supplémentaires |
10.3 Récursivité
10.3.1 Tri de la partie gauche
Après une partition de Lomuto, le pivot est à l’indice p. La partie gauche correspond à l’intervalle [gauche, p - 1]. Elle ne contient que des valeurs inférieures ou égales au pivot, mais ces valeurs ne sont pas nécessairement classées entre elles.
10.3.2 Tri de la partie droite
La partie droite correspond à l’intervalle [p + 1, droite]. Elle ne contient que des valeurs supérieures au pivot selon la convention retenue. Elle est triée indépendamment par un second appel récursif.
10.3.3 Cas de base
La récursion s’arrête lorsque l’intervalle contient zéro ou un seul élément. La condition gauche < droite suffit : si gauche est égal ou supérieur à droite, aucune partition n’est nécessaire.
| Condition de terminaison — Chaque appel récursif doit travailler sur un intervalle strictement plus petit. Le pivot déjà placé doit être exclu des deux appels récursifs. |
| PSEUDO-CODE — Tri rapide complet avec Lomuto |
| Procédure TriRapide(T, gauche, droite) Si gauche < droite Alors p ← PartitionLomuto(T, gauche, droite) TriRapide(T, gauche, p - 1) TriRapide(T, p + 1, droite) FinSi FinProcédure Algorithme Principal Lire n Pour i allant de 0 à n - 1 Faire Lire T[i] FinPour TriRapide(T, 0, n - 1) Afficher T FinAlgorithme |
10.3.4 Arbre de récursion
L’arbre de récursion représente les sous-tableaux traités. Sa hauteur dépend de l’équilibre des partitions. Des partitions proches de n/2 produisent un arbre peu profond ; des partitions de tailles 0 et n - 1 produisent une chaîne d’appels.
| Exemple conceptuel de partitions équilibrées |
| Intervalle de taille 8 [8] / [4] [3] / \ / [2] [1] [1] [1] / [1] [0] Hauteur de l’ordre de log₂(n). |
| Exemple conceptuel de partitions dégénérées |
| Intervalle de taille 8 [8] [7] [6] [5] ... Hauteur de l’ordre de n. |
10.3.5 Profondeur de pile et optimisation
Dans une implémentation récursive classique, chaque appel conserve ses bornes dans la pile d’exécution. La profondeur moyenne est O(log n), mais elle peut atteindre O(n) dans le pire cas. Une optimisation consiste à traiter récursivement la plus petite partition et à traiter l’autre par une boucle. La pile est alors limitée à O(log n), même lorsque les partitions sont déséquilibrées.
| PSEUDO-CODE — Réduction de la profondeur de récursion |
| Procédure TriRapidePileLimitee(T, gauche, droite) TantQue gauche < droite Faire p ← PartitionLomuto(T, gauche, droite) Si p - gauche < droite - p Alors TriRapidePileLimitee(T, gauche, p - 1) gauche ← p + 1 Sinon TriRapidePileLimitee(T, p + 1, droite) droite ← p - 1 FinSi FinTantQue FinProcédure |
| Remarque — La plus petite partie est traitée récursivement ; la plus grande est traitée par itération. |
10.4 Analyse
10.4.1 Coût d’une partition
Une partition parcourt l’intervalle une seule fois. Pour un sous-tableau de taille n, son coût est donc Θ(n). Le coût total dépend du nombre de niveaux de partitionnement et de la somme des tailles traitées à chaque niveau.
10.4.2 Meilleur cas et cas équilibré
Dans le meilleur cas, chaque pivot sépare le tableau en deux parties presque égales. La relation de récurrence est T(n) = 2T(n/2) + Θ(n). Il existe environ log₂(n) niveaux, et chaque niveau traite au total n éléments. La complexité est donc Θ(n log n).
| Décomposition du coût équilibré |
| Niveau 0 : 1 partition de taille n → coût ≈ n Niveau 1 : 2 partitions de taille n/2 → coût total ≈ n Niveau 2 : 4 partitions de taille n/4 → coût total ≈ n ... Nombre de niveaux ≈ log₂(n) Coût total ≈ n × log₂(n) = Θ(n log n) |
10.4.3 Cas moyen
Le cas moyen considère la distribution des différentes positions possibles du pivot. Même si toutes les partitions ne sont pas parfaitement équilibrées, elles sont suffisamment équilibrées en moyenne pour conserver une complexité attendue en O(n log n). Cette propriété explique l’efficacité pratique du tri rapide avec un pivot aléatoire ou une médiane de trois.
| Interprétation — Le terme « cas moyen » dépend d’un modèle probabiliste sur les entrées ou sur le choix du pivot. Un pivot randomisé permet d’obtenir une complexité attendue O(n log n) indépendamment de l’ordre initial. |
10.4.4 Pire cas
Le pire cas apparaît lorsque chaque pivot est le plus petit ou le plus grand élément du sous-tableau. Une partition a alors une taille n - 1 et l’autre une taille nulle. La relation devient T(n) = T(n - 1) + Θ(n), ce qui conduit à Θ(n²).
| Somme du pire cas |
| Coût ≈ n + (n - 1) + (n - 2) + ... + 2 + 1 = n(n + 1) / 2 = Θ(n²) |
Situation | Tailles des partitions | Profondeur | Temps |
|---|---|---|---|
| Très équilibrée | ≈ n/2 et n/2 | Θ(log n) | Θ(n log n) |
| Moyenne | Variables mais raisonnables | O(log n) attendue | O(n log n) attendu |
| Très déséquilibrée | 0 et n - 1 | Θ(n) | Θ(n²) |
10.4.5 Influence du choix du pivot
Le pivot ne modifie pas le coût linéaire d’une partition, mais il détermine la taille des deux problèmes récursifs. Le premier ou le dernier élément peut convenir sur des données aléatoires, mais il devient dangereux sur des tableaux déjà triés. Le pivot aléatoire et la médiane de trois réduisent la probabilité de partitions extrêmes répétées.
Type de données | Pivot début/fin | Pivot central | Pivot aléatoire | Médiane de trois |
|---|---|---|---|---|
| Déjà triées | Très mauvais | Souvent bon | Bon attendu | Très bon |
| Triées en ordre inverse | Très mauvais | Souvent bon | Bon attendu | Très bon |
| Aléatoires | Généralement bon | Généralement bon | Très robuste | Très bon |
| Beaucoup de doublons | Peut se dégrader | Peut se dégrader | Peut se dégrader | Partition à trois voies préférable |
10.4.6 Tri en place et mémoire
Le tri rapide classique échange les éléments directement dans le tableau. En dehors de la pile des appels récursifs, il utilise seulement quelques variables et est donc considéré comme un tri en place. La mémoire de pile est O(log n) en moyenne et O(n) dans le pire cas pour la version récursive naïve.
- Mémoire auxiliaire hors pile : O(1).
- Pile récursive moyenne : O(log n).
- Pile récursive dans le pire cas : O(n).
- Version avec récursion sur la plus petite partition : pile O(log n).
10.4.7 Stabilité
Le tri rapide classique n’est pas stable. Les échanges peuvent inverser l’ordre relatif de deux éléments égaux. Cette propriété doit être prise en compte lorsqu’on trie des enregistrements selon une clé tout en souhaitant conserver un ordre secondaire existant.
| Exemple de perte de stabilité |
| Entrée triée auparavant par nom : [(15, Ali), (12, Lina), (15, Sara)] Tri rapide selon la note uniquement : [(12, Lina), (15, Sara), (15, Ali)] Les deux notes 15 ont changé d’ordre relatif. |
10.4.8 Comparaison avec le tri fusion
Critère | Tri rapide | Tri fusion |
|---|---|---|
| Temps moyen | O(n log n) | O(n log n) |
| Pire cas | O(n²) | O(n log n) |
| Mémoire sur tableau | Faible, tri en place | O(n) auxiliaire |
| Stabilité | Non, généralement | Oui |
| Localité mémoire | Très bonne | Bonne mais copies supplémentaires |
| Listes chaînées | Moins naturel | Très adapté |
| Usage fréquent | Tableaux en mémoire | Stabilité, listes, tri externe |
Applications
Application 1 — Trier des notes
Une plateforme pédagogique doit classer rapidement un grand tableau de notes numériques. Les données tiennent en mémoire, la stabilité n’est pas indispensable et les échanges sont peu coûteux. Un tri rapide avec pivot aléatoire est adapté.
| PSEUDO-CODE — Tri croissant des notes |
| Procédure TrierNotes(Notes, n) TriRapide(Notes, 0, n - 1) FinProcédure |
Application 2 — Classer des produits par prix
Chaque élément est un enregistrement contenant un identifiant, un nom et un prix. La partition compare uniquement le champ prix, mais échange l’enregistrement entier afin de conserver la cohérence des informations associées.
| PSEUDO-CODE — Partition d’enregistrements selon le prix |
| Fonction PartitionProduits(P, gauche, droite) : Entier pivot ← P[droite].prix i ← gauche - 1 Pour j allant de gauche à droite - 1 Faire Si P[j].prix ≤ pivot Alors i ← i + 1 Échanger(P[i], P[j]) FinSi FinPour Échanger(P[i + 1], P[droite]) Retourner i + 1 FinFonction |
Application 3 — Classement décroissant
Pour obtenir un classement décroissant, il suffit d’inverser la relation utilisée par la partition. Les valeurs supérieures ou égales au pivot sont alors placées dans la zone gauche.
| PSEUDO-CODE — Partition décroissante |
| Fonction PartitionDecroissante(T, gauche, droite) : Entier pivot ← T[droite] i ← gauche - 1 Pour j allant de gauche à droite - 1 Faire Si T[j] ≥ pivot Alors i ← i + 1 Échanger(T[i], T[j]) FinSi FinPour Échanger(T[i + 1], T[droite]) Retourner i + 1 FinFonction |
Application 4 — Sélection du k-ième élément
Le partitionnement du tri rapide peut être utilisé sans trier entièrement le tableau. Après la partition, si le pivot se trouve à l’indice recherché, le résultat est obtenu. Sinon, une seule des deux parties doit être explorée. Cette méthode est appelée sélection rapide ou quickselect.
| PSEUDO-CODE — Sélection rapide |
| Fonction SelectionRapide(T, gauche, droite, k) : Valeur Si gauche = droite Alors Retourner T[gauche] FinSi p ← PartitionAleatoire(T, gauche, droite) Si k = p Alors Retourner T[p] SinonSi k < p Alors Retourner SelectionRapide(T, gauche, p - 1, k) Sinon Retourner SelectionRapide(T, p + 1, droite, k) FinSi FinFonction |
| Remarque — L’indice k est supposé valide. La complexité attendue est O(n), mais le pire cas reste O(n²). |
Application 5 — Données contenant de nombreux doublons
Lorsque de nombreuses valeurs sont identiques, une partition à deux zones peut créer des partitions déséquilibrées. Une partition à trois voies sépare les valeurs inférieures, égales et supérieures au pivot. La zone égale n’a plus besoin d’être triée récursivement.
| PSEUDO-CODE — Partition à trois voies |
| Procédure TriRapideTroisVoies(T, gauche, droite) Si gauche ≥ droite Alors Retourner FinSi pivot ← T[gauche] petit ← gauche courant ← gauche + 1 grand ← droite TantQue courant ≤ grand Faire Si T[courant] < pivot Alors Échanger(T[petit], T[courant]) petit ← petit + 1 courant ← courant + 1 SinonSi T[courant] > pivot Alors Échanger(T[courant], T[grand]) grand ← grand - 1 Sinon courant ← courant + 1 FinSi FinTantQue TriRapideTroisVoies(T, gauche, petit - 1) TriRapideTroisVoies(T, grand + 1, droite) FinProcédure |
Erreurs fréquentes et méthode de vérification
Erreur | Conséquence | Correction |
|---|---|---|
| Inclure le pivot dans un appel récursif | Récursion infinie possible | Utiliser p - 1 et p + 1 avec Lomuto |
| Confondre les bornes de Hoare et Lomuto | Sous-tableau non trié ou boucle | Employer la convention associée à la partition |
| Oublier le cas de base | Dépassement de pile | Tester gauche < droite |
| Comparer avec des relations incohérentes | Partition invalide | Définir précisément ≤ / > ou < / ≥ |
| Échanger seulement la clé d’un enregistrement | Données dissociées | Échanger l’enregistrement complet |
| Choisir systématiquement une extrémité | Pire cas sur tableau ordonné | Randomiser ou utiliser médiane de trois |
| Checklist de validation — Pour tester une partition, vérifier séparément : 1) la conservation de tous les éléments ; 2) la relation de la zone gauche avec le pivot ; 3) la relation de la zone droite ; 4) l’indice retourné ; 5) la diminution stricte des intervalles récursifs. |
Travaux dirigés
TD 1 — Identifier un pivot et les zones
Pour le tableau [31, 12, 45, 7, 26, 18, 39] et le pivot 26, proposer une partition valide. Préciser les zones gauche et droite.
TD 2 — Tracer la partition de Lomuto
Tracer la partition du tableau [10, 80, 30, 90, 40, 50, 70] en utilisant le dernier élément comme pivot. Indiquer i, j et le tableau après chaque échange.
TD 3 — Pivot au début
Adapter la partition afin d’utiliser le premier élément comme pivot, puis appliquer la méthode au tableau [25, 10, 30, 15, 20].
TD 4 — Partition de Hoare
Appliquer la partition de Hoare au tableau [24, 9, 29, 14, 19, 27] avec la valeur centrale comme pivot. Montrer les déplacements des indices.
TD 5 — Arbre de récursion
Construire l’arbre des intervalles pour le tableau [4, 2, 7, 3, 1, 6, 5], en supposant que le dernier élément est toujours choisi comme pivot.
TD 6 — Analyse des cas
Déterminer la complexité temporelle lorsque les partitions ont les tailles suivantes : a) n/2 et n/2 ; b) n/4 et 3n/4 ; c) 0 et n - 1.
TD 7 — Doublons
Expliquer le comportement du tri rapide classique sur [5, 5, 5, 5, 5, 5]. Proposer une amélioration.
TD 8 — Tri décroissant
Modifier la partition de Lomuto pour obtenir un tableau trié dans l’ordre décroissant. Tester sur [7, 2, 9, 1, 5].
TD 9 — Correction d’un algorithme
L’algorithme suivant appelle TriRapide(T, gauche, p) et TriRapide(T, p, droite) après une partition de Lomuto. Identifier l’erreur et proposer les bornes correctes.
TD 10 — Choix entre tri rapide et tri fusion
Pour chacun des contextes suivants, choisir la méthode la plus adaptée et justifier : tableau numérique en mémoire ; liste chaînée ; besoin de stabilité ; mémoire très limitée ; garantie stricte O(n log n).
Corrigés indicatifs des travaux dirigés
Correction du TD 1
| Une partition possible |
| [12, 7, 18] 26 [31, 45, 39] Toutes les valeurs de gauche sont inférieures à 26. Toutes les valeurs de droite sont supérieures à 26. L’ordre interne des deux zones n’a pas d’importance à cette étape. |
Correction du TD 2
| Trace de Lomuto — pivot 70 |
| T = [10, 80, 30, 90, 40, 50, 70], i = -1 j=0 : 10 ≤ 70 → i=0, échange T[0] avec T[0] j=1 : 80 > 70 → rien j=2 : 30 ≤ 70 → i=1, échange 80 et 30 [10, 30, 80, 90, 40, 50, 70] j=3 : 90 > 70 → rien j=4 : 40 ≤ 70 → i=2, échange 80 et 40 [10, 30, 40, 90, 80, 50, 70] j=5 : 50 ≤ 70 → i=3, échange 90 et 50 [10, 30, 40, 50, 80, 90, 70] Final : échange T[4] et T[6] [10, 30, 40, 50, 70, 90, 80] Position du pivot : 4 |
Correction du TD 3
On peut échanger le premier et le dernier élément, puis appliquer Lomuto. Pour [25, 10, 30, 15, 20], le tableau devient d’abord [20, 10, 30, 15, 25]. La partition place 25 entre les valeurs inférieures et les valeurs supérieures, par exemple [20, 10, 15, 25, 30].
| PSEUDO-CODE — Adaptation avec pivot au début |
| Fonction PartitionDebut(T, gauche, droite) : Entier Échanger(T[gauche], T[droite]) Retourner PartitionLomuto(T, gauche, droite) FinFonction |
Correction du TD 4
Le pivot central vaut 29 ou 14 selon la convention d’arrondi et la formule utilisée. Avec pivot T[(0 + 5) div 2] = T[2] = 29, l’indice i avance jusqu’à 29 et j recule jusqu’à 27 ; ces valeurs sont échangées. Le processus continue jusqu’au croisement. L’indice j retourné sépare les deux intervalles à trier.
| Critère de correction — Dans la partition de Hoare, il existe plusieurs traces valides selon le pivot central exact et la gestion des valeurs égales. L’essentiel est de respecter les mouvements des indices et les bornes récursives [gauche, j] et [j + 1, droite]. |
Correction du TD 5
Avec le dernier élément comme pivot, le premier pivot est 5. Les éléments inférieurs sont placés à gauche et les éléments supérieurs à droite. L’arbre exact dépend des permutations créées par la partition, mais chaque nœud doit représenter un intervalle strictement plus petit et exclure le pivot déjà placé.
| Structure attendue |
| Intervalle [0,6], pivot 5 ├── partie gauche : valeurs < ou = 5 │ ├── sous-partie gauche │ └── sous-partie droite └── partie droite : valeurs > 5 ├── sous-partie gauche └── sous-partie droite |
Correction du TD 6
Partitions | Profondeur | Complexité |
|---|---|---|
| n/2 et n/2 | Θ(log n) | Θ(n log n) |
| n/4 et 3n/4 | Θ(log n) | Θ(n log n) |
| 0 et n - 1 | Θ(n) | Θ(n²) |
Même si n/4 et 3n/4 ne sont pas parfaitement équilibrées, les deux tailles restent des fractions constantes de n ; la hauteur reste logarithmique.
Correction du TD 7
Avec Lomuto et la condition ≤ pivot, chaque valeur identique est déplacée vers la zone gauche. Le pivot termine à l’extrémité droite de l’intervalle et la récursion porte sur n - 1 éléments. Le temps devient quadratique. Une partition à trois voies regroupe immédiatement toutes les valeurs égales au pivot.
Correction du TD 8
| PSEUDO-CODE — Partition décroissante corrigée |
| Fonction PartitionDecroissante(T, gauche, droite) : Entier pivot ← T[droite] i ← gauche - 1 Pour j allant de gauche à droite - 1 Faire Si T[j] ≥ pivot Alors i ← i + 1 Échanger(T[i], T[j]) FinSi FinPour Échanger(T[i + 1], T[droite]) Retourner i + 1 FinFonction |
Sur [7, 2, 9, 1, 5], le résultat final est [9, 7, 5, 2, 1].
Correction du TD 9
Après une partition de Lomuto, le pivot est déjà à sa position définitive. Il doit être exclu des appels récursifs. Les bornes correctes sont [gauche, p - 1] et [p + 1, droite]. Appeler avec p dans les deux intervalles peut empêcher la réduction du problème.
Correction du TD 10
Contexte | Choix conseillé | Justification |
|---|---|---|
| Tableau numérique en mémoire | Tri rapide | Très bonnes performances pratiques et faible mémoire |
| Liste chaînée | Tri fusion | Découpage et fusion naturels sans accès direct |
| Stabilité indispensable | Tri fusion | Stable dans sa forme classique |
| Mémoire auxiliaire très limitée | Tri rapide | Tri en place, hors pile récursive |
| Garantie stricte O(n log n) | Tri fusion | Pire cas garanti |
Travail pratique — Étude expérimentale du tri rapide
Objectifs
- implémenter une partition correcte ;
- comparer plusieurs stratégies de choix du pivot ;
- mesurer le nombre de comparaisons et d’échanges ;
- observer la profondeur maximale de récursion ;
- comparer les résultats théoriques et expérimentaux ;
- valider systématiquement le résultat du tri.
Travail demandé
- Implémenter le tri rapide avec pivot à la fin.
- Ajouter une version avec pivot aléatoire.
- Ajouter une version utilisant la médiane de trois.
- Compter les comparaisons et les échanges effectués par chaque version.
- Mesurer la profondeur maximale de récursion.
- Tester des tableaux aléatoires, triés, inversés, presque triés et riches en doublons.
- Vérifier après chaque test que le tableau est effectivement trié.
- Comparer les résultats avec le tri fusion du chapitre précédent.
- Présenter les mesures dans un tableau et rédiger une conclusion argumentée.
Jeux d’essai minimaux
Jeu | Données | Objectif |
|---|---|---|
| Vide | [] | Vérifier le cas sans élément |
| Un élément | [7] | Vérifier le cas de base |
| Déjà trié | [1,2,3,4,5,6,7,8] | Observer un pivot extrême |
| Ordre inverse | [8,7,6,5,4,3,2,1] | Observer le déséquilibre |
| Doublons | [5,1,5,3,5,2,5] | Évaluer la gestion des égalités |
| Aléatoire | 1000 valeurs générées | Comparer les stratégies |
Instrumentation suggérée
| PSEUDO-CODE — Compteurs de performance |
| Variables globales comparaisons : Entier ← 0 échanges : Entier ← 0 profondeurMax : Entier ← 0 Procédure EchangerCompte(a, b) temporaire ← a a ← b b ← temporaire échanges ← échanges + 1 FinProcédure Procédure MettreAJourProfondeur(profondeur) Si profondeur > profondeurMax Alors profondeurMax ← profondeur FinSi FinProcédure |
Résultats attendus
- La version pivot à la fin se dégrade fortement sur les données déjà triées ou inversées.
- La version randomisée produit généralement des partitions plus équilibrées.
- La médiane de trois améliore souvent les données partiellement ordonnées.
- Les trois versions doivent produire exactement le même tableau trié.
- Le nombre de comparaisons croît approximativement comme n log n sur des données ordinaires.
- La profondeur peut devenir linéaire dans les cas dégénérés de la version naïve.
Grille d’évaluation proposée
Critère | Points |
|---|---|
| Partition correcte et robuste | 4 |
| Tri récursif et cas de base | 3 |
| Trois stratégies de pivot | 3 |
| Instrumentation des opérations | 3 |
| Jeux de tests et validation | 3 |
| Analyse théorique et expérimentale | 3 |
| Qualité du compte rendu | 1 |
Synthèse du chapitre
Notion | Idée essentielle |
|---|---|
| Pivot | Valeur de référence choisie pour partitionner un intervalle |
| Partition | Réorganisation séparant les valeurs selon leur relation au pivot |
| Position définitive | Avec Lomuto, le pivot retourné est à sa place finale |
| Récursion | Trier indépendamment les parties gauche et droite |
| Cas de base | Intervalle vide ou réduit à un élément |
| Cas moyen | O(n log n) avec des partitions raisonnables |
| Pire cas | O(n²) lorsque les partitions sont systématiquement extrêmes |
| Mémoire | O(log n) en moyenne pour la pile ; tri en place hors pile |
| Stabilité | Le tri rapide classique n’est pas stable |
| Pivot robuste | Aléatoire ou médiane de trois en pratique |
| À retenir — Le cœur du tri rapide n’est pas la récursion mais la qualité de la partition. Une partition correcte place le pivot, conserve tous les éléments et garantit la diminution stricte des intervalles à traiter. |
Glossaire
Terme | Définition |
|---|---|
| Pivot | Valeur choisie pour répartir les éléments d’un sous-tableau. |
| Partition | Opération qui réorganise les données autour du pivot. |
| Lomuto | Schéma de partition simple utilisant souvent le dernier élément comme pivot. |
| Hoare | Schéma de partition utilisant deux indices progressant depuis les extrémités. |
| Partition équilibrée | Partition dont les deux sous-tableaux ont des tailles comparables. |
| Partition dégénérée | Partition produisant une partie vide et une partie de taille n - 1. |
| Tri en place | Tri utilisant seulement une quantité constante de mémoire auxiliaire, hors pile. |
| Stabilité | Conservation de l’ordre relatif des éléments possédant la même clé. |
| Randomisation | Choix aléatoire réduisant les mauvais cas systématiques. |
| Quickselect | Algorithme utilisant une partition pour sélectionner un élément d’ordre donné. |
Auto-évaluation
Je peux… | Oui | À revoir |
|---|---|---|
| expliquer le rôle du pivot et d’une partition ; | ☐ | ☐ |
| tracer une partition de Lomuto ; | ☐ | ☐ |
| distinguer les bornes récursives de Lomuto et de Hoare ; | ☐ | ☐ |
| écrire le cas de base du tri rapide ; | ☐ | ☐ |
| justifier la complexité moyenne O(n log n) ; | ☐ | ☐ |
| expliquer le pire cas O(n²) ; | ☐ | ☐ |
| choisir une stratégie de pivot adaptée ; | ☐ | ☐ |
| expliquer pourquoi le tri rapide est en place mais non stable ; | ☐ | ☐ |
| comparer le tri rapide au tri fusion ; | ☐ | ☐ |
| tester et valider une implémentation complète. | ☐ | ☐ |
Conclusion
Le tri rapide illustre avec force le lien entre conception algorithmique et analyse des performances. Sa partition est linéaire, mais le coût global dépend de l’équilibre des sous-problèmes. Bien utilisé, avec un pivot randomisé ou une stratégie comme la médiane de trois, il offre d’excellentes performances sur les tableaux en mémoire. Sa maîtrise exige toutefois une attention particulière aux invariants de partition, aux bornes récursives, aux doublons et à la profondeur de pile.