Complexité : meilleur cas (déjà trié) $\Theta(n)$ ; pire cas (trié à l'envers) $\sum_{i=1}^{n-1} i = \dfrac{n(n-1)}{2} = \Theta(n^2)$. Très efficace sur données presque triées.
6 / 22
Propriété 1 : tri en place
Un tri est en place s'il n'utilise qu'une mémoire supplémentaire constante $O(1)$, en réorganisant les éléments à l'intérieur du tableau d'origine.
Pas de copie de taille $n$ : on permute les cases sur place.
Exemples : tri par sélection, tri par insertion, tri rapide (version classique) sont en place. Le tri par fusion ne l'est pas.
7 / 22
Propriété 2 : stabilité
Un tri est stable s'il conserve l'ordre relatif initial des éléments de clé égale.
Définition mathématique. pour tout couple d'indices $i < j$ tel que $\text{clé}(t_i) = \text{clé}(t_j)$, l'élément issu de l'indice $i$ reste avant celui issu de $j$ :
Utile pour trier selon plusieurs critères successifs : trier par âge une liste déjà triée par prénom garde l'ordre alphabétique à âge égal.
8 / 22
Stabilité — exemple
On trie $[\,(3,a),\ (3,c),\ (2,b)\,]$ selon la valeur ($a$ avant $c$ au départ) :
Tri
Résultat
(3,a) vs (3,c)
Insertion (stable)
(2,b), (3,a), (3,c)
a avant c ✔
Sélection (non stable)
(2,b), (3,c), (3,a)
c avant a ✘
Le tri par sélection échange le minimum $2$ (position 2) avec la position 0 occupée par $(3,a)$ : cet échange « à distance » envoie $(3,a)$ après $(3,c)$.
Stables : insertion, fusion. Non stables : sélection, tri rapide.
9 / 22
Tri rapide — principe
Diviser pour régner avec un pivot :
Choisir un pivot dans la liste.
Partition : placer les éléments $\leq$ pivot à gauche, les $>$ pivot à droite. Le pivot est à sa place définitive.
Trier récursivement la sous-liste gauche et la droite.
10 / 22
Tri rapide — arbre d'appels
Sur $[3, 8, 1, 5, 2]$, pivot = 1ᵉʳ élément (rouge). On remonte en concaténant gauche + pivot + droite.
11 / 22
Tri rapide — implémentation
deftri_rapide(L):
iflen(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)
12 / 22
Tri rapide — complexité
La partition d'une liste de taille $n$ coûte $\Theta(n)$.
Meilleur cas — pivot médian, coupe en deux moitiés :
$$T(n) = 2\,T(n/2) + cn \;\Rightarrow\; cn \times \log_2 n = \Theta(n\log n)$$
(travail $cn$ par niveau $\times \log_2 n$ niveaux).
Pire cas — pivot extrémal (liste déjà triée) :
$$T(n)=T(n-1)+cn = c\,(n+\dots+1) = c\,\tfrac{n(n+1)}{2} = \Theta(n^2)$$
En moyenne le coût reste $\Theta(n\log n)$.
13 / 22
Tri rapide — choix du pivot
Prendre toujours le premier élément rend le pire cas $O(n^2)$ fréquent (listes déjà triées).
Pour rendre le pire cas improbable :
pivot aléatoire ;
médiane de trois (premier, milieu, dernier).
Le tri rapide classique est en place mais non stable.
14 / 22
Tri par fusion — principe
Diviser pour régner sans pivot :
Couper la liste en deux moitiés.
Trier récursivement chaque moitié.
Fusionner les deux moitiés triées en une seule liste triée.
15 / 22
L'étape de fusion
deffusion(A, B):
C = []
i, j = 0, 0while i < len(A) and j < len(B):
if A[i] <= B[j]:
C.append(A[i]); i += 1else:
C.append(B[j]); j += 1return C + A[i:] + B[j:]
Fusion de deux listes de tailles $m$ et $p$ en $O(m+p)$.
16 / 22
Tri par fusion — implémentation
deftri_fusion(L):
iflen(L) <= 1:
return L
m = len(L) // 2
gauche = tri_fusion(L[:m])
droite = tri_fusion(L[m:])
return fusion(gauche, droite)
$T(n) = 2\,T(n/2) + O(n) \Rightarrow O(n\log n)$ garanti, même au pire cas.
17 / 22
Tri par fusion — arbre
Sur $[3, 8, 1, 5, 2]$ : on descend en coupant jusqu'aux singletons, puis on remonte en fusionnant.
Fusions successives → [1, 2, 3, 5, 8]
18 / 22
Tri par fusion — exercice
À vous : 1) fusionnez $A=[1,4,7]$ et $B=[2,3,9]$ étape par étape ; 2) établissez la récurrence de $T(n)$ et la complexité au pire cas.
Récurrence : $T(n)=2T(n/2)+cn$. Coupe en deux moitiés garantie ⇒ $cn$ par niveau $\times \log_2 n$ niveaux $= \Theta(n\log n)$ au meilleur, moyen et pire cas (pas de cas dégradé).
19 / 22
Tri par fusion — propriétés
Complexité $O(n\log n)$ garantie (meilleur, moyen et pire cas).
Stable (avec $\leq$ dans la fusion).
Non en place : nécessite $O(n)$ de mémoire supplémentaire.
Compromis : le tri fusion garantit $O(n\log n)$ et la stabilité, au prix de la mémoire ; le tri rapide est en place mais risque $O(n^2)$.
20 / 22
Comparaison des tris
Tri
Moyenne
Pire
En place
Stable
Sélection
$O(n^2)$
$O(n^2)$
Oui
Non
Insertion
$O(n^2)$
$O(n^2)$
Oui
Oui
Rapide
$O(n\log n)$
$O(n^2)$
Oui
Non
Fusion
$O(n\log n)$
$O(n\log n)$
Non
Oui
21 / 22
Récapitulatif
Tri rapide$O(n\log n)$ moyen, en place, non stable
Tri fusion$O(n\log n)$ garanti, stable, $O(n)$ espace
Pivotchoix crucial (aléatoire / médiane)
Tris simples $O(n^2)$ ; rapide et fusion atteignent $O(n\log n)$.
Les deux reposent sur « diviser pour régner ».
Retenir le couple (en place ? / stable ?) de chaque tri.