Trier un million de valeurs semble long. Mais trier deux moitiés de cinq cent mille valeurs, puis les fusionner, l’est déjà moins… et on peut recommencer sur chaque moitié. C’est l’idée de diviser pour régner : découper un problème en sous-problèmes plus petits de même nature, les résoudre récursivement, puis combiner leurs solutions.
Une question sur ce cours ?
ULU, le tuteur d’ULUMINE, t’aide à partir de ce cours.
Objectifs
- Identifier les trois étapes d’un algorithme « diviser pour régner »
- Écrire la recherche dichotomique sous forme récursive
- Comprendre et programmer le tri fusion
- Comparer le coût du tri fusion (n log n) à celui des tris par insertion ou sélection (n²)
1. Le principe
- Diviser : découper le problème en sous-problèmes de même nature, plus petits (souvent deux moitiés).
- Régner : résoudre chaque sous-problème, récursivement ; les cas assez petits sont résolus directement (cas de base).
- Combiner : construire la solution du problème à partir des solutions des sous-problèmes.
2. Recherche dichotomique récursive
Dans une liste triée, on compare x à l’élément du milieu : soit on l’a trouvé, soit on continue dans une seule moitié. Ici, il n’y a pas d’étape de combinaison : un seul sous-problème est résolu.
def dicho(L, x, g, d):
"""Indice de x dans la liste triée L, entre les indices g et d, ou -1."""
if g > d:
return -1
m = (g + d) // 2
if L[m] == x:
return m
if L[m] < x:
return dicho(L, x, m + 1, d)
return dicho(L, x, g, m - 1)Recherche de 23 dans L = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (appel dicho(L, 23, 0, 9))
- m = 4, L[4] = 16 < 23 : on cherche entre les indices 5 et 9.
- m = 7, L[7] = 56 > 23 : on cherche entre 5 et 6.
- m = 5, L[5] = 23 : trouvé.
La fonction renvoie 5 après 3 appels. Pour n éléments, il y a au plus environ log₂(n) + 1 appels.
3. Le tri fusion
On coupe la liste en deux moitiés, on trie chaque moitié par tri fusion, puis on fusionne les deux moitiés triées : on compare leurs premiers éléments, on prend le plus petit, et on recommence.
def fusion(A, B):
"""Fusionne deux listes triées en une liste triée."""
R = []
i = 0
j = 0
while i < len(A) and j < len(B):
if A[i] <= B[j]:
R.append(A[i])
i = i + 1
else:
R.append(B[j])
j = j + 1
return R + A[i:] + B[j:]
def tri_fusion(L):
if len(L) <= 1:
return L
m = len(L) // 2
return fusion(tri_fusion(L[:m]), tri_fusion(L[m:]))Tri fusion de [5, 2, 7, 1]
- Diviser : [5, 2] et [7, 1], puis [5], [2], [7], [1] (cas de base).
- Combiner : fusion([5], [2]) = [2, 5] et fusion([7], [1]) = [1, 7].
- Combiner : fusion([2, 5], [1, 7]) = [1, 2, 5, 7].
| Tri | Coût dans le pire cas | Pour n = 1 000 000 (ordre de grandeur) |
|---|---|---|
| Insertion, sélection | proportionnel à n² | 10¹² opérations |
| Fusion | proportionnel à n log₂(n) | 2 × 10⁷ opérations |
4. Autres exemples
- Exponentiation rapide : xⁿ = (xn/2)² si n est pair ; on divise l’exposant par 2 à chaque appel.
- Rotation d’une image carrée de côté 2ᵏ d’un quart de tour : on la découpe en quatre quarts, on fait tourner chaque quart récursivement, puis on permute circulairement les quatre quarts.
- Maximum d’une liste : maximum de la moitié gauche, maximum de la moitié droite, puis le plus grand des deux.
À retenir
- Diviser pour régner : diviser, régner (récursivement), combiner.
- Recherche dichotomique : liste triée, une seule moitié explorée, environ log₂(n) étapes.
- Tri fusion : deux moitiés triées récursivement puis fusionnées.
- Le tri fusion coûte de l’ordre de n log₂(n), bien moins que n² pour de grandes listes.
Et maintenant, à toi !
Vérifie que tu as compris avec les exercices, puis révise avec la fiche.