Analyse des tris efficaces

A. Le tri par fusion

Le tri par fusion repose sur une fonction récursive tri_fusion et une fonction auxiliaire itérative fusion. On analyse d'abord la fusion (boucle → invariant + variant), puis le tri lui-même (récursion → mesure + récurrence).

A.1 — La fonction fusion : spécification

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:]

A.2 — Correction de fusion : invariant de boucle

Initialisation. Avant le premier tour, \(C = [\,]\) et \(i = j = 0\). \((I_1)\) et \((I_2)\) sont vraies (\(C\) vide, \(A[0{:}0] = B[0{:}0] = [\,]\)) ; \((I_3)\) est vraie car \(C\) n'a aucun élément. ✓

Conservation. Supposons \(I\) vrai et la condition de boucle vraie (\(i < \operatorname{len}(A)\) et \(j < \operatorname{len}(B)\)). On ajoute \(m = \min(A[i], B[j])\) à \(C\) et on avance le compteur correspondant. Par \((I_3)\), tout élément de \(C\) est \(\le A[i]\) et \(\le B[j]\), donc \(\le m\) : \(C\) reste triée et \(m\) est bien placé en fin \((I_1)\). On a consommé un élément de plus de \(A\) ou de \(B\), donc \((I_2)\) reste vrai. Comme \(A\) et \(B\) sont triées, le nouveau \(A[i]\) (ou \(B[j]\)) est \(\ge m \ge\) tous les éléments de \(C\) : \((I_3)\) est rétabli. ✓

Sortie. À la fin de la boucle, \(i = \operatorname{len}(A)\) ou \(j = \operatorname{len}(B)\) : l'une des deux listes est entièrement consommée. On renvoie C + A[i:] + B[j:]. Par \((I_2)\), \(C\) contient \(A[0{:}i]\) et \(B[0{:}j]\) ; on lui ajoute le reste (\(A[i{:}]\) ou \(B[j{:}]\), l'autre étant vide). Par \((I_3)\) et le tri de \(A, B\), ce reste est trié et tous ses éléments sont \(\ge\) ceux de \(C\). Le résultat est donc trié et contient exactement les éléments de \(A\) et \(B\) : la postcondition est satisfaite. ✓

A.3 — Terminaison de fusion : variant de boucle

À chaque tour, on incrémente \(i\) ou \(j\) de \(1\) (jamais les deux), donc \(V\) décroît strictement de \(1\). De plus, tant que la boucle s'exécute, \(i < \operatorname{len}(A)\) et \(j < \operatorname{len}(B)\), donc \(V \ge 1 > 0\). Par le théorème de terminaison de Floyd (une suite d'entiers naturels strictement décroissante est finie, car \((\mathbb{N}, <)\) est bien fondé), la boucle effectue un nombre fini de tours. ✓

Le nombre de tours est au plus \(\operatorname{len}(A) + \operatorname{len}(B)\) : la fusion de deux listes de tailles \(m\) et \(p\) est en \(O(m + p)\).

A.4 — Terminaison de tri_fusion : fonction de mesure

def tri_fusion(L):
    if len(L) <= 1:
        return L
    m = len(L) // 2
    return fusion(tri_fusion(L[:m]), tri_fusion(L[m:]))

Pour une liste de longueur \(n \ge 2\), avec \(m = \lfloor n/2 \rfloor\), les appels récursifs portent sur \(L[{:}m]\) et \(L[m{:}]\) de longueurs \(\lfloor n/2 \rfloor\) et \(\lceil n/2 \rceil\). Comme \(n \ge 2\), on a \(\lfloor n/2 \rfloor < n\) et \(\lceil n/2 \rceil \le n - 1 < n\) : la mesure décroît strictement à chaque appel. Comme \(\mathbb{N}\) est bien fondé, on atteint le cas de base en un nombre fini d'étapes : tri_fusion termine. (La fonction fusion termine d'après A.3.) ✓

A.5 — Correction de tri_fusion : récurrence bien fondée

On raisonne par récurrence forte sur la mesure \(\mu(L) = \operatorname{len}(L)\) (récurrence bien fondée sur \((\mathbb{N}, <)\)).

Cas de base (\(\operatorname{len}(L) \le 1\)). Une liste vide ou à un élément est déjà triée ; elle est renvoyée telle quelle. \(P(L)\) est vraie. ✓

Hérédité. Soit \(n \ge 2\) ; supposons \(P\) vraie pour toute liste de longueur \(< n\). Pour \(L\) de longueur \(n\) : par hypothèse de récurrence (longueurs \(< n\)), tri_fusion(L[:m]) et tri_fusion(L[m:]) renvoient des permutations triées de \(L[{:}m]\) et \(L[m{:}]\). Par la correction de fusion (A.2), fusion(gauche, droite) renvoie une liste triée contenant exactement les éléments de gauche et droite, c'est-à-dire de \(L[{:}m]\) et \(L[m{:}]\), soit exactement les éléments de \(L\). Donc \(P(L)\) est vraie. ✓

