Tri rapide

#Tri rapide (Quicksort)Copier le lien

Le tri rapide (quicksort) est un algorithme de tri efficace basé sur le principe de "diviser pour régner". C'est l'un des algorithmes de tri les plus utilisés en pratique en raison de son excellente performance moyenne.

#Principe de l'algorithmeCopier le lien

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 interactiveCopier le lien

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

#Implémentation en PythonCopier le lien

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éCopier le lien

• 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
• Espace : O(log n) - Espace auxiliaire pour la récursion

#OptimisationsCopier le lien

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

#VariantesCopier le lien

• 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

#Exercice : Implémentation du tri rapide avec choix de pivot médiane de troisCopier le lien

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

#InstructionsCopier le lien

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 codeCopier le lien

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 algorithmesCopier le lien

| 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.