Aller au contenu principal

Tri rapide

Progression

#Tri rapide (Quicksort)

À quoi ça sert ?

À quoi ça sert: trier en place avec d’excellentes performances moyennes et une empreinte mémoire faible. Comment: choisir un pivot, partitionner, puis trier récursivement. Attention au pire cas et à la stabilité.

#Principe de l'algorithme

Le tri rapide fonctionne en sélectionnant un élément "pivot" du tableau et en partitionnant les autres éléments en deux sous-tableaux selon qu'ils sont inférieurs ou supérieurs au pivot. Le tri est alors appliqué récursivement aux deux sous-tableaux.

#Animation interactive

Voici une animation qui illustre le fonctionnement du tri rapide étape par étape :

Chargement...

#Implémentation en Python

pythonpython
1def quicksort(arr, low, high):2    if low < high:3        # Partitionner le tableau et obtenir l'index du pivot4        pi = partition(arr, low, high)5        6        # Trier récursivement les éléments avant et après la partition7        quicksort(arr, low, pi - 1)8        quicksort(arr, pi + 1, high)9 10def partition(arr, low, high):11    # Choisir le dernier élément comme pivot12    pivot = arr[high]13    14    # Index du plus petit élément (indique la position correcte du pivot)

#Complexité

  • Meilleur cas : O(n log n) - Le pivot divise toujours le tableau en deux parties égales
  • Cas moyen : O(n log n) - Le pivot est généralement proche du milieu
  • Pire cas : O(n²) - Le pivot est toujours le plus petit ou le plus grand élément (évité par pivot aléatoire/introsort)
  • Espace : O(log n) - Espace auxiliaire pour la récursion (profondeur moyenne)
Stabilité et ordre

Quicksort n’est pas stable (l’ordre relatif des égaux peut changer). Si la stabilité est requise, préférez mergesort/Timsort.

#Optimisations

  1. Choix du pivot :

    • Premier/ dernier élément (simple mais peut être inefficace)
    • Élément aléatoire (bonne moyenne)
    • Médiane de trois (premier, milieu, dernier)

  2. Tri par insertion pour petits tableaux :

    • Pour les tableaux de taille < 10, utiliser un tri par insertion est souvent plus efficace

  3. Éviter la récursion :

    • Utiliser une pile pour simuler la récursion et éviter les débordements de pile

#Variantes

  • Tri rapide à 3 voies : Gère efficacement les éléments dupliqués
  • Tri rapide introspectif : Commence par quicksort et bascule vers heapsort si la récursion est trop profonde

#Quand préférer autre chose ?

  • Données presque triées et stabilité nécessaire → Timsort (Python sort).
  • Clés entières bornées → counting/radix sort (linéaire).

#Exercice : Implémentation du tri rapide avec choix de pivot médiane de trois

Implémentez une version du tri rapide qui utilise la médiane de trois éléments (premier, milieu, dernier) comme pivot.

#Instructions

  1. Créez une fonction median_of_three(arr, low, high) qui retourne l'index de la médiane de trois éléments.
  2. Modifiez la fonction partition pour utiliser cet index comme pivot.
  3. Testez votre implémentation avec différents tableaux.

#Exemple de code

pythonpython
1import random2 3def median_of_three(arr, low, high):4    mid = (low + high) // 25    if arr[mid] < arr[low]:6        arr[low], arr[mid] = arr[mid], arr[low]7    if arr[high] < arr[low]:8        arr[low], arr[high] = arr[high], arr[low]9    if arr[high] < arr[mid]:10        arr[mid], arr[high] = arr[high], arr[mid]11    return mid12 13def partition_median(arr, low, high):14    # Utiliser la médiane de trois comme pivot

#Comparaison avec d'autres algorithmes

| Algorithme | Meilleur cas | Cas moyen | Pire cas | Espace | Stable | |------------|--------------|-----------|----------|--------|--------| | Tri rapide | O(n log n) | O(n log n)| O(n²) | O(log n)| Non | | Tri fusion | O(n log n) | O(n log n)| O(n log n)| O(n) | Oui | | Tri par tas| O(n log n) | O(n log n)| O(n log n)| O(1) | Non | | Tri par insertion | O(n) | O(n²) | O(n²) | O(1) | Oui |

Le tri rapide est souvent préféré dans la pratique en raison de ses performances moyennes excellentes et de son efficacité en place.