Diviser pour régner : principe et application au tri fusion

En 30 secondes

• Diviser pour régner : DIVISER en sous-problèmes, RÉGNER en les résolvant récursivement, COMBINER les résultats.
• Le tri fusion divise la liste en deux jusqu'à des listes d'un élément (cas de base), puis fusionne les listes triées deux à deux.
• Complexité du tri fusion : O(n log n) en temps, O(n) en espace (listes temporaires de la fusion).

Ce que tu sauras faire

• Décrire les trois étapes du principe diviser pour régner.
• Dérouler les étapes du tri fusion sur une liste d'exemple.
• Déterminer la complexité en temps et en espace du tri fusion.

Les mots à connaître

Diviser pour régner

la stratégie algorithmique qui résout un problème en le divisant en sous-problèmes plus petits de même nature, en résolvant chaque sous-problème séparément, puis en combinant leurs résultats pour obtenir la solution du problème initial.

Sous-problème

une instance plus petite du même problème que le problème initial, obtenue en divisant les données, et résolue par le même algorithme appliqué récursivement.

Tri fusion

un algorithme de tri qui applique le principe diviser pour régner : il divise la liste à trier en deux moitiés, trie récursivement chaque moitié, puis fusionne les deux moitiés triées en une seule liste triée.

Le piège classique

Confondre « diviser » et « trier directement » : le tri fusion ne trie pas en divisant, il trie en FUSIONNANT des sous-listes déjà triées ; la division sert seulement à obtenir des listes assez petites pour être triées trivialement.

L'astuce

DIVISER pour régner : divise le problème, résous chaque petit morceau, puis combine les résultats — jamais l'inverse.