Tri fusion

Diviser pour régner.

À l'instar de la politique où le principe diviser pour régner consiste à semer la discorde afin d'af­fai­blir ses adversaires, en informatique ce principe consiste à affaiblir le problème à résoudre en

  1. Partitionnant (diviser) ce problème en sous-problèmes (supposés plus simples à résoudre);
  2. Résolvant (régner) ces sous-problèmes individuellement;
  3. Réunissant les résultats partiels pour résoudre le problème initial.

Un exemple classique de problème étudié dès le lycée et dont la résolution s'appuie sur ce principe algorithmique est la recherche dichotomique. En effet, la partition divise la zone de recherche en deux parts de tailles égales et on se concentre uniquement sur la bonne moitié en reproduisant ce mécanisme sur une nouvelle moitié et ainsi de suite de manière à ramener la zone de recherche à une unité. Notons que dans ce cas, la résolution d'un des deux sous-problèmes se résume à ne rien faire. Beaucoup d'algorithmes reposant sur ce principe sont récursifs, en effet si les sous-problèmes ne sont qu'une homothétie du problème initial, il est tentant de leur appliquer à nouveau le principe et ainsi de suite.

L'algorithme de tri que nous allons étudier dans ce chapitre utilise ce principe algo­ri­thmi­que tout comme celui du chapitre prochain, le tri rapide. Nous verrons en troi­sième année d'autres al­go­ri­thmes de cette nature, la mul­ti­pli­ca­tion de Ka­rat­suba et la transformée de Fourier rapide.

Le tri fusion.

Comme toujours pour les algorithmes de tri, on cherche à trier les valeurs d'un tableau/liste dans l'ordre croissant. Le fonctionnement de l'algorithme du tri fusion est relativement simple, il consiste :

  1. à partitionner la liste en deux parts égales ;
  2. à trier chacune des deux parts ;
  3. à fusionner les deux parts triées.

