Sur cette page
Un exemple concret
Le tri fusion d'une liste de 8 nombres la coupe en deux listes de 4, puis de 2, puis de 1. Une liste d'un élément est déjà triée. On fusionne ensuite deux à deux des listes triées : 8 listes de 1 deviennent 4 listes de 2, puis 2 de 4, puis une seule liste triée de 8.
Le piège à éviter
Ne confonds pas « découper » et « diviser pour régner » : il faut que les sous-problèmes soient indépendants et de même nature. Si les mêmes sous-problèmes reviennent sans cesse, la programmation dynamique devient plus adaptée.
Pour aller plus loin
La méthode repose sur trois temps. Diviser : on découpe l'entrée, souvent en deux moitiés. Régner : on résout chaque partie, en général par un appel récursif, jusqu'à un cas de base trivial. Combiner : on reconstruit la solution globale à partir des solutions partielles. Toute la difficulté se situe parfois dans la combinaison, comme la fusion de deux listes triées, parfois dans la division, comme le choix du pivot dans le tri rapide.
Le gain se mesure par la complexité. Le tri par insertion vu en Première est en O(n²) dans le pire des cas. Le tri fusion est en O(n log n) : pour n = 1 024, cela représente environ 1 024 × 10 = 10 240 opérations élémentaires, contre environ un million pour un algorithme quadratique. La recherche dichotomique dans un tableau trié relève aussi de cette idée : on élimine une moitié à chaque étape, d'où un coût en O(log n).
D'autres exemples classiques permettent de s'entraîner : le calcul rapide d'une puissance (a puissance n vaut le carré de a puissance n/2 si n est pair), la recherche du maximum d'un tableau en le coupant en deux, ou la rotation d'une image d'un quart de tour par découpage en quatre blocs. Dans le programme de Terminale, la méthode figure dans la partie « Algorithmique », à côté de la programmation dynamique et de la recherche textuelle.
Ne pas confondre
- Programmation dynamique : Elle traite des sous-problèmes qui se chevauchent et mémorise leurs résultats pour ne pas les recalculer ; diviser pour régner suppose des sous-problèmes indépendants.
- Algorithme glouton : Un glouton fait un seul choix local à chaque étape sans revenir en arrière ; il ne découpe pas le problème en sous-problèmes à combiner.
Dans ta copie
La méthode « diviser pour régner » consiste à décomposer un problème en sous-problèmes indépendants de même nature, à les résoudre récursivement, puis à combiner leurs solutions. Le tri fusion en est l'exemple type : on coupe la liste en deux moitiés, on trie chacune récursivement, puis on fusionne les deux listes triées. Comme il y a environ log2(n) niveaux de découpage et que chaque niveau coûte de l'ordre de n opérations, le tri fusion est en O(n log n), ce qui est bien plus efficace qu'un tri par insertion sur de grandes listes.
À retenir
- La méthode suit trois étapes : diviser, régner, combiner.
- Elle s'écrit le plus souvent avec une fonction récursive.
- Le tri fusion a une complexité en O(n log n).
- La recherche dichotomique élimine une moitié à chaque étape.
Teste-toi
NSI · question corrigée
Quelle est la complexité du tri fusion d'une liste de n éléments ?
Voir la réponse
Réponse B. Il y a environ log2(n) niveaux de découpage et chaque niveau de fusion coûte de l'ordre de n opérations.
NSI · question corrigée
Dans le tri fusion, à quelle étape fait-on le travail de comparaison des éléments ?
Voir la réponse
Réponse C. Diviser revient seulement à couper la liste ; ce sont les fusions de listes triées qui comparent les éléments.
Questions fréquentes
Faut-il toujours couper en deux ?
Non, c'est seulement le cas le plus fréquent. On peut couper en trois ou en quatre parties, comme dans la rotation d'une image découpée en quatre blocs.
Le tri rapide relève-t-il aussi de cette méthode ?
Oui. On partitionne la liste autour d'un pivot, puis on trie récursivement les deux parties. Mais avec un mauvais choix de pivot, son pire cas reste quadratique.
Notions liées
Pour réviser tout le chapitre, va sur la page NSI, ou retrouve toutes les définitions dans le lexique du bac. Dans l'application, les quiz reprennent ces notions sur le programme de ta série.