C11.3 : Tri fusion
L'algorithme du tri fusion a été inventé par le mathématicien américain John von Neumann dans les années 1940. Cependant, le tri fusion a été popularisé par le livre "The Art of Computer Programming" de Donald Knuth (publié en 1968), qui a contribué à sa reconnaissance en tant qu'algorithme de tri efficace et pratique.
Principe d'un algorithme "diviser pour régner"
En informatique, "diviser pour régner" est une technique algorithmique consistant à :
- • Diviser : découper un problème initial en sous-problèmes ;
- • Régner : résoudre les sous-problèmes (récursivement ou directement s'ils sont assez petits) ;
- • Combiner : calculer une solution au problème initial à partir des solutions des sous-problèmes.
Application au tri-fusion
Présentation de la méthode
Le tri fusion est une méthode de tri utilisant un algorithme "diviser pour régner".
C'est une méthode de tri efficace.
Les étapes de l'algorithme consistent à :
- 1) Couper la liste en deux ;
- 2) Trier chacune des deux listes ;
- 3) Fusionner les deux listes triées.
Mise en œuvre
Fonction coupe(L)
Écrire une fonction qui prend une liste en paramètre et sépare ses éléments en deux listes (de tailles identiques à 1 près) qu'elle renvoie.
Fonction fusion(L1, L2)
Écrire une fonction qui prend deux listes triées en paramètres et renvoie une liste triée correspondant à la fusion de ces deux listes.
Fonction récursive tri_fusion(L)
Écrire une fonction récursive qui prend une liste en paramètre et renvoie une liste triée.
Efficacité du tri fusion
Écrire un programme qui compare l'efficacité du tri par insertion, du tri par sélection et du tri fusion.
Pour cela on écrira un programme qui trace les courbes donnant le temps de tri de chacun de ces trois algorithmes en fonction du nombre d'éléments à trier.