Maîtriser Quicksort : La Partition Expliquée

1. Le Principe du Tri Rapide

La stratégie du tri rapide se décompose comme suit :

1. Diviser : C'est l'étape de partitionnement. On choisit un élément du tableau, le pivot. On réorganise ensuite le tableau (ou le sous-tableau) de sorte que tous les éléments inférieurs ou égaux au pivot se retrouvent à sa gauche, et tous les éléments supérieurs se retrouvent à sa droite. À la fin de cette étape, le pivot est à sa position définitive dans le tableau trié.
2. Régner : On applique récursivement le tri rapide sur les deux sous-tableaux : celui à gauche du pivot et celui à sa droite.
3. Combiner : Aucune action n'est nécessaire. Comme les sous-tableaux sont triés "en place" et que le pivot est déjà bien positionné, le tableau entier se retrouve trié une fois que les appels récursifs se terminent.

L'intelligence de l'algorithme réside entièrement dans la procédure de partitionnement. La fonction de tri rapide n'est en fait qu'un "pilote" (driver) qui orchestre les appels à cette fonction de partitionnement.

Pour bien saisir cette abstraction, je vous invite à regarder l'introduction de la vidéo suivante.

2. L'algorithme de partition de Lomuto

Il existe plusieurs manières de réaliser le partitionnement. La plus simple à comprendre et à implémenter est celle proposée par Nico Lomuto. Elle est souvent enseignée en premier.

Principe de la partition de Lomuto :

1. Choix du pivot : On choisit un pivot. Pour la simplicité de l'algorithme, on choisit souvent le dernier élément du sous-tableau.
2. Parcours et échange : On maintient un indice i qui marque la frontière de la zone des éléments plus petits que le pivot. On parcourt le tableau avec un autre indice j.
   • Au début, i est juste avant le début du sous-tableau.
   • Pour chaque élément A[j], si A[j] est inférieur ou égal au pivot, on incrémente i et on échange A[i] avec A[j].
3. Placement final du pivot : Une fois le parcours terminé, tous les éléments jusqu'à l'indice i sont plus petits que le pivot. On échange alors l'élément en A[i+1] avec le pivot (qui était au début à la fin du tableau). Le pivot est maintenant à sa place définitive, à l'indice i+1.

L'image suivante, inspirée du livre de référence de Cormen et al., illustre parfaitement ce processus.

Pour voir cet algorithme en action, la vidéo suivante propose une excellente démonstration visuelle.

3. Implémentation en Python (avec partition de Lomuto)

Maintenant, mettons cela en pratique. Le code ci-dessous structure l'algorithme en trois fonctions, comme il est courant de le faire pour plus de clarté :

1. partition(arr, low, high) : Implémente le schéma de Lomuto.
2. quick_sort_recursive(arr, low, high) : Le pilote récursif.
3. quick_sort(arr) : La fonction principale que l'utilisateur appelle.

def partition(arr, low, high):
    """
    Partitionne le sous-tableau arr[low..high] en utilisant le dernier élément comme pivot.
    Retourne l'index final du pivot.
    """



    # On choisit le dernier élément comme pivot
    pivot = arr[high]
    



    # i est l'index du dernier élément plus petit que le pivot trouvé
    i = low - 1
    
    for j in range(low, high):



        # Si l'élément courant est plus petit ou égal au pivot
        if arr[j] <= pivot:



            # On incrémente i et on échange arr[i] et arr[j]
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
            



    # Le pivot doit être placé après le dernier élément plus petit que lui.
    # On échange donc arr[i+1] avec le pivot (arr[high])
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    



    # On retourne l'index où se trouve maintenant le pivot
    return i + 1

def quick_sort_recursive(arr, low, high):
    """
    La fonction récursive qui pilote le tri rapide.
    """
    if low < high:



        # pi est l'index de partitionnement, arr[pi] est maintenant à sa place.
        pi = partition(arr, low, high)
        



        # Trie récursivement les éléments avant et après la partition
        quick_sort_recursive(arr, low, pi - 1)
        quick_sort_recursive(arr, pi + 1, high)

def quick_sort(arr):
    """
    Fonction principale pour appeler le tri rapide.
    """
    quick_sort_recursive(arr, 0, len(arr) - 1)




