Définition — Tri rapide Le tri rapide (Quicksort) est un algorithme de tri basé sur le paradigme Diviser pour régner, proposé par C.A.R. Hoare en 1959. C'est l'un des algorithmes de tri les plus utilisés en pratique grâce à ses excellentes performances en moyenne.

Principe : choisir un élément appelé pivot, puis partitionner le tableau en deux parties — les éléments inférieurs au pivot à gauche, les supérieurs à droite — et trier récursivement chaque partie.

Les trois étapes — Diviser pour régner

Choisir un pivot — sélectionner un élément p = T[k] (souvent le dernier, le premier, ou un élément médian).
Partitionner— réarranger le tableau tel que :
- Tous les éléments ≤ p sont à gauche du pivot.
- Tous les éléments ≥ p sont à droite du pivot.
- Le pivot est à sa position finale définitive.
Récursion — appliquer récursivement le tri sur les deux sous-tableaux.

Illustration — Arbre de récursion

Exemple — Tri de [8, 3, 1, 5, 9, 2, 7, 4, 6] (pivot = dernier élément)

Étape 1 : pivot = 6
  [3, 1, 5, 2, 4] | [6] | [8, 9, 7]
         ↙                    ↘
Étape 2a : pivot = 4       Étape 2b : pivot = 7
  [3, 1, 2] | [4] | [5]      [8, 9] | [7] | []
       ↙                          ↙
Étape 3 : pivot = 2          Étape 3b : pivot = 9
  [1] | [2] | [3]              [8] | [9] | []

Résultat final (fusion des sous-tableaux triés) :
  [1, 2, 3, 4, 5, 6, 7, 8, 9]

Différence clé avec le tri par fusion

Critère	Tri rapide	Tri par fusion
Division	Déséquilibrée selon le pivot	Toujours en deux moitiés égales
Travail principal	À la division (partition)	À la combinaison (fusion)
Espace suppl.	O(log n) pile d'appels	O(n) tableaux temporaires
Pire cas	O(n²)	O(n log n)

Fonction partition — le cœur de l'algorithme

La partition (schéma de Lomuto) place le pivot à sa position finale et réarrange les autres éléments. Elle utilise deux indices :

i — frontière de la zone des éléments ≤ pivot (initialement debut − 1).
j — curseur de parcours de debut à fin − 1.

Pseudocode — partition (schéma de Lomuto)

fonction partition(T, debut, fin) :
    pivot ← T[fin]          ← choisir le dernier élément comme pivot
    i     ← debut - 1

    Pour j de debut à fin - 1 :
        Si T[j] ≤ pivot alors
            i ← i + 1
            échanger T[i] et T[j]

    échanger T[i+1] et T[fin]   ← mettre le pivot à sa place finale
    retourner i + 1              ← retourner la position du pivot

Trace de partition — T = [3, 6, 8, 10, 1, 2, 1], pivot = T[6] = 1

j	T[j]	T[j] ≤ pivot ?	i	Tableau après
init	—	—	-1	`[3, 6, 8, 10, 1, 2, 1]`
0	3	Non	-1	pas de changement
1	6	Non	-1	pas de changement
4	1	Oui (1 ≤ 1)	0	`[1, 6, 8, 10, 3, 2, 1]`
fin	—	swap pivot ↔ T[i+1]	1	`[1, 1, 8, 10, 3, 2, 6]`

Trace de partition — T = [10, 80, 30, 90, 40, 50, 70], pivot = T[6] = 70

j	T[j]	T[j] ≤ 70 ?	i	Action	Tableau
init	—	—	-1	—	`[10,80,30,90,40,50,70]`
0	10	Oui	0	swap T[0]↔T[0]	`[10,80,30,90,40,50,70]`
1	80	Non	0	—	inchangé
2	30	Oui	1	swap T[1]↔T[2]	`[10,30,80,90,40,50,70]`
3	90	Non	1	—	inchangé
4	40	Oui	2	swap T[2]↔T[4]	`[10,30,40,90,80,50,70]`
5	50	Oui	3	swap T[3]↔T[5]	`[10,30,40,50,80,90,70]`
fin	—	—	4	swap T[4]↔T[6] (pivot)	`[10,30,40,50,70,90,80]`

