CPGE 2ᵉ année — MP / PSI · Informatique

Les algorithmes de tri

Pr. EL HADIQ Zouhair

Au-delà des tris simples vus en première année, deux méthodes efficaces fondées sur « diviser pour régner » : le tri rapide et le tri par fusion.

🎯 Objectifs du chapitre
Sommaire
  1. Rappels : les tris simples de première année
  2. Deux propriétés clés : tri en place et stabilité
  3. Le tri rapide (quicksort)
  4. Le tri par fusion (merge sort)
  5. Comparaison des algorithmes de tri

1. Rappels : les tris simples de première année

En première année, trois tris ont été étudiés. Tous ont une complexité quadratique \(O(n^2)\) dans le pire des cas, ce qui les rend lents sur de grandes listes.

Tri Principe Complexité (pire cas)
Sélection Chercher le minimum et le placer en tête, puis recommencer sur le reste. \(O(n^2)\)
Insertion Insérer chaque élément à sa place dans la partie déjà triée. \(O(n^2)\)
À bulles Échanger les éléments adjacents mal ordonnés, en plusieurs passes. \(O(n^2)\)

Le tri par sélection, par exemple, effectue \((n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}\) comparaisons, soit \(O(n^2)\). L'objectif de ce chapitre est d'atteindre une complexité bien meilleure, \(O(n \log n)\).

2. Deux propriétés clés : tri en place et stabilité

Pour caractériser un algorithme de tri, deux propriétés sont importantes :

Tri en place. Un tri est en place s'il n'utilise qu'une quantité de mémoire supplémentaire constante \(O(1)\), en réorganisant les éléments à l'intérieur du tableau d'origine (sans créer de copie de taille n).
Stabilité. Un tri est stable s'il conserve l'ordre relatif initial des éléments ayant une clé égale. Utile lorsqu'on trie selon plusieurs critères successifs.

Exemple de stabilité : on trie une liste de personnes déjà triées par prénom, cette fois par âge. Un tri stable garde, parmi les personnes de même âge, l'ordre alphabétique acquis précédemment ; un tri non stable peut le détruire.

3. Le tri rapide (quicksort)

Principe (diviser pour régner). On choisit un élément appelé pivot. On réorganise la liste (étape de partition) de sorte que les éléments plus petits que le pivot soient à sa gauche et les plus grands à sa droite. Le pivot est alors à sa place définitive. On applique ensuite récursivement le même procédé aux deux sous-listes gauche et droite.

Une implémentation simple et lisible (non en place, qui construit deux sous-listes) :

def tri_rapide(L):
    if len(L) <= 1:
        return L
    pivot = L[0]
    petits = [x for x in L[1:] if x <= pivot]
    grands = [x for x in L[1:] if x > pivot]
    return tri_rapide(petits) + [pivot] + tri_rapide(grands)
Complexité. En moyenne, la partition équilibre les deux côtés et l'on obtient T(n) = 2 T(n/2) + \(O(n)\), soit \(O(n \log n)\). Dans le pire des cas (pivot toujours minimal ou maximal, par exemple sur une liste déjà triée avec ce choix de pivot), une seule sous-liste est non vide à chaque étape : T(n) = T(n-1) + \(O(n)\), soit \(O(n^2)\).
Choix du pivot. Prendre systématiquement le premier élément rend le pire cas fréquent (listes déjà triées). On préfère un pivot aléatoire, ou la médiane de trois (premier, milieu, dernier), pour rendre le pire cas très improbable et garantir \(O(n \log n)\) en pratique.

Le tri rapide « classique » (avec partition à l'intérieur du tableau) est en place (\(O(1)\) d'espace auxiliaire, hormis la pile de récursion) mais non stable.

4. Le tri par fusion (merge sort)

Principe (diviser pour régner). On coupe la liste en deux moitiés, on trie récursivement chacune, puis on fusionne les deux moitiés triées en une seule liste triée. La fusion parcourt les deux listes en parallèle et choisit à chaque étape le plus petit élément de tête.

L'étape de fusion de deux listes déjà triées :

def fusion(A, B):
    C = []
    i, j = 0, 0
    while i < len(A) and j < len(B):
        if A[i] <= B[j]:
            C.append(A[i]); i += 1
        else:
            C.append(B[j]); j += 1
    return C + A[i:] + B[j:]

Le tri par fusion lui-même :

def tri_fusion(L):
    if len(L) <= 1:
        return L
    m = len(L) // 2
    gauche = tri_fusion(L[:m])
    droite = tri_fusion(L[m:])
    return fusion(gauche, droite)
Complexité. La liste est divisée en deux à chaque niveau (log2 n niveaux) et la fusion d'un niveau coûte \(O(n)\). On a T(n) = 2 T(n/2) + \(O(n)\), soit \(O(n \log n)\) garanti, y compris dans le pire des cas — contrairement au tri rapide.

En contrepartie, le tri par fusion n'est pas en place : il nécessite \(O(n)\) de mémoire supplémentaire pour les listes fusionnées. Il est en revanche stable (à condition d'utiliser <= dans la fusion).

5. Comparaison des algorithmes de tri

Tri Moyenne Pire cas En place Stable
Sélection \(O(n^2)\) \(O(n^2)\) Oui Non
Insertion \(O(n^2)\) \(O(n^2)\) Oui Oui
Tri rapide \(O(n \log n)\) \(O(n^2)\) Oui Non
Tri fusion \(O(n \log n)\) \(O(n \log n)\) Non Oui
✅ Points essentiels.

CPGE MP/PSI — Informatique · Chapitre : Les algorithmes de tri · Conforme au programme officiel 2023