Les 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.

L'objectif de ce chapitre est d'atteindre une complexité bien meilleure, \(O(n \log n)\). Reprenons d'abord en détail les deux tris simples les plus utilisés.

1.1 Le tri par sélection

Principe. À l'étape \(i\), on cherche le minimum de la partie non triée \(t[i..n-1]\) et on l'échange avec \(t[i]\). La partie gauche grandit d'une case à chaque étape jusqu'à ce que tout le tableau soit trié.

Exemple de déroulement sur le tableau \(t = [29,\ 10,\ 14,\ 37,\ 13]\). À chaque passe, le minimum de la zone non triée (en gras) est amené en tête de cette zone :

Implémentation (en place). Une seule application directe du principe :

def tri_selection(t):
    n = len(t)
    for i in range(n - 1):
        imin = i
        for j in range(i + 1, n):
            if t[j] < t[imin]:
                imin = j
        t[i], t[imin] = t[imin], t[i]   # échange le minimum en position i
    return t

1.2 Le tri par insertion

Principe. On parcourt le tableau de gauche à droite. À l'étape \(i\), l'élément \(t[i]\) est inséré à sa place dans la partie déjà triée \(t[0..i-1]\), en le décalant vers la gauche tant qu'il est plus petit que son voisin.

def tri_insertion(t):
    for i in range(1, len(t)):
        cle = t[i]
        j = i - 1
        while j >= 0 and t[j] > cle:
            t[j + 1] = t[j]
            j -= 1
        t[j + 1] = cle
    return t

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 :

Pour voir la différence, ajoutons une étiquette à chaque valeur et trions selon la valeur uniquement. Partons de \([\,(3,a),\ (3,c),\ (2,b)\,]\) (l'étiquette \(a\) est avant \(c\) au départ) :

Pourquoi le tri par sélection casse l'ordre ici : à la première passe, le minimum \(2\) (étiquette \(b\), en position 2) est échangé avec la position 0, occupée par \((3,a)\). Cet échange envoie \((3,a)\) après \((3,c)\), détruisant leur ordre initial. C'est le mécanisme d'échange « à distance » qui rend le tri par sélection non stable.

Application concrète : 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.

Illustration graphique (arbre d'appels) sur \([3,\ 8,\ 1,\ 5,\ 2]\), pivot = premier élément. Chaque nœud montre la liste reçue ; le pivot est en rouge, et les flèches mènent aux sous-listes « \(\leq\) pivot » (gauche) et « \(>\) pivot » (droite). On remonte ensuite en concaténant gauche + pivot + 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)

L'étape de partition d'une liste de taille \(n\) parcourt les \(n-1\) autres éléments : son coût est \(\Theta(n)\). Notons \(T(n)\) le coût total du tri. Détaillons les deux cas extrêmes.

En moyenne (pivot quelconque), on démontre que le coût reste \(\Theta(n \log n)\) : le pire cas est rare dès que le pivot est bien choisi.

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.

Illustration graphique (arbre de division puis de fusion) sur \([3,\ 8,\ 1,\ 5,\ 2]\). On descend en coupant en deux jusqu'aux singletons, puis on remonte en fusionnant :

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)

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

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