Tri rapide

9.1 Définition du tri rapide

Le Tri rapide (Quick Sort) est un algorithme de tri efficace qui utilise l'approche "diviser pour régner". Il fonctionne en choisissant un pivot, divisant le tableau en deux sous-tableaux - les éléments inférieurs au pivot et les éléments supérieurs au pivot, puis applique le même processus de manière récursive à chaque sous-tableau.

L'algorithme du tri rapide est apparu comme une tentative de résoudre le problème de "comment déplacer rapidement vers la gauche les petits éléments et vers la droite les grands". Supposons que nous ayons l'élément le plus petit à l'extrême droite, peut-on le déplacer rapidement, sinon à sa position finale, du moins près d'elle ? Cela réduirait considérablement le nombre de comparaisons inutiles.

Principe de fonctionnement :

1. Choix du pivot :

Nous choisissons un élément du tableau comme pivot. Cela peut être le premier élément, le dernier élément, l'élément du milieu ou un élément aléatoire. Parfois, c'est la moyenne de trois éléments aléatoires.

2. Partitionnement :

Nous déplaçons tous les éléments inférieurs au pivot vers la partie gauche du tableau, et tous les éléments supérieurs au pivot vers la partie droite. En conséquence, le pivot se retrouve à sa place finale dans le tableau trié.

3. Application récursive :

Nous appliquons le processus de manière récursive aux sous-tableaux gauches et droits, en n'incluant pas le pivot.

Processus étape par étape

1. Choisir le pivot.
2. Déplacer les éléments inférieurs au pivot à gauche et les éléments supérieurs à droite.
3. Appliquer le processus de manière récursive aux sous-tableaux.

Complexité temporelle et spatiale du tri rapide

Complexité temporelle :

• Dans le pire des cas : O(n^2) — se produit lorsque le pire pivot est choisi à chaque fois (par exemple, quand le tableau est déjà trié).
• En moyenne : O(n log n) — pour des données réparties aléatoirement.
• Dans le meilleur des cas : O(n log n) — lorsque le tableau est divisé en parties égales à chaque fois.

Complexité spatiale :

O(log n) — nécessaire pour stocker la pile d'appels de la récursion, si la récursion terminale est utilisée et que les pivots sont choisis judicieusement.

9.2 Implémentation de l'algorithme de tri rapide

Implémentation en Python :

def quick_sort(arr):
    if len(arr) <= 1:
        return arr  # Cas de base : tableau avec 0 ou 1 élément déjà trié
    
    pivot = arr[len(arr) // 2]  # Choisir le pivot
    left = [x for x in arr if x < pivot]  # Éléments inférieurs au pivot
    middle = [x for x in arr if x == pivot]  # Éléments égaux au pivot
    right = [x for x in arr if x > pivot]  # Éléments supérieurs au pivot
    
    return quick_sort(left) + middle + quick_sort(right)

# Exemple d'utilisation :
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("Tableau trié :", sorted_arr)
# Output : Tableau trié : [1, 1, 2, 3, 6, 8, 10]

Exemple de fonctionnement de l'algorithme

Considérons un tableau : [3, 6, 8, 10, 1, 2, 1]

Premier passage :

• Pivot : 8
• Éléments à gauche : [3, 6, 1, 2, 1]
• Éléments au milieu : [8]
• Éléments à droite : [10]

Tri récursif de la partie gauche [3, 6, 1, 2, 1] :

• Pivot : 1
• Éléments à gauche : []
• Éléments au milieu : [1, 1]
• Éléments à droite : [3, 6, 2]

Tri récursif de la partie droite [3, 6, 2] :

• Pivot : 6
• Éléments à gauche : [3, 2]
• Éléments au milieu : [6]
• Éléments à droite : []

Tri récursif de la partie gauche [3, 2] :

• Pivot : 2
• Éléments à gauche : []
• Éléments au milieu : [2]
• Éléments à droite : [3]

Résultat de la fusion : [1, 1, 2, 3, 6] pour la partie gauche, [10] pour la partie droite, et [8] pour le milieu.

Tableau trié final : [1, 1, 2, 3, 6, 8, 10]