Algorithmique iii - Tri fusion
← ↑ →
L'algorithme du tri fusion obéit au principe diviser pour régner. Les trois étapes de ce paradigme consistent ici à :
  1. diviser la liste à trier en deux sous-listes de même taille ;
  2. trier chacune de ces deux sous-listes séparément ;
  3. fusionner les deux listes triées pour reconstituer une liste complète triée.
L'algorithme s'écrit généralement de manière récursive, le tri de chacune des deux sous-listes est réalisé de la même façon. La base récurrente con­sis­te simplement à ne rien faire si la liste est constituée d'un seul élement.

Le tri fusion repose fondamentalement sur l'algorithme de fusionnement de deux listes triées qui est de complexité linéaire. Cet algorithme au­xi­liai­re a par ailleurs un intérêt propre indépendamment du tri fusion, nous com­men­ce­rons donc par l'étu­de de celui-ci.

Algorithme de fusion

On se donne deux listes triées \(A\) et \(B\) et on souhaite obtenir une liste triée \(C\) qui contient l'in­té­gra­li­té des termes présents dans ces deux listes. Une première idée naïve consisterait à trier la concaténation \(A.B\) de ces deux listes avec un algorithme de tri de son choix. Cette méthode ne faisant aucun cas de la croissance des deux listes initiales, la complexité de ce tri serait celle de l'algorithme de tri choisi, soit \(\Omega(n\log n)\) s'il s'agit d'un tri com­pa­ra­tif. Néanmoins, il serait intéressant en guise d'exercice (cf. exercice 1) d'estimer la/les complexité(s) de cet algorithme en le limitant aux instances du type \(A.B\) avec \(A\) et \(B\) croissantes et de même longueur.

On peut faire certainement faire mieux en exploitant cette croissance, mais notons dès à présent que la structure choisie pour implanter les listes, tableaux ou listes chaînées, a un impact majeur à la fois sur la conception de l'algorithme et sur la complexité.

L'algorithme de fusionnement efficace est celui qui tombe sous le sens dès que l'on réfléchit quelques instants à un moyen économique de constituer une seule liste triée à partir de deux listes triées. C'est la réponse à un problème que tout le monde a été amené à résoudre dans le monde physique. On dispose de deux boites contenant des fiches triées dans l'ordre croissant dont on ne voit que la première fiche (cf. figure ci-dessous).


\(A\qquad\ \qquad B\ \qquad\qquad C\ \)
Fusion de deux listes triées \(A\) et \(B\) dans une liste \(C\).

Pour trier l'ensemble des valeurs, il suffit de comparer le premier terme de chacune des deux listes \(A\) et \(B\), d'extraire le plus petit des deux de sa boite/liste et de l'insérer à la fin d'une liste auxiliaire \(C\), puis répéter cette opération jusqu'à ce que tous les éléments des deux boites/listes aient été traités. Il n'est pas difficile de démontrer que la complexité de cet algorithme est linéaire en le nombre d'élé­ments contenus dans ces deux listes (cf. exercice plus bas).

Vous pouvez observer le fonctionnement de cet algorithme en modifiant les valeurs des deux listes \(A\) et \(B\) ci-dessous (ces deux listes sont supposées triées).

L'écriture de l'algorithme qui calque le procédé mécanique que nous venons de présenter ne pose aucune difficulté particulière. Les deux listes initiales \(A\) et \(B\) sont donc consommées pour cons­ti­tuer progressivement la liste résultat \(C\) triée. La structure de donnée idoine est ma­ni­fes­te­ment la liste chaînée, l'algorithme ne fait que réagencer les pointeurs pour construire la liste triée \(C\), autrement dit la fusion se fait in situ et ne nécessite pas de mémoire auxiliaire. Cet algorithme s'adapte sans aucune difficulté à une structure de tableau à condition d'allouer un tableau auxiliaire \(C\) de taille \(\#A+\#B\), mais dans ce cas le tri ne se fait plus in situ. L'exercice 3 étudie une manière de réaliser la fusion in situ avec une structure de tableau au prix d'une complexité nettement moins favorable. 

Fusion(A,B):liste
données
   A,B: listes triées 
variables
   C: liste
   i,j: entiers
