Tri fusion

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Tri fusion appliqué à un tableau de 7 éléments.

Le tri fusion est un algorithme de tri par comparaison stable. Sa complexité temporelle pour une entrée de taille n est de l'ordre de n log n, ce qui est asymptotiquement optimal. Ce tri est basé sur la technique algorithmique diviser pour régner. L'opération principale de l'algorithme est la fusion, qui consiste à réunir deux listes triées en une seule. L'efficacité de l'algorithme vient du fait que deux listes triées peuvent être fusionnées en temps linéaire.

Le tri fusion se décrit naturellement sur des listes et c'est sur de telles structures qu'il est à la fois le plus simple et le plus rapide. Cependant, il fonctionne aussi sur des tableaux. La version la plus simple du tri fusion sur les tableaux a une efficacité comparable au tri rapide, mais elle n'opère pas en place : une zone temporaire de données supplémentaire de taille égale à celle de l'entrée est nécessaire (des versions plus complexes peuvent être effectuées sur place mais sont moins rapides). Sur les listes, sa complexité est optimale, il se montre très simplement et ne requiert pas de copie en mémoire temporaire.

Algorithme[modifier | modifier le code]

L'algorithme est naturellement décrit récursivement. Deux points de vue sont possibles. Voici le premier, particulièrement efficace pour trier les listes :

  1. On trie les éléments deux à deux, ce qui donne de petites listes triées de 2 éléments chacune
  2. On fusionne ces listes deux à deux, ce qui donne de nouvelles listes triées et deux fois plus grandes
  3. On réitère l'opération précédente jusqu'à obtenir une seule liste

Le second point de vue est tout aussi efficace pour le tri des tableaux, mais déconseillé pour les listes :

  1. On coupe en deux parties à peu près égales les données à trier
  2. On trie les données de chaque partie (pour cela, on coupe chaque partie en deux et on trie chacune)
  3. On fusionne les deux parties

La récursivité s'arrête car on finit par arriver à des listes composées d'un seul élément et le tri est alors trivial. En détail :

  fonction scinder(liste0) : 
     si longueur(liste0) <= 1, renvoyer le couple (liste0, liste_vide)
     sinon, 
        soient e1 et e2 les deux premiers éléments de liste0, et reste le reste de liste0
        soit (liste1, liste2) = scinder(reste) 
        renvoyer le couple de listes (liste de tête : e1 et de queue : liste1, liste de tête : e2 et de queue : liste2)
 
  fonction fusionner(liste1, liste2) :
     si la liste1 est vide, renvoyer liste 2 
     sinon si la liste2 est vide, renvoyer liste 1
     sinon 
        si tête(liste 1) <= tête(liste2), renvoyer la liste de tête : tête(liste1) et de queue : fusionner(queue(liste1),liste2)
        sinon, renvoyer la liste de tête : tête(liste2) et de queue : fusionner(liste1,queue(liste2))   
 
  fonction triFusion(liste0) :
     si longueur(liste0) <= 1, renvoyer liste0
     sinon,
        soit (liste1, liste2) = scinder(liste0)
        renvoyer fusionner(triFusion(liste1), triFusion(liste2))

Ce deuxième algorithme n'est pas le plus efficace pour trier les listes, car il scinde avant de trier les moitiés. En effet, l'obtention du point de sission nécessite un parcours de la liste auquel s'ajoute le parcours inéherent à la fusion.


Mise en œuvre sur des listes[modifier | modifier le code]

L'algorithme suivant est détaillé de sorte qu'il soit traduisible en n'importe quel langage impératif en quelques minutes. La liste à trier est de taille n. Pour la concision et l'efficacité de l'algorithme, on suppose que la liste à trier comporte au moins 2 éléments et que :

  • soit elle est simplement chaînée, non circulaire et précédée par un maillon racine p (hors de la liste mais pointant vers son premier élément) ;
  • soit elle est simplement chaînée et circulaire ;
  • soit elle est doublement chaînée et circulaire.

Dans tous les cas, la liste est triée après le chaînon p passé en paramètre, c'est-à-dire que le chainon successeur de p sera le plus petit de la liste. Des descriptions un peu moins concises mais libérées de ces contraintes structurelles existent.

fonction trier(p, n)
    Q := n/2 (division entière)
    P := n-Q
    si P >= 2
        q := trier(p, P)
        si Q >= 2 trier(q, Q)
    sinon
        q := p.suivant
    fin
    q := fusionner(p, P, q, Q)
    renvoyer q
fin
 
fonction fusionner(p, P, q, Q)
    répéter indéfiniment
        si valeur(p.suivant) > valeur(q.suivant) 
            déplacer le maillon q.suivant après le maillon p
            si Q = 1 quitter la boucle
            Q := Q-1
        sinon
            si P = 1
                tant que Q >= 1
                    q := q.suivant
                    Q := Q-1
                fin
                quitter la boucle
            fin
            P := P-1
        fin
        p := p.suivant
    fin
    renvoyer q
