Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Tri fusion

Le tri fusion est un algorithme de tri optimal (complexité en et consomme n en mémoire).

Le tri repose sur le fait que pour fusionner deux listes/tableaux trié(e)s, n comparaisons (au maximum) sont nécessaires.

Exemple

Opération de fusion

Fusionner [1;2;5] et [3;4] : On sait que le premier élément de la liste fusionnée sera le premier élément d'une des deux listes d'entrée (soit 1, soit 3), propriété non remarquable sur des listes non triées.

On compare donc 1 et 3 → 1 est plus petit.

[2;5] - [3;4] → [1]

On compare 2 et 3 → 2 est plus petit.

[5] - [3;4] → [1;2]

On compare 5 et 3 → 3 est plus petit.

[5] - [4] → [1;2;3]

On compare 5 et 4 → 4 est plus petit.

[5] → [1;2;3;4]

[1;2;3;4;5]

Bien sûr ce n'est qu'une étape du tri.

Tri, procedure complète

À l'état initial on a les éléments un par un, on les fusionne deux a deux:

([6] [1]) ([2] [5]) ([4] [7]) [3]

On obtient:

([1;6] [2;5]) ([4;7] [3]) que l'on fusionne deux à deux à nouveau et ainsi de suite:

([1;2;5;6] [3;4;7])

[1;2;3;4;5;6;7]

Remarque : On fait operations de fusion, ici on à 7 éléments, on fait 3 fusions (nécessitant chacune n comparaisons, soit ).

Propriétés

1. Le nombre de comparaisons nécessaires est de l'ordre de .
2. L'espace mémoire requis est de n.