debut
   C ← []
   TQ (A ≠ []) ET (B ≠ []) FAIRE
      SI (tete(A) ≤ tete(B)) ALORS
         Enfiler(C,Depiler(A)) 
      SINON
         Enfiler(C,Depiler(B)) 
      FSI
   FTQ
   TQ (A ≠ []) FAIRE
      Enfiler(C,Depiler(A)) 
   FTQ 
   TQ (B ≠ []) FAIRE
      Enfiler(C,Depiler(B)) 
   FTQ
   RETOURNER(C) 
FIN
Dans le cas d'une implantation avec des listes chaînées, les deux dernières boucles (instructions #16 à #21) peuvent être avantageusement remplacées par une simple redirection du pointeur vide du dernier enregistrement de la liste \(C\) vers la liste qui n'est pas vide. Cette dernière phase a alors une complexité en \(\Theta(1)\) au lieu d'une complexité linéaire en le nombre de termes résiduels de la liste \(A\) ou \(B\). La version, telle qu'elle est présentée, a pour mérite d'être adaptable sans effort à une structure de tableau.

On peut trouver de nombreuses déclinaisons de cet algorithme sur internet et beaucoup sont récursives. C'est à proscrire, le procédé est éminemment itératif et l'écriture récursive n'apporte aucun bénéfice, même pas sur la forme du code.
Soit \(n\) un entier naturel. Calculez le nombre de comparaisons effectuées par le tri à bulles pour trier la concaténation des listes \(P\) et \(I\) contenant respectivement les entiers pairs (non-nuls) et impairs inférieurs ou égaux à \(n\) dans l'ordre croissant.
Soient \((a_n)_{n\in I}\) et \((b_n)_{n\in J}\) deux séquences croissantes d'entiers naturels d'en­semb­les d'indexation respectifs \(I=[1,k]\) et \(J=[1,l]\) avec \((k,l)\in{\mathbf N}\times{\mathbf N}\). Montrez par récurrence que la séquence \((c_n)_{n\in K}\) où \(K=[1,k+l]\) constituée après l'algorithme de fusionnement est croissante.
Soient \(p,q\) et \(r\) trois entiers naturels tels que \(1\leq p\leq q\leq r\leq n\) et \(T\) un tableau de taille \(n\) d'ensemble d'indexation \([1,n]\). On suppose que le sous-tableau \(T[p,q]\) décrit la liste triée \(A\) et que le sous-tableau \(T[q+1,r]\) décrit la liste triée \(B\).

Écrivez un algorithme Fusion\((T,p,q,r)\) sur place de manière à ce qu'à la fin de la fusion, le sous-tableau \(T[p,r]\) contiennent la liste triée \(C\). Indication : inspirez vous de l'algorithme Tri-Insertion. Quelle est sa complexité ?
Faites la preuve d'arrêt de l'algorithme Fusion. Calculez la complexité \(T(n)\) de l'algorithme en fonction de la longueur \(n\) de la liste fusionnée.

Le tri fusion

L'algorithme du tri fusion mime les trois étapes caractéristiques du principe diviser pour régner et s'écrit simplement. Cette fois nous le présentons dans l'hypothèse d'une implantation avec une structure de tableau. L'algorithme étant récursif, il nous faut disposer pour le processus de division, de deux indices \(p\) et \(r\) qui bornent le sous-tableau \(T[p:r]\) à traiter. Ce processus ne doit perdurer que si le sous-tableau à traiter contient au moins deux éléments, autrement dit si \(r-p+1 \geq 2\) i.e. \(p < r\), d'où le test pour la base récurrente en ligne #6. La division se fait au milieu du tableau dont l'indice est calculé en ligne #7. Les deux sous-tableaux \(T[p,q]\) et \(T[q+1,r]\) sont triés par les appels récursifs des lignes #8 et #9 puis fusionnés en ligne #10. 

Tri-Fusion(@T,p,r)
DONNÉES
   L: liste
   p,r:entiers
DEBUT
   SI (p < r) ALORS
      q ← ⌊(p + r) / 2⌋
      TriFusion(T,p,q)
      TriFusion(T,q + 1,r)
      Fusion(T,p,q,r)
   FSI
