Rappeler les tris simples de 1ʳᵉ année et leur complexité $O(n^2)$.
Comprendre les notions de tri en place et de stabilité.
Définir et implémenter le tri rapide ; discuter le choix du pivot.
Définir et implémenter le tri par fusion.
Comparer les complexités des méthodes.
2 / 15
Rappel : les tris simples
Tri
Principe
Pire cas
Sélection
Placer le minimum en tête, recommencer.
$O(n^2)$
Insertion
Insérer chaque élément dans la partie triée.
$O(n^2)$
À bulles
Échanger les voisins mal ordonnés.
$O(n^2)$
Le tri par sélection effectue $(n-1)+(n-2)+\dots+1 = \dfrac{n(n-1)}{2}$ comparaisons.
Objectif : passer de $O(n^2)$ à $O(n\log n)$.
3 / 15
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.
4 / 15
Propriété 2 : stabilité
Un tri est stable s'il conserve l'ordre relatif initial des éléments de clé égale.
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.
Insertion et fusion sont stables ; sélection et tri rapide ne le sont pas.
5 / 15
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.
6 / 15
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)
7 / 15
Tri rapide — complexité
En moyenne, la partition équilibre les deux côtés :
Pire des cas (pivot toujours extrémal, ex. liste déjà triée) : $T(n)=T(n-1)+O(n) \Rightarrow O(n^2)$.
8 / 15
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.
9 / 15
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.
10 / 15
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)$.
11 / 15
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.
12 / 15
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)$.
13 / 15
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
14 / 15
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.