Algorithmes de tri

Tri par fusion

Le tri par fusion procède comme suit:

Mise en application du tri par fusion sur une liste d'entiers

Cette méthode de tri, basée sur la technique diviser pour régner, découpe récursivement la liste à trier en deux sous-listes. Si une sous-liste est vide ou possède un seul élément, elle est triée par définition. Sinon, la sous-liste est découpée en deux. Une fois les deux sous-listes triées, l'opération principale de l'algorithme, nommée la fusion, consiste à réunir les sous-listes triées en une seule. Cette fusion se fait selon l'observation suivante: le plus petit élément de la nouvelle liste à construire est soit le plus petit élément de la première sous-liste, soit le plus petit élément de la deuxième sous-liste. Ainsi, on peut construire la nouvelle liste élément par élément en retirant tantôt le premier élément de la première sous-liste, tantôt le premier élément de la deuxième sous-liste après les avoir comparés. Une fois l'une des sous-listes vide, il suffit d'ajouter le reste de l'autre sous-liste en queue de la nouvelle liste. La figure suivante illustre cet algorithme:

Déroulement du tri par fusion sur une liste d'entiers

Le découpage de la liste à trier nécessite de la mémoire supplémentaire mais la complexité de cet algorithme est nettement meilleure que celle des algorithmes précédents en terme de comparaisons réalisées.

A vous de jouer !

En vous basant sur les exemples présentés ci-dessus, répondez à chacun des points suivants:

En guise d'exploration préliminaire de l'algorithme, utilisez la visualisation proposée sur opendsa-server.cs.vt.edu en lui appliquant la liste [3, 4, 6, 2, 5, 1, 8, 7] ci-dessus.
Décrivez à la main chacune des étapes de progression du tri par fusion appliqué à la liste [91, 17, 2, 35, 54]. Au besoin, recourez au lien ci-dessus ou au programme TestFusion vous permettant de valider votre réponse.
Implémentez le tri par fusion en Python en vous basant sur le squelette téléchargeable ici. Corrigez ensuite votre code à l'aide de la solution proposée ci-dessous.
En vous basant sur la solution de l'implémentation réalisée précédemment, décrivez la suite d'appels récursifs générés par l'appel TriFusion([3, 4, 2, 1]).
Pour chacune des listes suivantes, calculez le nombre de comparaisons d'éléments nécessaires à son tri selon l'implémentation proposée précédemment.
1. croissante = [1, 2, 3, 4, 5, 6, 7, 8]
2. decroissante = [8, 7, 6, 5, 4, 3, 2, 1]
3. aleatoire = [54, 26, 93, 31, 77, 17, 44, 55]
Déterminez le nombre de comparaisons nécessaires pour fusionner une liste triée de longueur n avec une liste triée de longueur m dans le meilleur et dans le pire des cas.
Calculez le nombre de comparaisons d'éléments nécessaires au tri de listes comportant 32, 128 puis n éléments. Au besoin, recourez au programme AnalyseComplexite vous permettant de valider vos réponses.

Solution

Voir les solutions sur le site.
L'algorithme est décrit comme suit:

Ceci se traduit récursivement par la suite d'opérations suivantes:
- Découpage de [91, 17, 2, 35, 54] en [91, 17] et [2, 35, 54]
- Découpage de [91, 17] en [91] et [17]
- Fusion des listes [91] et [17] en [17, 91]
- Découpage de [2, 35, 54] en [2] et [35, 54]
- Découpage de [35, 54] en [35] et [54]
- Fusion des listes [35] et [54] en [35, 54]
- Fusion des listes [2] et [35, 54] en [2, 35, 54]
- Fusion des listes [17, 91] et [2, 35, 54] en [2, 17, 35, 54, 91]
- Processus terminé
Solution de l'implémentation
L'appel TriFusion([3, 4, 2, 1] génère la succession d'appels récursifs suivants (TFI correspond à la fonction TriFusionInterne): >>> TriFusion([3, 4, 2, 1]) TFI([3, 4, 2, 1]) fusion(TFI([3, 4]), TFI([2, 1])) fusion(fusion(TFI([3]), TFI([4])), TFI([2, 1])) fusion(fusion([3], TFI([4])), TFI([2, 1])) fusion(fusion([3], [4]), TFI([2, 1])) fusion([3, 4], TFI([2, 1])) fusion([3, 4], fusion(TFI([2]), TFI([1]))) fusion([3, 4], fusion([2], TFI([1]))) fusion([3, 4], fusion([2], [1])) fusion([3, 4], [1, 2]) [1, 2, 3, 4]
1. La liste croissante nécessite 12 comparaisons.
2. La liste decroissante nécessite 12 comparaisons.
3. La liste aleatoire nécessite 17 comparaisons.
Dans le meilleur des cas (par exemple, lorsque tous les éléments de la liste la plus courte sont inférieurs à ceux de la liste la plus longue), la fusion nécessite min(n;m) comparaisons. Dans le pire des cas (par exemple, lorsque tous les éléments de la liste de longueur n sont inférieurs à ceux de la liste de longueur m sauf le dernier qui est plus grand que tous les autres), la fusion nécessite n+m-1 comparaisons.
D'une manière générale, les listes croissante et decroissante à n éléments sont triées à l'aide d'environ n/2log(n) comparaisons et les listes aleatoire à n éléments à l'aide d'environ nlog(n) comparaisons. En effet, les fusions se réalisent en log(n) passes et à chaque passe, les fusions nécessitent au maximum n-1 comparaisons.

D'une manière générale, la complexité du tri par fusion est de l'ordre de nlog(n) tout en comptant le temps de calcul nécessaire pour réaliser les différents découpages. Néanmoins, malgré cette rapidité d'exécution, cet algorithme n'est que très rarement utilisé. En effet, en raison des découpages répétés, l'algorithme nécessite de l'espace mémoire supplémentaire qui peut être un facteur critique lorsque le jeu de données à trier est conséquent.

Algorithmes et structures de données

Navigation

Algorithmes de tri

Tri par fusion

Home

Contact

Droits