FIN
Si la structure de données utilisée est la liste chaînée, la fusion est donc réalisée sur place. Dans le cas où la structure de données utilisée est un tableau, la fusion sur place occasionne un coût qui peut être rédhibitoire et il peut être préférable de se donner un tableau auxiliaire.

Il faut relativiser le coût mémoire d'un tableau auxiliaire, surtout si l'on veut comparer équitablement la complexité en espace avec celle d'une structure de liste chaînée. On rappelle en effet que pour cette dernière structure, chaque enregistrement contient un pointeur dont la taille est celle d'un registre machine, une liste chaînée de taille \(n\) contient donc intrinsèquement l'équivalent d'un tableau d'entiers de taille \(n\) pour sa propre gestion.
On suppose que la longueur du tableau à trier est toujours une puissance de \(2\) (quitte à compléter les cases surnuméraires avec une valeur constante supposée strictement supérieure aux \(n\) valeurs utiles). Réécrivez l'algorithme du tri fusion de manière itérative, en fusionnant les paires de sous-tableaux successifs de taille 1, 2, 4, 8, etc : \begin{align*} \text{taille}\ 1\quad&T[\underbrace{4,\color{yellow}{1}}_{},\underbrace{7,\color{yellow}{2}}_{},\underbrace{5,\color{yellow}{6}}_{},\underbrace{8,\color{yellow}{3}}_{}]\\ \text{taille}\ 2\quad &T[\underbrace{1,4,\color{yellow}{2,7}}_{},\underbrace{5,6,\color{yellow}{3,8}}_{}]\\ \text{taille}\ 4\quad&T[\underbrace{1,2,4,7,\color{yellow}{3,5,6,8}}_{}]\\ \text{tableau trié}\quad&T[1,2,3,4,5,6,7,8] \end{align*} Calculez la complexité de cet algorithme.

Vous pouvez observer le fonctionnement récursif du tri fusion en modifiant les valeurs du tableau ci-dessous. Dans la table, la colonne de gauche indique le numéro de l'appel récursif ainsi que la position où se fait la division ou la fusion. À doite, la position du processus de division est matérialisée par une barre verticale coupant les valeurs de la sous-liste en deux blocs, alors que le processus de fusionnement les fait disparaître.

\(\qquad T=\,[\)\(]\)

On suppose cette fois que la liste à trier est implantée sous forme de liste simplement chaînée. Écrivez un algorithme Séparer\((L)\) qui extrait les enregistrements d'indices pairs de la liste \(L\) et qui les insère dans une liste initialement vide qui sera renvoyée par l'algorithme. À la fin du processus de séparation, la liste \(L\) ne contient donc plus que les termes d'indices impairs (le premier terme de la liste \(L\) a pour indice 1). Calculez la complexité de cet algorithme.
Faites la preuve d'arrêt du tri fusion et prouver sa validité.

Complexité

Travaux pratiques

Écrivez trois versions de l'algorithme du tri fusion :
  1. La structure de données est un tableau et le tri est fait sur place ;
  2. La structure de données est un tableau et on autorise un tableau auxiliaire pour la fusion ;
  3. La structure de données est une liste simplement chaînée.
Comparez le nombre de comparaisons moyen effectuées par ces trois algorithmes de tris en fonction de la taille de la liste \(n\) trier et tracez les trois courbes avec Gnuplot. La moyenne sera ici calculée de manière empirique en triant des listes de taille \(n\) fixée dont les termes auront été tirés aléatoirement. La taille maximale des listes et le nombre d'échantillons seront choisis pour respecter un temps de calcul de l'ordre de quelques minutes pour analyser chacun des algorithmes de tri. On supposera que les listes sont des permutations de \(\mathfrak S_n\).

Pour créer une permutation aléatoire de \(\mathfrak S_n\) (au sens où sa probabilité est la probabilité uniforme \(1/n!\)), partir de la permutation identité \((1,2,3,\ldots,n)\) puis transposer le \(i\)-ème terme avec l'un des termes suivants (donc de la position \(i\) à la position \(n\) incluses) choisi au hasard et ceci pour toutes les valeurs de \(i\) allant de \(1\) à \(n-1\).