#Tri rapide (Quicksort)Copier le lien

Prérequis : récursivité ; invariants de boucle (chapitre Complexité de l'algorithme 1) ; notions sur les tas et le tri par fusion.

Objectifs d'apprentissage : écrire la partition de Lomuto et prouver son invariant ; dériver les complexités meilleur/moyen/pire cas ; durcir l'implémentation (pivot aléatoire, médiane de trois, coupure vers le tri par insertion) ; savoir choisir quicksort ou une alternative selon les données.

#1. PrincipeCopier le lien

Le tri rapide choisit un élément pivot et partitionne les autres éléments : les plus petits ou égaux à gauche, les plus grands à droite. Le pivot atteint alors sa position définitive, et les deux sous-tableaux se trient récursivement. La récursion se termine lorsque les sous-tableaux comptent moins de deux éléments.

#Animation interactiveCopier le lien

Entrées : le tableau initial (modifiable). Sorties : la séquence de partitionnements et le tableau trié. Point d'attention visuel : à chaque partition, l'élément pivot (highlight) atteint sa place finale et n'est plus jamais touché ; comptez les partitionnements pour sentir la profondeur de récursion.

#2. Implémentation : partition de LomutoCopier le lien

1def partitionner(arr, bas, haut):2    """Partition de Lomuto ; pivot = arr[haut].3    Invariant : à chaque tour de boucle,4      arr[bas..i]  <= pivot,5      arr[i+1..j-1] > pivot,6      arr[j..haut-1] non examinés.7    Renvoie la position finale du pivot."""8    pivot = arr[haut]9    i = bas - 110    for j in range(bas, haut):11        if arr[j] <= pivot:12            i += 113            arr[i], arr[j] = arr[j], arr[i]14    arr[i + 1], arr[haut] = arr[haut], arr[i + 1]

L'invariant de partition est la preuve de correction du tri : après la boucle, tout élément avant la position retournée est ≤ pivot, tout élément après est > pivot ; le pivot est correctement placé et l'induction sur les sous-tableaux termine.

#3. ComplexitéCopier le lien

• Meilleur cas : O(n log n), quand chaque pivot coupe en deux moitiés équilibrées ; la récursion a une profondeur log₂ n et chaque niveau traite n éléments.
• Cas moyen : O(n log n) ; un découpage même très déséquilibré en moyenne (par exemple toujours au quart) donne toujours du n log n en espérance.
• Pire cas : O(n²), quand le pivot est systématiquement l'élément extrême (tableau déjà trié avec le pivot au bord). C'est le vrai risque de l'algorithme ; le mitiger est l'objet de la section suivante.
• Espace : O(log n) en moyenne pour la pile de récursion, O(n) dans le pire cas non atténué.

En pratique, les constantes de quicksort (accès contigus, tout en place) le rendent plus rapide que le tri par fusion sur des tableaux en mémoire ; c'est le tri des bibliothèques C et, sous une forme durcie (introsort), de la STL C++.

#4. Durcir l'implémentationCopier le lien

Trois améliorations standards, chacune contre un échec précis :

1. Pivot aléatoire ou médiane de trois (premier, milieu, dernier) : rend le pire cas extrêmement improbable sur données réelles ; un adversaire ne peut plus le provoquer sans connaître le générateur.
2. Coupure vers le tri par insertion sous un seuil (environ 10 à 20 éléments) : le tri par insertion domine quicksort sur les petits tableaux grâce à ses constantes et à sa performance sur les séquences quasi triées.
3. Toujours trier récursivement le plus petit sous-tableau d'abord (et boucler sur le plus grand) : borne la profondeur de pile à O(log n), éliminant le risque de débordement de pile du pire cas.

La variante introsort pousse la logique jusqu'au bout : quicksort durci, basculement vers heapsort dès que la profondeur dépasse 2 × log₂ n, et tri par insertion en finition ; c'est ce cocktail qui équipe std::sort.

#5. Exercice : médiane de troisCopier le lien

1import random2 3def mediane_de_trois(arr, bas, haut):4    """Réordonne arr[bas], arr[milieu], arr[haut] et renvoie l'indice du milieu."""5    milieu = (bas + haut) // 26    if arr[milieu] < arr[bas]:7        arr[bas], arr[milieu] = arr[milieu], arr[bas]8    if arr[haut] < arr[bas]:9        arr[bas], arr[haut] = arr[haut], arr[bas]10    if arr[haut] < arr[milieu]:11        arr[milieu], arr[haut] = arr[haut], arr[milieu]12    return milieu13 14def partitionner_mediane(arr, bas, haut):

Vérification observable : l'assertion confirme le tri sur cinq tirages aléatoires ; ajoutez le test clé [1, 2, 3, 4, 5, 6, 7, 8] (déjà trié), qui provoquait le pire cas avec le pivot en bout de tableau, et observez que la médiane de trois coupe désormais au milieu.

#6. Comparaison avec les autres trisCopier le lien

#7. Quand préférer autre choseCopier le lien

• Données presque triées et stabilité nécessaire : Timsort (sorted et sort de Python), qui détecte les suites déjà ordonnées.
• Clés entières bornées, très grand volume : tri par comptage ou tri par base, linéaires sous leurs hypothèses.
• Besoin d'un pire cas garanti en O(n log n) avec mémoire constante : tri par tas ou introsort.
• Listes chaînées : le tri par fusion s'impose (pas d'accès direct au pivot, et la fusion de listes est naturelle).