Le tri rapide (Quicksort) en Python pas a pas

Qu'est-ce que le tri rapide (Quicksort) ?

Le tri rapide, ou Quicksort, est l'un des algorithmes de tri les plus célèbres et les plus efficaces. Inventé par Tony Hoare en 1959, il repose sur une stratégie de type « diviser pour régner » (divide and conquer). Son principe est simple mais puissant : choisir un élément (appelé pivot), partitionner la liste autour de ce pivot pour que tous les éléments plus petits soient à gauche et les plus grands à droite, puis appliquer récursivement le même traitement aux deux sous-listes créées.

En NSI, comprendre Quicksort est essentiel. Il illustre parfaitement des concepts clés comme la récursivité, la complexité algorithmique et l'importance du choix d'un bon pivot. Contrairement à des algorithmes plus simples comme le tri par sélection ou par insertion, Quicksort est souvent utilisé dans la pratique pour sa rapidité sur de grands ensembles de données.

Le principe de l'algorithme pas à pas

Voyons comment fonctionne Quicksort sur un exemple concret. Prenons la liste : [10, 80, 30, 90, 40, 50, 70].

Les étapes sont les suivantes :

1. Choix du pivot : On choisit un élément. Souvent, c'est le dernier (ici, 70).
2. Partitionnement : On réorganise la liste pour que :
   • Tous les éléments inférieurs au pivot soient à sa gauche.
   • Tous les éléments supérieurs ou égaux au pivot soient à sa droite.
   Après partitionnement autour de 70, on pourrait obtenir : [10, 30, 40, 50, 70, 90, 80]. Le pivot (70) est maintenant à sa position finale, triée.
3. Récursion : On applique récursivement les étapes 1 et 2 aux deux sous-listes :
   • Sous-liste gauche (éléments < pivot) : [10, 30, 40, 50]
   • Sous-liste droite (éléments > pivot) : [90, 80]
   On recommence jusqu'à ce que les sous-listes aient 0 ou 1 élément (cas de base de la récursion).

La magie de Quicksort réside dans ce partitionnement qui place le pivot à sa bonne place à chaque étape.

Implémentation en Python : du pseudo-code au code fonctionnel

Passons maintenant à la pratique avec une implémentation classique en Python. Nous allons d'abord écrire la fonction de partition, puis la fonction principale quicksort.

La fonction de partitionnement

Cette fonction est le cœur de l'algorithme. Elle prend une liste, un indice de début (low) et un indice de fin (high), choisit un pivot (ici le dernier élément), et réorganise la liste.

def partition(liste, low, high):
    # Choisir le pivot (dernier élément)
    pivot = liste[high]
    # Indice du plus petit élément, indique la position correcte du pivot
    i = low - 1
    
    for j in range(low, high):
        # Si l'élément courant est plus petit que le pivot
        if liste[j] <= pivot:
            i += 1  # Incrémenter l'index du plus petit élément
            liste[i], liste[j] = liste[j], liste[i]  # Échanger
    
    # Placer le pivot à sa position correcte (entre les éléments < et >)
    liste[i + 1], liste[high] = liste[high], liste[i + 1]
    return i + 1  # Retourne l'indice de la position du pivot

La fonction Quicksort récursive

Maintenant, la fonction principale qui appelle récursivement partition et s'appelle elle-même.

def quicksort(liste, low=0, high=None):
    if high is None:
        high = len(liste) - 1
    
    if low < high:
        # pi est l'indice de partition, liste[pi] est à la bonne place
        pi = partition(liste, low, high)
        
        # Trier récursivement les éléments avant et après la partition
        quicksort(liste, low, pi - 1)   # Sous-liste gauche
        quicksort(liste, pi + 1, high)  # Sous-liste droite
    return liste

Tu peux tester avec : print(quicksort([10, 80, 30, 90, 40, 50, 70])). Le résultat sera la liste triée : [10, 30, 40, 50, 70, 80, 90].

Complexité et performances : pourquoi "rapide" ?

Le nom "tri rapide" n'est pas volé ! Sa performance est généralement excellente :

• Complexité dans le cas moyen : O(n log n). C'est la même que pour le tri fusion (Mergesort), mais Quicksort est souvent plus rapice en pratique car les opérations sont simples et il utilise peu de mémoire supplémentaire.
• Complexité dans le pire des cas : O(n²). Cela arrive si le pivot choisi est systématiquement le plus petit ou le plus grand élément (par exemple, trier une liste déjà triée avec le dernier élément comme pivot).
• Complexité en espace : O(log n) en moyenne pour la pile d'appels récursifs.

Comment éviter le pire cas ? La clé est le choix du pivot. Des stratégies existent :

• Pivot aléatoire : Choisir un élément au hasard.
• Médiane de trois : Prendre le premier, le milieu et le dernier élément, et choisir la médiane.

Ces techniques rendent le pire cas extrêmement improbable.

Quicksort en pratique : avantages, inconvénients et variantes

Quand utiliser Quicksort ? Comparons-le à d'autres algorithmes vus en NSI.

Avantages :

• Très rapide en pratique sur la plupart des données.
• Tri en place : il ne nécessite qu'un espace mémoire supplémentaire très faible (contrairement au tri fusion qui a besoin d'un tableau auxiliaire).
• Cache-friendly : son fonctionnement séquentiel est efficace pour le cache du processeur.

Inconvénients :

• Non stable : deux éléments égaux peuvent voir leur ordre relatif modifié. Si la stabilité est importante (tri de données complexes), préfère le tri fusion.
• Performance dégradée dans le pire cas (mais évitable).
• Récursif : peut causer un débordement de pile sur de très grandes listes (une version itérative existe).

Variantes intéressantes :

• Dual-Pivot Quicksort : Utilise deux pivots au lieu d'un. C'est l'algorithme utilisé par défaut pour trier les tableaux de primitifs en Java ! Il est souvent encore plus performant.
• Introsort : Un hybride qui commence avec Quicksort et bascule sur le tri par tas (Heapsort) si la récursion devient trop profonde, garantissant ainsi une complexité O(n log n).

Pour tes projets NSI, implémenter Quicksort est un excellent exercice. Tu peux ensuite le comparer expérimentalement avec d'autres algorithmes en mesurant le temps d'exécution sur des listes de tailles différentes.