→ Pivot 70 est maintenant en position 4 (sa place définitive). Zone gauche [10,30,40,50] ≤ 70 ✓ — Zone droite [90,80] ≥ 70 ✓

Algorithme complet

Pseudocode — triRapide

fonction triRapide(T, debut, fin) :
    Si debut < fin alors
        p ← partition(T, debut, fin)   ← p = position finale du pivot
        triRapide(T, debut, p - 1)     ← trier la partie gauche
        triRapide(T, p + 1, fin)       ← trier la partie droite

    ← cas de base : sous-tableau vide ou de taille 1 → déjà trié

Implémentations

def partition(T, debut, fin):
    """
    Schéma de Lomuto : pivot = T[fin].
    Place le pivot à sa position finale et retourne cet index.
    """
    pivot = T[fin]
    i = debut - 1                    # frontière zone ≤ pivot

    for j in range(debut, fin):
        if T[j] <= pivot:
            i += 1
            T[i], T[j] = T[j], T[i] # échanger

    T[i + 1], T[fin] = T[fin], T[i + 1]  # placer le pivot
    return i + 1


def tri_rapide(T, debut=0, fin=None):
    """Tri rapide récursif en place — schéma de Lomuto."""
    if fin is None:
        fin = len(T) - 1
    if debut < fin:
        p = partition(T, debut, fin)
        tri_rapide(T, debut, p - 1)   # trier la partie gauche
        tri_rapide(T, p + 1, fin)     # trier la partie droite


# Affichage des étapes
def tri_rapide_verbose(T, debut=0, fin=None, niveau=0):
    if fin is None:
        fin = len(T) - 1
    indent = "  " * niveau
    if debut < fin:
        print(f"{indent}triRapide({T[debut:fin+1]}) pivot={T[fin]}")
        p = partition(T, debut, fin)
        print(f"{indent}→ après partition : {T[debut:fin+1]}, pivot à pos {p}")
        tri_rapide_verbose(T, debut, p - 1, niveau + 1)
        tri_rapide_verbose(T, p + 1, fin,   niveau + 1)


T = [10, 80, 30, 90, 40, 50, 70]
print("Avant :", T)
tri_rapide_verbose(T)
print("Après :", T)

def partition_hoare(T, debut, fin):
    """
    Schéma de Hoare : pivot = T[debut] (schéma original).
    Utilise deux pointeurs qui se rapprochent depuis les deux extrémités.
    Plus efficace que Lomuto : 3× moins d'échanges en moyenne.
    """
    pivot = T[debut]
    i = debut - 1
    j = fin + 1

    while True:
        i += 1
        while T[i] < pivot:
            i += 1
        j -= 1
        while T[j] > pivot:
            j -= 1
        if i >= j:
            return j          # retourne l'index de séparation (≠ Lomuto)
        T[i], T[j] = T[j], T[i]


def tri_rapide_hoare(T, debut=0, fin=None):
    """Tri rapide avec le schéma de partition de Hoare."""
    if fin is None:
        fin = len(T) - 1
    if debut < fin:
        p = partition_hoare(T, debut, fin)
        tri_rapide_hoare(T, debut, p)       # Note : p (pas p-1) avec Hoare
        tri_rapide_hoare(T, p + 1, fin)


# Pivot aléatoire (améliore le pire cas)
import random

def partition_aleatoire(T, debut, fin):
    """Choix aléatoire du pivot → évite le pire cas O(n²)."""
    k = random.randint(debut, fin)
    T[k], T[fin] = T[fin], T[k]   # échanger le pivot aléatoire avec T[fin]
    return partition(T, debut, fin)  # utiliser ensuite Lomuto


def tri_rapide_aleatoire(T, debut=0, fin=None):
    if fin is None:
        fin = len(T) - 1
    if debut < fin:
        p = partition_aleatoire(T, debut, fin)
        tri_rapide_aleatoire(T, debut, p - 1)
        tri_rapide_aleatoire(T, p + 1, fin)


# Test comparatif
import time

