algorithme Tri fusion avec tableau
entrée Un tableau T[1,n] de valeurs d'un ensemble totalement ordonné.
sortie Le tableau T trié dans l'ordre croissant
complexité O(n log n)
sources C tri-fusion-tab.c   creer-tab.c

Sommaire

  1. Problème et modélisation
  2. Description de l'algorithme
  3. Validité de l'algorithme
  4. Notes sur les sources en langage C
  5. Complexité de l'algorithme
  6. Exercices

Problème et modélisation.
On cherche à trier les valeurs d'une liste rangées dans une structure de tableau dans l'ordre croissant.

Description de l'algorithme.
L'algorithme est basé sur le principe "diviser pour régner", autrement dit on divise virtuellement le tableau de départ en deux sous-tableaux de la moitié de la taille initiale et ainsi de suite jusqu'à ce que les tableaux ne contiennent plus qu'un seul élément. Le backtracking commence à ce moment et l'algorithme de fusionnement fusionne les deux sous-tableaux en un tableau trié de deux valeurs et le processus récursif va assurer la reconstitution complète du tableau.

Exemple: T = [3,1,5,9,4,6,8,7,2]. L'arbre de récursion explicite le principe de division (D) et de fusionnement (F) de l'algorithme. Les nombres à gauche indique le niveau la profondeur de récursion.



C'est donc l'algorithme de fusionnement qui fait la majeure partie du travail.

algorithme TRI-FUSION(@T,g,d);
données
   T: tableau de valeurs;
   g,d: entiers;
variables
    p: entier;
debut   
   SI (g < d) ALORS 
      p ← (g + d) / 2;
      TRI-FUSION(T,g,p);
      TRI-FUSION(T,p + 1,d);
      FUSIONNER(@T,g,p,d);
   FSI
fin.

Validité de l'algorithme.
L'algorithme se termine car la taille de l'intervalle [g,d] des sous-tableaux est divisée par deux à chaque appel ce qui assure que la condition g ≥ d de sortie de boucle sera nécessairement satisfaite. Pour la validité de l'algorithme, on fait une récurrence. Si l'on suppose que les deux appels récursifs trient le sous-tableau gauche T[g,p] et le sous-tableau droit T[p + 1,d], alors leur fusion reconstitue un tableau T[g,d] trié. La base récurrente est satisfaite puisque dans le cas où le tableau ne contient qu'un seul terme, lalgorithme ne fait rien, le tableau étant trivialement trié.

Notes sur les sources en langage C.
Il n'y a rien de particulier à signaler, excepté la remarque usuelle sur le indices d'indexation des tableaux du C qui commencent à 0.

complexité de l'algorithme.
La taille des données est évidemment le cardinal n du tableau à trier. Il n'y a pas lieu de distinguer de meilleur ou de pire des cas, le processus récursif ne dépend pas de l'instance mais uniquement de sa taille n. La formule de récurrence suivante somme respectivement le coût du test, du calcul du milieu p et du fusionnement, soit Θ(1) + Θ(1) + Θ(n) = Θ(n) et des deux appels récursifs :

T(n) = Θ(n) + 2T(n/2)    avec   T(1) = Θ(1).
et en substituant T(n/2) par sa valeur, on obtient
T(n) = Θ(n) + 2[Θ(n/2) + 2T(n/4)]
En poursuivant le procédé de substitution, on obtient log n termes Θ(n) dans la somme et finalement
T(n) = Θ(n log n)