Par récurrence bien fondée, \(P(L)\) est vraie pour toute liste \(L\) : tri_fusion est partiellement correct. Avec la terminaison (A.4), il est totalement correct.

A.6 — Complexité de tri_fusion (calcul)

Mise en équation. La fonction tri_fusion fait deux appels récursifs sur des listes de taille \(n/2\), puis une fusion qui parcourt les \(n\) éléments (coût linéaire, A.3). En notant \(c\) une constante :

Résolution par déroulement. On remplace successivement \(T(n/2)\), \(T(n/4)\), … :

Le déroulement s'arrête quand la sous-liste a taille \(1\), c'est-à-dire \(\dfrac{n}{2^{k}} = 1\), soit \(k = \log_2 n\). On obtient alors :

On retrouve ce résultat par le théorème maître : pour \(T(n) = a\,T(n/b) + O(n)\) avec \(a = b = 2\), on a \(n^{\log_b a} = n^{1} = n\), cas où la complexité vaut \(O(n\log n)\).

Comparaisons et conclusion. Chaque niveau effectue au plus \(n - 1\) comparaisons et il y a \(\log_2 n\) niveaux : le nombre de comparaisons est de l'ordre de \(n\log_2 n\). Cette complexité ne dépend pas du contenu : \(O(n\log n)\) est le même au meilleur et au pire des cas, donc garanti. La complexité spatiale est \(O(n)\) (listes auxiliaires) : le tri par fusion n'est pas en place, mais il est stable.

B. Le tri rapide

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)

B.1 — Correction de l'étape de partition

Ce lemme remplace ici l'invariant de boucle : les deux compréhensions parcourent \(L[1{:}]\) et chaque \(x\) y est rangé selon la comparaison à pivot, de façon exhaustive et exclusive. C'est l'analogue « ensembliste » de l'invariant d'une partition écrite avec une boucle.

B.2 — Terminaison de tri_rapide : fonction de mesure

Le pivot est retiré avant les appels récursifs : \(\operatorname{len}(\text{petits}) + \operatorname{len}(\text{grands}) = \operatorname{len}(L) - 1\). Donc \(\operatorname{len}(\text{petits}) \le n - 1 < n\) et \(\operatorname{len}(\text{grands}) \le n - 1 < n\) : la mesure décroît strictement à chaque appel récursif. Comme \(\mathbb{N}\) est bien fondé, le cas de base est atteint en un nombre fini d'étapes : tri_rapide termine pour toute entrée. ✓

B.3 — Correction de tri_rapide : récurrence bien fondée

Récurrence forte sur \(\mu(L) = \operatorname{len}(L)\).

Cas de base (\(\operatorname{len}(L) \le 1\)). \(L\) est déjà triée et renvoyée telle quelle : \(P(L)\) vraie. ✓

Hérédité. Soit \(n \ge 2\), \(P\) supposée vraie pour toute liste de longueur \(< n\). Comme \(\operatorname{len}(\text{petits}) < n\) et \(\operatorname{len}(\text{grands}) < n\), l'hypothèse de récurrence donne : tri_rapide(petits) est une permutation triée de petits, et tri_rapide(grands) une permutation triée de grands. La valeur renvoyée tri_rapide(petits) + [pivot] + tri_rapide(grands) :

• contient exactement les éléments de \(L\) : \(\text{petits} \cup \{\text{pivot}\} \cup \text{grands} = L\) (lemme B.1) ;
• est triée : tout élément de petits est \(\le \text{pivot}\), tout élément de grands est \(> \text{pivot}\) ; comme chaque bloc est trié et que \(\text{petits} \le \text{pivot} < \text{grands}\), la concaténation est croissante.

Donc \(P(L)\) est vraie. Par récurrence bien fondée, tri_rapide est partiellement correct ; avec B.2, il est totalement correct. ✓

B.4 — Complexité de tri_rapide (calcul)

L'étape de partition parcourt \(L[1{:}]\) (deux compréhensions) : elle coûte \(c\,n\) opérations, soit \(O(n)\). Le coût total dépend de l'équilibre des deux sous-listes, donc du pivot.

Pire des cas. Le pivot est toujours le plus petit (ou le plus grand) élément : une sous-liste est vide, l'autre a \(n - 1\) éléments. La récurrence est \(T(n) = T(n - 1) + c\,n\). On la déroule :

Meilleur cas et cas moyen. La partition équilibre les deux côtés (\(n/2\) chacun) : \(T(n) = 2\,T(n/2) + c\,n\), exactement la récurrence du tri par fusion (A.6), de solution \(O(n\log n)\). En moyenne sur tous les ordres d'entrée, le nombre moyen de comparaisons vaut environ \(2n\ln n \approx 1{,}39\,n\log_2 n\), donc également \(O(n\log n)\).

C. Synthèse

CPGE MP/PSI — Informatique · Analyse des tris : correction, terminaison et complexité