n = 5000
T1 = list(range(n))           # pire cas pour pivot = dernier
T2 = list(range(n))

start = time.time()
tri_rapide(T1, 0, n - 1)      # peut être lent sur tableau trié
print(f"Lomuto (trié) : {time.time()-start:.4f}s")

start = time.time()
tri_rapide_aleatoire(T2, 0, n - 1)
print(f"Pivot aléatoire (trié) : {time.time()-start:.4f}s")

#include <stdio.h>

void echanger(int *a, int *b) {
    int tmp = *a; *a = *b; *b = tmp;
}

int partition(int T[], int debut, int fin) {
    int pivot = T[fin];
    int i     = debut - 1;

    for (int j = debut; j < fin; j++) {
        if (T[j] <= pivot) {
            i++;
            echanger(&T[i], &T[j]);
        }
    }
    echanger(&T[i + 1], &T[fin]);
    return i + 1;
}

void tri_rapide(int T[], int debut, int fin) {
    if (debut < fin) {
        int p = partition(T, debut, fin);
        tri_rapide(T, debut, p - 1);
        tri_rapide(T, p + 1, fin);
    }
}

void afficher(int T[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", T[i]);
    printf("\n");
}

int main() {
    int T[] = {10, 80, 30, 90, 40, 50, 70};
    int n = 7;
    printf("Avant : "); afficher(T, n);
    tri_rapide(T, 0, n - 1);
    printf("Après : "); afficher(T, n);
    return 0;
}

import java.util.Arrays;

public class TriRapide {

    static int partition(int[] T, int debut, int fin) {
        int pivot = T[fin];
        int i     = debut - 1;

        for (int j = debut; j < fin; j++) {
            if (T[j] <= pivot) {
                i++;
                int tmp = T[i]; T[i] = T[j]; T[j] = tmp;
            }
        }
        int tmp = T[i+1]; T[i+1] = T[fin]; T[fin] = tmp;
        return i + 1;
    }

    static void triRapide(int[] T, int debut, int fin) {
        if (debut < fin) {
            int p = partition(T, debut, fin);
            triRapide(T, debut, p - 1);
            triRapide(T, p + 1, fin);
        }
    }

    public static void main(String[] args) {
        int[] T = {10, 80, 30, 90, 40, 50, 70};
        System.out.println("Avant : " + Arrays.toString(T));
        triRapide(T, 0, T.length - 1);
        System.out.println("Après : " + Arrays.toString(T));
    }
}

Sortie (Python verbose)

Avant : [10, 80, 30, 90, 40, 50, 70]
triRapide([10, 80, 30, 90, 40, 50, 70]) pivot=70
→ après partition : [10, 30, 40, 50, 70, 90, 80], pivot à pos 4
  triRapide([10, 30, 40, 50]) pivot=50
  → après partition : [10, 30, 40, 50], pivot à pos 3
    triRapide([10, 30, 40]) pivot=40
    → après partition : [10, 30, 40], pivot à pos 2
  triRapide([90, 80]) pivot=80
  → après partition : [80, 90], pivot à pos 5
Après : [10, 30, 40, 50, 70, 80, 90]

Analyse de la complexité

Complexité — Tri rapide

Cas	Situation	Récurrence	Complexité
Meilleur	Pivot = médiane exacte	\(T(n) = 2T(n/2) + \Theta(n)\)	O(n log n)
Moyen	Partitions proportionnelles	\(T(n) = T(n/10) + T(9n/10) + \Theta(n)\)	O(n log n)
Pire	Pivot = min ou max à chaque fois	\(T(n) = T(n-1) + \Theta(n)\)	O(n²)
Espace	Pile de récursion	—	O(log n) moy. / O(n) pire

Pire cas — Tableau déjà trié avec pivot = dernier Si le tableau est déjà trié (croissant ou décroissant) et qu'on choisit toujours le dernier élément comme pivot, la partition crée des sous-tableaux de taille 0 et n−1 à chaque étape → arbre de récursion dégénéré en liste → O(n²) comparaisons.

Solutions : choisir un pivot aléatoire, ou utiliser la stratégie médiane de trois (median-of-three).

Stratégies de choix du pivot

Comparaison des stratégies

Stratégie	Description	Avantage	Inconvénient
Dernier élément	`pivot = T[fin]`	Simple à implémenter	O(n²) sur tableau trié
Premier élément	`pivot = T[debut]`	Simple	O(n²) sur tableau trié/inversé
Pivot aléatoire	`k = random(debut, fin)`	Évite les cas dégénérés	Appel random() à chaque étape
Médiane de trois	Médiane de T[debut], T[milieu], T[fin]	Meilleure partition en pratique	Légèrement plus complexe

Implémentation — Médiane de trois

def mediane_de_trois(T, debut, fin):
    """
    Choisit le pivot comme la médiane de T[debut], T[milieu], T[fin].
    Place ce pivot en T[fin] pour utiliser ensuite partition() de Lomuto.
    """
    milieu = (debut + fin) // 2
    # Trier les trois candidats sur place
    if T[debut] > T[milieu]:
        T[debut], T[milieu] = T[milieu], T[debut]
    if T[debut] > T[fin]:
        T[debut], T[fin] = T[fin], T[debut]
    if T[milieu] > T[fin]:
        T[milieu], T[fin] = T[fin], T[milieu]
    # Maintenant T[debut] ≤ T[milieu] ≤ T[fin]
    # La médiane est T[milieu], on l'échange avec T[fin-1]
    T[milieu], T[fin] = T[fin], T[milieu]
    return T[fin]   # le pivot est maintenant en T[fin]


def tri_rapide_median3(T, debut=0, fin=None):
    if fin is None:
        fin = len(T) - 1
    if debut < fin:
        mediane_de_trois(T, debut, fin)
        p = partition(T, debut, fin)
        tri_rapide_median3(T, debut, p - 1)
        tri_rapide_median3(T, p + 1, fin)

Comparaison globale des algorithmes de tri

Algorithme	Meilleur	Moyen	Pire	Espace	Stable	En place
Tri rapide	O(n log n)	O(n log n)	O(n²)	O(log n)	❌	✅
Tri fusion	O(n log n)	O(n log n)	O(n log n)	O(n)	✅	❌
Tri tas	O(n log n)	O(n log n)	O(n log n)	O(1)	❌	✅
Tri insertion	O(n)	O(n²)	O(n²)	O(1)	✅	✅
Tri bulles	O(n)	O(n²)	O(n²)	O(1)	✅	✅
Tri sélection	O(n²)	O(n²)	O(n²)	O(1)	❌	✅

Points clés à retenir

Le tri rapide est en place (O(log n) espace pour la pile) contrairement au tri fusion (O(n)).
Son pire cas O(n²) survient quand le pivot est systématiquement le minimum ou le maximum — typiquement sur un tableau déjà trié avec pivot = T[fin].
Utiliser un pivot aléatoire ou la médiane de trois garantit O(n log n) en pratique.
Le schéma de Hoare est environ 3× plus efficace en échanges que Lomuto, mais plus complexe à implémenter correctement.
En pratique, le tri rapide est souvent plus rapide que le tri fusion grâce à une meilleure localité de cache, malgré la même complexité asymptotique.
En Python, sorted() utilise Timsort (hybride insertion + fusion), pas le tri rapide.

Sortie

// La sortie apparaîtra ici…

Prêt · Ctrl+Entrée pour exécuter

Algorithme de tri rapide

Tri rapide — Quicksort

Illustration — Arbre de récursion

Fonction partition — le cœur de l'algorithme

Algorithme complet

Implémentations

Analyse de la complexité

Stratégies de choix du pivot

Comparaison globale des algorithmes de tri

Discussion (0)

Laisser un commentaire

Structures de données

Algorithmes

Programmation

Bases de données

CPGE

Modules informatique

Algorithme de tri rapide

Tri rapide — Quicksort

Illustration — Arbre de récursion

Fonction partition — le cœur de l'algorithme

Algorithme complet

Implémentations

Analyse de la complexité

Stratégies de choix du pivot

Comparaison globale des algorithmes de tri

Discussion (0)

Laisser un commentaire