La nature des deux sous-problèmes à résoudre est strictement identique à celle du problème initial, il est donc naturel de diviser les listes en deux à leurs tours et ainsi de suite à la manière de la dichotomie. Ces divisions successives aboutissent au tri d'une multitude de listes qui ne contiennent plus qu'un seul élément (ou vides, selon la parité du nombre d'éléments des listes ancêtres). La division en deux part égales ne pose aucune difficulté dans le cas où la liste a une structure de tableau, il suffit de calculer le milieu du tableau, à savoir \(\frac{n+1}{2}\) si le tableau est indexé de \(1\) à \(n\). C'est plus compliqué s'il s'agit d'une liste chaînée (cf. exercice).

Le fusionnement.

À ce stade, rien n'est encore trié, c'est l'étape de fusionnement qui va trier effectivement la liste. De manière imagée, l'algorithme de fusionnement est la transposition informatique de la méthode que nous appliquons naturellement pour rassembler le contenu de deux paquets de cartes triées pour obtenir un seul paquet trié. On dispose les deux tas de cartes triées faces visibles côte-à-côte et on retire la plus petite des deux cartes au sommet de ces tas pour la placer sur le nouveau tas, face cachée cette fois, et on recommence jusqu'à ce qu'il ne reste qu'un tas qu'il suffit de rajouter au tas nouvellement constitué. L'animation ci-dessous laisse penser que le tas de cartes \(C\) est trié dans l'ordre inverse alors qu'il est simp­lement affiché face visible dans l'ordre inverse pour illustrer le mécanisme.

\(\phantom{B}A=\)
\(\phantom{A}B=\)
\(\phantom{A}C=\) [ ]

Nous allons présenter l'algorithme dans le cas où la liste a une structure de tableau. Le fusionnement opérant sur deux sous-listes d'une même liste, trois indices croissants \(p\), \(q\) et \(r\) caractérisent les deux sous-listes contiguës \(L[p:q]\) et \(L[q+1:r]\) supposées triées. Après le fu­sion­nement, la liste \(L[p:q]\) est donc triée.

Écrivez un algorithme Copier(X,s,Y,d,n) qui copie \(n\) valeurs consécutives du tableau \(X\) en partant de \(s\) dansle tableau \(Y\) à partir de \(d\). Faites la preuve de justesse et la preuve d'arrêt.

La première étape consiste à recopier les éléments des deux sous-listes \(L[p:q]\) et \(L[q+1:r]\) dans deux listes auxiliaires \(G\) et \(D\) (partie gauche et partie droite), permettant ainsi d'écraser les anciennes valeurs de la sous-liste \(L[p:r]\) lors de la fusion de \(G\) et \(D\). La boucle (# 14) compare les premiers termes et range le plus petit dans la liste initiale tant qu'il reste un terme dans les deux listes. Il faut noter l'asymétrie du traitement des termes de la liste résiduelle, en effet il est inutile de copier les termes de la liste \(D\) si la liste \(G\) est vide à l'issue de la boucle puisque dans ce cas les éléments de \(D\) sont déjà à leur place dans la liste initiale \(L\).

Fusionner(@L,p,q,r)
données
   L: tableau de valeurs
   p, q, r: entiers
variables
   G: tableau de q - p valeurs
   D: tableau de r - q - 1 valeurs
   i, j, k, ng, nd: entiers  
DEBUT
   ng ← q - p + 1
   nd ← r - q
   Copier(L,1,G,1,ng)
   Copier(L,q + 1,D,1,nd)
   i ← 1
   j ← 1
   k ← p
   TQ ((i ≤ ng) ET (j ≤ nd)) FAIRE
      SI (G[i] ≤ D[j]) ALORS
         L[k] ← G[i]
         i ← i + 1
      SINON
         L[k] ← D[j]
         j ← j + 1
      FSI
      k ← k + 1   
   FTQ
   Copier(G,i,L,k,ng - i)
FIN

Nous supposons que l'algorithme Copier est valide. Les variables \(i\) et \(j\) sont initialisées à 1 avant l'entrée dans la boucle #17 et l'une des deux exclusivement est incrémentée à chaque passage, ainsi une des deux conditions (exclusivement là aussi) de la conjonction ne sera plus satisfaite et on sortira de cette boucle, donc l'algorithme se termine.

Montrons que la liste \(L\) est bien triée à la fin de l'exécution. Considérons l'assertion suivante : à chaque entrée dans la boucle #17, le sous-tableau \(L[p:k-1]\) contient les \(k-p\) éléments les plus petits et triés des sous-tableaux \(G[1:n_g]\) et \(D[1:n_d]\), d'autre part \(G[i]\) (resp. \(D[j]\)) est la plus petite valeur du tableau \(G\) (resp. \(D\)) qui n'a pas été replacée dans \(L\). Avant l'entrée dans la boucle, le sous-tableau \(L[p:k-1]\) est vide puisque \(k=p\), il contient bien les \(k-p=0\) plus petits éléments de \(G\) et \(D\) triés et \(G[1]\) et \(D[1]\) sont bien les plus petites valeurs respectives de \(G\) et \(D\) qui n'ont pas encore été replacées dans \(L\). Supposons que \(G[i]\leq D[j]\) (même raisonnement en inversant les rôles de \(G\) et \(D\) dans le cas contraire), dans ce cas \(G[i]\) est la plus petite valeur qui n'a pas encore été replacée dans \(L\). Comme \(L[p:k-1]\) contient les \(k-p\) plus petits éléments, une fois que \(G[i)\) a été copié dans \(L[k]\), le sous-tableau \(L[p:k]\) contient les \(k-p+1\) plus petits éléments. S'ensuivent les incréments de \(i\) et \(k\) qui rétablissent l'invariant de boucle.

La sortie de la boucle se fait pour \(i = n_g\) ou \(j = n_d\), avec \(L[p,k]\) qui contient les plus petits éléments triés. Dans les deux cas, les éléments résiduels sont triés et plus grands que les \(k-p+1\) premiers éléments de \(L[p:r]\) qu'il faille les recopier dans \(L\) si \(j = n_d\) ou non si \(i = n_g\).

Le tri.

L'écriture de l'algorithme ne pose plus alors aucune difficulté, il suffit de réaliser la division en deux parts égales du tableau en calculant le milieu et d'appeler récursivement l'algorithme sur chacun des deux sous-tableaux puis de les fusionner une fois triés. Il peut paraître prématuré de présenter des algorithmes récursifs avant même l'étude de la récursivité qui se fera en troisième année, mais son utilisation ici ne pose pas de difficulté particulière, on acceptera donc cette opportunité sans en comprendre nécessairement les dessous. À ce stade un algorithme a un statut récursif s'il fait appel à lui-même. Bien entendu cela suppose que les appels récursifs (autodéfinition) se font sur des instances de plus en plus petites pour que le procédé converge, et qu'il faut également savoir traiter la ou les instances atomiques sans faire appel à la récursivité (base récurrente) pour la même raison.

Tri-Fusion(@L,p,r)
données
   L: tableau de valeurs
   p, r: entiers
variables
   q: entier
DEBUT
   SI (p < r)
      q ← (p + r) / 2
      Tri-fusion(L,p,q)
      Tri-fusion(L,q + 1,r)
      Fusionner(L,p,q,r)
   FSI
FIN

Ici la base récurrente consiste à ne rien faire (le sous-tableau ne contient qu'un seul élément) et les deux appels récursifs suivent le calcul du milieu de l'intervalle du tableau à considérer. La figure ci-dessous illustre le processus récursif de partitionnement puis de fusionnement des différents sous-tableaux.

Appels récursifs (AR) et fusionnements (F) tableau \([3,5,4,1,0,2,6]\) par l'algorithme du tri fusion.
On suppose que la liste \(L\) est implantée sous forme de liste chaînée. Écrivez un algorithme Partager\((@L)\) qui renvoie une liste chaînée contenant tous les éléments d'ordre impair de la liste \(L\) obtenus en les détachant de la liste \(L\) (à la fin du partage, la liste \(L\) ne contient donc plus que les éléments d'ordre pair). Écrivez un algorithme de fusionnement de deux listes chaînées triées, qui renvoie la liste triée (les deux listes d'origine sont vides à la fin du fusionnement). Concluez en écrivant l'algorithme du tri fusion pour une liste chaînée.

Complexité.

La complexité de l'algorithme qui réalise la copie est évidemment en \(\Theta(n)\) si \(n\) désigne le nombre de termes à copier. Pour ne pas compliquer inutilement l'analyse de la complexité de l'algorithme Fusionner, nous supposerons que les termes du tableau résiduel sont systématiquement recopiés dans la liste \(L\) même lorsque cette copie est inutile s'il s'agit de la liste \(D\). L'approche globale est ici préférable, chaque terme de la liste \(L\) est copié une première fois dans l'une des deux listes auxiliaires \(G\) ou \(D\) et la boucle principale suivie de la copie résiduelle les réintègre un-à-un dans la liste d'origine \(L\), il y a donc \(2n\) copies. Autrement dit la complexité du fusionnement est \(\Theta(n)\) si \(n\) désigne le nombre de termes dans la liste \(L\).

Notons \(T(n)\) la fonction de complexité du tri fusion. L'algorithme étant récursif \(T(n)\) va s'écrire très logiquement à l'aide d'une récurrence faisant apparaître cette fonction autant de fois dans la récurrence qu'il y a d'appels récursifs dans l'algorithme. Supposons qu'un algorithme utilisant le paradigme diviser pour régner, divise l'instance en \(b\) parts égales et s'appelle \(a\) fois*(*) pour le tri fusion on a \(a=b=2\), mais il exis­te des al­go­ri­thmes ré­cur­sifs tels que \(a\not = b\). Si l'on suppose que le coût de l'algorithme est constant \(\Theta(1)\) en deça d'une certaine taille de données à traiter, que le coût de la division est \(D(n)\) et celui de la combinaison des résultats partiels \(C(n)\), on obtient la récurrence suivante :

\begin{equation} \label{eq:rec} T(n)= \begin{cases} \Theta(1)&\text{si}\ n\leq c,\\ aT(\frac{n}{b})+D(n)+C(n)&\text{sinon}. \end{cases} \end{equation}

La base récurrence consiste à ne rien faire quand le tableau ne contient qu'un seul élément (\(n=1\)), donc la constante \(c=1\). Le coût de la division se limite à calculer l'indice du milieu du tableau (instruction #9) et le coût est donc \(D(n)=\Theta(1)\) et nous savons que le coût du fusionnement est \(\Theta(n)\). La récurrence \((\ref{eq:rec})\) devient

\begin{equation} \label{eq:rec2} T(n)= \begin{cases} \Theta(1)&\text{si}\ n\leq 1,\\ 2T(\frac{n}{2})+\Theta(n)&\text{sinon}. \end{cases} \end{equation}

Nous verrons l'an prochain comment résoudre une récurrence générale du type \((\ref{eq:rec})\) afin de ne pas avoir à produire une démonstration pour chaque nouvel algorithme récursif. Pour ne pas alourdir l'exposé nous supposerons ici que \(n=2^k\) afin de ne pas avoir à considérer la propagation des parties entières lors des appels récursifs. Sans cette hypothèse, le résultat du calcul qui va suivre est simp­lement la conjonction d'une minoration et d'une majoration. En appliquant la formule \((\ref{eq:rec2})\) à \(T(\frac{n}{2})\) et en répétant le remplacement \(k\) fois de suite, on obtient

\begin{align*} T(n) &=2{\color{#FF0}T(\frac{n}{2})}+\Theta(n)\\ &=2\left({\color{#FF0}2T(\frac{n}{4})+\Theta(\frac{n}{2})}\right)+\Theta(n)\\ &\phantom{=}\vdots\\ &=2^kT(\frac{n}{2^k})+k\Theta(n)\\ &=n\Theta(1)+\log_2(n)\Theta(n)\\ &=\Theta(n\log n). \end{align*}
La complexité de l'algorithme du tri fusion pour trier un tableau de taille \(n\) est \begin{equation} T(n)=\Theta(n\log(n)). \end{equation}
Quelle est la complexité de l'algorithme du tri fusion dans le cas où la liste a une structure de liste chaînée (cf. exo)  ?

Travaux pratiques

Implantez l'algorithme du tri fusion pour des listes avec une structure de tableau. Vérifiez expérimentalement la complexité de cet algorithme à partir de tableaux associés à des permutations aléatoires. On rappelle que pour créer une permutation aléatoire de \(\mathfrak S_n\) (au sens où sa probabilité est la probabilité uniforme \(1/n!\)), il faut 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\).
Implantez l'algorithme du tri fusion pour des listes avec une structure de liste chaînée et faites de même.