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. Divisant ce problème en sous-problèmes (supposés plus simples à résoudre);
  2. Résolvant (régner) ces sous-problèmes individuellement;
  3. Combinant 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 consiste à :

  1. diviser 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 à leur tour 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.

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é. Attention, dans l'animation on montre le paquet \(C\) de l'autre côté afin de voir quelle est la dernière carte qui y a été empilée.

\(\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:r]\) est donc triée.

Écrivez un algorithme Copier(X,i,Y,j,n) qui copie \(n\) valeurs consécutives du tableau \(X\) en partant de \(i\) dans le tableau \(Y\) à partir de \(j\). 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 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,D: tableaux de valeurs
   i, j, k, ng, nd: entiers  
DEBUT
   ng ← q - p + 1
   nd ← r - q
   Allouer(G,ng)
   Allouer(D,nd)  
   Copier(L,p,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 + 1)
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) ALORS
      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.

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=\,[\)\(]\)

L'algorithme du tri fusion est stable. Les seuls échanges entre valeurs de la liste ayant lieu dans l'algorithme de fusionnement, assurons nous que deux termes de même valeur restent dans le même ordre l'un par rapport à l'autre. Les deux sous-listes sont supposées triées avant le fusionnement. Si les deux valeurs identiques sont dans la même sous-liste, c'est évident puisqu'elles la première sera rangée avant la seconde dans la liste fusionnée. Dans l'autre cas la valeur qui est placée avant l'autre dans la liste intiale sera dans la sous-liste gauche et la deuxième dans la sous-liste droite et comme en cas d'égalité l'algorithme de partitionnement extrait d'abord la valeur de la sous-liste gauche, on a le résultat.

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{#FF8}{1}}_{},\underbrace{7,\color{#FF8}{2}}_{},\underbrace{5,\color{#FF8}{6}}_{},\underbrace{8,\color{#FF8}{3}}_{}]\\ \text{taille}\ 2\quad &T[\underbrace{1,4,\color{#FF8}{2,7}}_{},\underbrace{5,6,\color{#FF8}{3,8}}_{}]\\ \text{taille}\ 4\quad&T[\underbrace{1,2,4,7,\color{#FF8}{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.
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{#FF8}T(\frac{n}{2})}+\Theta(n)\\ &=2\left({\color{#FF8}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

Déclarez la structure tliste suivante pour représenter les listes : 
typedef struct {
  uint n;        // longueur de la liste
  int *valeurs;
} tliste;
Écrivez une fonction void Copier(tliste X, uint i, tliste Y, uint j, uint n) qui copie les \(n\) valeurs de l'intervalle \(\ab{i}{i+n-1}\) de la liste \(X\) aux positions \(\ab{j}{j+n-1}\) de la liste \(Y\) respectivement. La copie doit s'arrêter au cas où l'on a atteint la fin d'une des listes avant d'avoir copié \(n\) valeurs.
Écrivez une fonction void Fusionner(tliste L, uint p, uint q, uint r) qui fusionne la sous-liste \(L[p,q]\) avec la sous-liste \(L[q+1,r]\) dans la sous-liste \(L[p,r]\).
Écrivez une fonction void TriFusion(tliste L, uint p, uint r) qui trie une liste \(L\) avec l'algorithme du tri fusion. Vérifiez de manière empirique, en triant des permutations aléatoires de différentes tailles (cf. tris empiriques) que la complexité moyenne de ce tri est conforme au cours.
Complément :
Implantez l'algorithme du tri fusion pour des listes avec une structure de liste chaînée et faites de même.
Implantez la version itérative du tri fusion étudié en travaux dirigés sur des tableaux de taille \(2^k\). On suppose que le tableau \(T\) est de taille quelconque et ne contient que des valeurs entières de majorant strict \(m:=2^{63}-1\). Pour pouvoir appliquer l'algorithme, on complètera \(T\) par le nombre de valeurs \(m\) nécessaires pour que sa longueur soit égale à \[2^{\lceil\log_2(|T|)\rceil}\] où \(\lceil x\rceil\) désigne le plus petit entier supérieur ou égal à \(x\).