Analyse des tris efficaces

Pr. EL HADIQ Zouhair

Correction · Terminaison · Complexité — Tri rapide & Tri par fusion

Informatique CPGE — MP / PSI

1 / 16

Cadre : correction totale

$$\text{Correction totale} = \text{Correction partielle} + \text{Terminaison}$$

Objectif	Boucle (itératif)	Récursion
Correction	Invariant : init. + conservation + sortie	Récurrence bien fondée : base + hérédité
Terminaison	Variant $V \in \mathbb{N}$ décroissant (Floyd)	Mesure $\mu \in \mathbb{N}$ décroissante

Ensemble bien fondé. $(\mathbb{N}, <)$ : pas de suite infinie strictement décroissante — c'est ce qui garantit l'arrêt.

2 / 16

Tri fusion — la fonction `fusion`

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

Spécification. Précondition : $A$, $B$ triées. Postcondition : liste triée contenant exactement les éléments de $A$ et $B$.

3 / 16

Correction de `fusion`INVARIANT

♻ Invariant I (début de chaque tour)

(I₁) $C$ est triée ;
(I₂) $C$ contient exactement $A[0{:}i]$ et $B[0{:}j]$ ;
(I₃) tout élément de $C$ est $\leq A[i]$ et $\leq B[j]$ (s'ils existent).

Initialisation. $C=[\,]$, $i=j=0$ : I₁, I₂, I₃ trivialement vraies.

Conservation. On ajoute $m=\min(A[i],B[j])$ ; par I₃, $C \leq m$ donc $C$ reste triée ; un compteur avance (I₂) ; le tri de $A,B$ rétablit I₃.

4 / 16

Correction de `fusion` — sortieINVARIANT

Sortie. La boucle s'arrête quand $i=\text{len}(A)$ ou $j=\text{len}(B)$.

On renvoie $C + A[i{:}] + B[j{:}]$. Par I₂, $C$ contient $A[0{:}i]$ et $B[0{:}j]$ ; le reste (une seule liste non vide) est trié et $\geq$ tous les éléments de $C$ (I₃).

Conclusion Le résultat est trié et contient exactement les éléments de $A$ et $B$ : la postcondition est satisfaite. $\blacksquare$

5 / 16

Terminaison de `fusion`VARIANT

⌛ Variant $V = (\text{len}(A)-i) + (\text{len}(B)-j) \in \mathbb{N}$.

À chaque tour, $i$ ou $j$ augmente de 1 : $V$ décroît strictement. Tant que la boucle tourne, $V \geq 1 > 0$.

Théorème de Floyd Une suite d'entiers naturels strictement décroissante est finie (car $(\mathbb{N},<)$ est bien fondé). Donc la boucle s'arrête. $\blacksquare$

Nombre de tours $\leq \text{len}(A)+\text{len}(B)$ : fusion en $O(m+p)$.

6 / 16

Terminaison de `tri_fusion`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:]))

📏 Mesure $\mu(L) = \text{len}(L) \in \mathbb{N}$ ; cas de base $\text{len}(L) \leq 1$.

Pour $n \geq 2$ : les appels portent sur des longueurs $\lfloor n/2 \rfloor < n$ et $\lceil n/2 \rceil \leq n-1 < n$. $\mu$ décroît strictement $\Rightarrow$ cas de base atteint en temps fini. $\blacksquare$

7 / 16

Correction de `tri_fusion`RÉCURRENCE

P(L) tri_fusion(L) renvoie une permutation triée de $L$. Récurrence forte sur $\mu(L)=\text{len}(L)$.

Base ($\text{len}(L)\leq 1$) : $L$ déjà triée, renvoyée telle quelle. ✓

Hérédité. Pour $n \geq 2$, par hypothèse (longueurs $< n$), gauche et droite sont des permutations triées de $L[:m]$ et $L[m:]$. Par la correction de fusion, le résultat est trié et contient les éléments de $L$. ✓

Avec la terminaison : tri_fusion est totalement correct.

8 / 16

Complexité de `tri_fusion`COMPLEXITÉ

$$T(n) = 2\,T(n/2) + O(n) \;\Longrightarrow\; O(n\log n)$$

Garanti Même complexité au meilleur et au pire cas (la division ne dépend pas du contenu). Espace $O(n)$, stable, non en place.