# Exemple d'utilisation
my_array = [10, 7, 8, 9, 1, 5]
quick_sort(my_array)
print("Tableau trié:", my_array)  # Devrait afficher [1, 5, 7, 8, 9, 10]

Le choix du pivot

Choisir systématiquement le dernier élément comme pivot peut être problématique. Si le tableau est déjà trié ou trié en ordre inverse, le partitionnement sera déséquilibré (un sous-tableau de taille 0 et un de taille n-1), menant à une complexité en $\Theta (n^2)$.

Une stratégie simple et très efficace en pratique pour éviter ce cas est de choisir un pivot aléatoire. On choisit un indice au hasard dans le sous-tableau, on échange cet élément avec le dernier, puis on exécute l'algorithme de Lomuto normalement.

import random

def random_partition(arr, low, high):



    # Choisir un index de pivot aléatoire
    rand_pivot_index = random.randrange(low, high + 1)
    



    # Échanger avec le dernier élément pour utiliser l'implémentation de Lomuto
    arr[rand_pivot_index], arr[high] = arr[high], arr[rand_pivot_index]
    



    # Appeler la partition de Lomuto standard
    return partition(arr, low, high)




# La fonction quick_sort_recursive devrait alors appeler random_partition
# au lieu de partition.

4. L'algorithme de partition de Hoare

La partition de Hoare est le schéma original, historiquement le premier. Il est légèrement plus complexe, mais souvent plus performant en pratique car il effectue moins d'échanges.

Principe de la partition de Hoare :

1. Choix du pivot : On choisit un pivot (par exemple, le premier élément).
2. Pointeurs convergents : On utilise deux pointeurs, i partant du début et j partant de la fin du sous-tableau.
   • On avance i tant que arr[i] < pivot.
   • On recule j tant que arr[j] > pivot.
3. Échange : Si i < j, cela signifie qu'on a trouvé un élément trop grand à gauche (arr[i]) et un élément trop petit à droite (arr[j]). On les échange.
4. Répétition : On répète le processus jusqu'à ce que les pointeurs i et j se croisent (i >= j).

Attention, une subtilité cruciale :
Contrairement à Lomuto, la partition de Hoare ne garantit pas que le pivot se trouve à l'indice retourné. Elle garantit seulement que tous les éléments à gauche de cet indice sont $\le$ au pivot, et tous ceux à droite sont $\ge$ au pivot. L'index retourné est le point de "cassure". Par conséquent, les appels récursifs doivent inclure cet indice : quick_sort(arr, low, j) et quick_sort(arr, i, high).

Le document suivant, destiné à des étudiants préparant les concours, décrit les deux méthodes.

Exercice Pratique

1. Implémentation : Reprenez le code Python fourni pour le tri rapide avec la partition de Lomuto. Assurez-vous de bien le comprendre et de pouvoir le réécrire de mémoire.
2. Amélioration : Modifiez votre implémentation pour utiliser un pivot aléatoire. Testez-la sur différents tableaux (triés, inversés, aléatoires).
3. Défi (pour aller plus loin) : Implémentez la fonction de partitionnement de Hoare. Intégrez-la dans le pilote récursif en faisant bien attention aux indices des appels récursifs, qui diffèrent de ceux utilisés avec Lomuto. C'est un excellent exercice pour vérifier votre compréhension fine des algorithmes.

Conclusion

Le tri rapide est un algorithme puissant et largement utilisé. Son efficacité dépend entièrement de la qualité de sa fonction de partitionnement.

À retenir :

• Le tri rapide est un algorithme diviser pour régner où le travail se concentre sur l'étape de partition.
• Le schéma de Lomuto est simple : il construit une partition d'éléments plus petits que le pivot et place ce dernier à sa position finale.
• Le schéma de Hoare est l'original : il utilise deux pointeurs convergents et est souvent plus rapide, mais sa gestion des indices est plus subtile.
• Le choix du pivot est critique pour éviter le pire cas en $\Theta (n^2)$. Un pivot aléatoire est une stratégie robuste.

Dans la prochaine leçon, nous analyserons formellement la complexité du tri rapide. Nous verrons pourquoi, malgré un pire cas en $\Theta (n^2)$, sa complexité moyenne en $\Theta (n\log n)$ et ses bonnes performances en pratique en font un choix si populaire.