fin

Le déplacement d'un maillon q.suivant après un maillon p nécessite un pointeur temporaire t. Si la liste est simplement chainée, le déplacement se fait par cet échange de liens :

t := q.suivant
q.suivant := t.suivant
t.suivant := p.suivant
p.suivant := t

Si la liste est doublement chainée et circulaire, le déplacement se fait par cet échange de liens :

t := q.suivant
 
q.suivant := t.suivant
q.suivant.précédent := q
 
t.précédent := p
t.suivant := p.suivant
p.suivant.précédent := t
p.suivant := t

Ainsi décrit, l'algorithme peut être hybridé très facilement avec d'autres tris. Cela se fait en rajoutant une condition sur la toute première ligne de la fonction fonction trier(p, n). Sur de petites sous-listes, elle a pour rôle de remplacer toutes les operations qui suivent par un tri de complexité quadratique mais en pratique plus rapide. Dans la suite, les conditions P >= 2 et Q >= 2 peuvent alors être retirées.

Mise en œuvre sur des tableaux[modifier | modifier le code]

Avec des tableaux, on peut faire le tri sur place ou non. On a alors schématiquement trois possibilités de gestion de la mémoire :

  • On fait le traitement sur place. On commence par trier les paires ou les triades d'éléments sur place puis on fusionne sur place les listes adjacentes entre elles. La procédure de fusion s'applique alors à un sous-tableau contenant deux listes l'une après l'autre. Pour fusionner en place, la mise en œuvre simple, qui consiste à décaler la première liste quand on insère un ou plusieurs éléments de la deuxième, est lente (un peu comme un tri par insertion). D'autres algorithmes plus rapides existent, mais ils sont compliqués et souvent ne sont pas stables (ne conservent pas l'ordre précédent). Voir le lien externe plus bas.
  • On fait le traitement à moitié sur place. On commence par trier les paires ou les triades d'éléments sur place puis on fusionne. Lors de la fusion, on effectue une copie de la première liste en mémoire temporaire (on peut faire une copie des deux listes, mais ce n'est pas nécessaire). Ainsi on a plus besoin de décaler les données, on copie simplement un élément de la première liste (depuis la mémoire temporaire) ou de la deuxième liste (qui est gardée sur place). Cette solution est plus rapide (plus rapide qu'un tri par tas mais plus lente qu'un tri rapide).
  • On utilise une zone temporaire de même taille que le tableau à trier. On peut alors faire les fusions d'un des tableaux à l'autre. Trier un seul élément revient alors à le recopier d'un tableau à l'autre, trier deux éléments revient à les copier de manière croisée ou non etc. Cette fois, lors de la fusion, quand on copie le premier élément de la première liste ou de la deuxième, on n'a pas besoin de décaler les données, ni de recopier la première liste. Cette solution a une complexité comparable au tri rapide, sans avoir l'inconvénient du pire des cas quadratique. Ce tri fusion fait plus de copies qu'un tri rapide mais fait moins de comparaisons.

Propriétés[modifier | modifier le code]

  1. Le nombre de comparaisons nécessaires est de l'ordre de n \log n.
  2. L'espace mémoire requis est en O(n) à moins de faire des rotations d'éléments.

Optimisations possibles[modifier | modifier le code]

  • Au niveau de l'utilisation de la mémoire :
    • On peut limiter la mémoire utilisée à n/2 éléments en recopiant seulement la première des deux listes à fusionner en mémoire temporaire ;
    • On peut limiter la mémoire utilisée à O(1) en ne recopiant pas les éléments. On peut fusionner en faisant une rotation des éléments allant du milieu de la première liste au milieu de la deuxième.
  • Au niveau de la vitesse d'exécution :
    • On peut avoir la rapidité d'exécution de la copie d'un tableau à un autre, tout en utilisant un tableau temporaire de taille n/2 seulement. Soit A la première et B la deuxième moitié du tableau à trier, et C le tableau temporaire de taille n/2. On trie en copiant les éléments entre A et C, puis entre A et B. Enfin, on fusionne les listes obtenues en B et C dans le tableau entier AB.

Exemple[modifier | modifier le code]

Opération de fusion[modifier | modifier le code]

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) car ce sont des listes 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, procédure complète[modifier | modifier le code]

À l'état initial, on a les éléments un par un, on les fusionne deux à 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 \log n opérations de fusion, ici on a 7 éléments, on fait 3 fusions (nécessitant chacune n comparaisons, soit n \log n).

Voir aussi[modifier | modifier le code]

Sur les autres projets Wikimedia :

Liens externes[modifier | modifier le code]