9 / 16

Calcul — `tri_fusion`COMPLEXITÉ

On déroule $T(n) = 2\,T(n/2) + c\,n$ :

T(n) = 2 T(n/2) + cn = 4 T(n/4) + 2cn = 8 T(n/8) + 3cn = ... = 2^k T(n/2^k) + k·cn

Arrêt quand $n/2^k = 1$, soit $k = \log_2 n$ :

$$T(n) = n\,T(1) + (\log_2 n)\,cn = O(n\log n)$$

Théorème maître $a=b=2$, $n^{\log_b a}=n$ → cas $O(n\log n)$. Au plus $n\log_2 n$ comparaisons.

10 / 16

Tri rapide — partitionLEMME

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)

Lemme de partition $petits=\{x \leq pivot\}$, $grands=\{x > pivot\}$ ; $petits$, $[pivot]$, $grands$ partitionnent $L$, avec $petits \leq pivot < grands$.

11 / 16

Terminaison de `tri_rapide`MESURE

📏 Mesure $\mu(L)=\text{len}(L) \in \mathbb{N}$ ; cas de base $\text{len}(L)\leq 1$.

Le pivot est retiré : $\text{len}(petits) + \text{len}(grands) = \text{len}(L) - 1$.

Donc $\text{len}(petits) \leq n-1 < n$ et $\text{len}(grands) \leq n-1 < n$ : $\mu$ décroît strictement à chaque appel $\Rightarrow$ tri_rapide termine pour toute entrée. $\blacksquare$

12 / 16

Correction de `tri_rapide`RÉCURRENCE

P(L) tri_rapide(L) renvoie une permutation triée de $L$. Récurrence forte sur $\text{len}(L)$.

Base : $\text{len}(L)\leq 1$, déjà triée. ✓

Hérédité : par hypothèse, $tri(petits)$ et $tri(grands)$ triés. La concaténation $tri(petits)+[pivot]+tri(grands)$ :

contient tous les éléments de $L$ (lemme) ;
est triée car $petits \leq pivot < grands$ et chaque bloc est trié. ✓

13 / 16

Complexité de `tri_rapide`COMPLEXITÉ

Cas	Récurrence	Résultat
Moyen / meilleur (équilibré)	$T(n)=2T(n/2)+O(n)$	$O(n\log n)$
Pire (pivot extrémal)	$T(n)=T(n-1)+O(n)$	$O(n^2)$

Terminaison ≠ vitesse La mesure $\mu$ garantit l'arrêt dans tous les cas ; c'est la répartition de la partition qui fixe la vitesse. Pivot aléatoire / médiane de trois $\Rightarrow$ pire cas improbable.

14 / 16

Calcul — `tri_rapide`COMPLEXITÉ

Pire cas ($T(n)=T(n-1)+cn$) :

T(n) = T(n-1) + cn = T(n-2) + c(n-1) + cn = ... = c·(n + (n-1) + ... + 2) + T(1) = c·( n(n+1)/2 - 1 ) + O(1) = O(n²)

Meilleur / moyen ($T(n)=2\,T(n/2)+cn$) : même déroulé que la fusion → $O(n\log n)$.

En moyenne $\approx 2n\ln n \approx 1{,}39\,n\log_2 n$ comparaisons, donc $O(n\log n)$.

15 / 16

Synthèse

Tri	Correction	Terminaison	Complexité
Fusion	Invariant de `fusion` + récurrence	Variant $(m{-}i){+}(p{-}j)$ ; mesure $\text{len}$	$O(n\log n)$ garanti
Rapide	Lemme partition + récurrence	Mesure $\text{len}$ (pivot retiré)	$O(n\log n)$ / $O(n^2)$

Boucle → invariant + variant (Floyd).
Récursion → récurrence bien fondée + mesure décroissante.
Correction = arrêt + résultat juste ; complexité = vitesse.

16 / 16

Analyse des tris efficaces

Cadre : correction totale

Tri fusion — la fonction fusion

Correction de fusionINVARIANT

Correction de fusion — sortieINVARIANT

Terminaison de fusionVARIANT

Terminaison de tri_fusionMESURE

Correction de tri_fusionRÉCURRENCE

Complexité de tri_fusionCOMPLEXITÉ

Calcul — tri_fusionCOMPLEXITÉ