Le tri à fusion

Le tri fusion

Il s’agit à nouveau d’un tri suivant le paradigme diviser pour régner. Le principe du tri fusion (ou tri par interclassement) en est le suivant :

L'animation ci-après détaille le fonctionnement du fusion :

Démonstration du tri fusion

  1. PROCEDURE tri_fusion ( TABLEAU a[1:n])
  2. FAIRE
  3.     SI TABLEAU EST VIDE RENVOYER TABLEAU
  4.     gauche = partie_gauche de TABLEAU
  5.     droite = partie_droite de TABLEAU
  6.     gauche = tri_fusion gauche
  7.     droite = tri_fusion droite
  8.     renvoyer fusion gauche droite
  9.     POUR i VARIANT DE 1 A n - 1 - passage FAIRE
  10.         SI a[i] > a[i+1] ALORS
  11.             echanger a[i] ET a[i+1]
  12.             permut ← VRAI
  13.         FIN SI
  14.     FIN POUR
  15.     passage ← passage + 1
  16. FIN PROCEDURE
  1. let rec fusion = function
  2.     | liste, []
  3.     | [], liste -> liste
  4.     | h1::t1, h2::t2 ->
  5.         if h1 <= h2 then
  6.           h1 :: fusion (t1, h2::t2)
  7.         else
  8.           h2 :: fusion (h1::t1, t2);;
  9.  
  10. let rec divise = function
  11.     | []
  12.     | [_] as liste -> liste, []
  13.     | tete::queue -> let m1, m2 = divise queue in tete::m2, m1;;
  14.  
  15. let rec tri_fusion = function
  16.     | []
  17.     | [_] as liste -> liste
  18.     | liste ->
  19.         let l1, l2 = divise liste in
  20.           fusion (tri_fusion l1, tri_fusion l2);;
  1. type tab = array of integer;
  2.  
  3. function fusion(gauche, droite: tab): tab;
  4. var
  5. i, j: integer;
  6. begin
  7.     j := 0;
  8.     setlength(fusion, length(gauche) length(droite));
  9.     while (length(gauche) > 0) and (length(droite) > 0) do
  10.     begin
  11.         if gauche[0] <= droite[0] then
  12.         begin
  13.             fusion[j] := gauche[0];
  14.             inc(j);
  15.             for i := low(gauche) to high(gauche) - 1 do
  16.                 gauche[i] := gauche[i1];
  17.             setlength(gauche, length(gauche) - 1);
  18.         end else
  19.         begin
  20.             fusion[j] := droite[0];
  21.             inc(j);
  22.             for i := low(droite) to high(droite) - 1 do
  23.                 droite[i] := droite[i1];
  24.             setlength(droite, length(droite) - 1);
  25.         end;
  26.     end;
  27.     if length(gauche) > 0 then
  28.         for i := low(gauche) to high(gauche) do
  29.             fusion[j i] := gauche[i];
  30.     j := j length(gauche);
  31.     if length(droite) > 0 then
  32.         for i := low(droite) to high(droite) do
  33.             fusion[j i] := droite[i];
  34. end;
  35.  
  36. function tri_fusion(m: tab): tab;
  37. var
  38.     gauche, droite: tab;
  39.     i, milieu: integer;
  40. begin
  41.     setlength(tri_fusion, length(m));
  42.     if length(m) = 1 then
  43.         tri_fusion[0] := m[0]
  44.     else if length(m) > 1 then
  45.     begin
  46.         milieu := length(m) div 2;
  47.         setlength(gauche, milieu);
  48.         setlength(droite, length(m)-milieu);
  49.         for i := low(gauche) to high(gauche) do
  50.             gauche[i] := m[i];
  51.         for i := low(droite) to high(droite) do
  52.             droite[i] := m[milieui];
  53.         gauche  := tri_fusion(gauche);
  54.         droite := tri_fusion(droite);
  55.         tri_fusion := fusion(gauche, droite);
  56.     end;
  57. end;
  1. def fusion(gauche,droite):
  2.     resultat = []
  3.     index_gauche, index_droite = 0, 0
  4.     while index_gauche < len(gauche) and index_droite < len(droite):        
  5.         if gauche[index_gauche] <= droite[index_droite]:
  6.             resultat.append(gauche[index_gauche])
  7.             index_gauche += 1
  8.         else:
  9.             resultat.append(droite[index_droite])
  10.             index_droite += 1
  11.     if gauche:
  12.         resultat.extend(gauche[index_gauche:])
  13.     if droite:
  14.         resultat.extend(droite[index_droite:])
  15.     return resultat
  16.  
  17. def tri_fusion(m):
  18.     if len(m) <= 1:
  19.         return m
  20.     milieu = len(m) // 2
  21.     gauche = m[:milieu]
  22.     droite = m[milieu:]
  23.     gauche = tri_fusion(gauche)
  24.     droite = tri_fusion(droite)
  25.     return list(fusion(gauche, droite))
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. void fusion (int *a, int n, int m) {
  5.     int i, j, k;
  6.     int *x = malloc(n * sizeof (int));
  7.     for (i = 0, j = m, k = 0; k < n; k++) {
  8.         x[k] = j == n      ? a[i++]
  9.              : i == m      ? a[j++]
  10.              : a[j] < a[i] ? a[j++]
  11.              :               a[i++];
  12.     }
  13.     for (i = 0; i < n; i++) {
  14.         a[i] = x[i];
  15.     }
  16.     free(x);
  17. }
  18.  
  19. void tri_fusion (int *liste, int taille) {
  20.     if (taille < 2) return;
  21.     int milieu = taille / 2;
  22.     tri_fusion(liste, milieu);
  23.     tri_fusion(liste milieu, taille - milieu);
  24.     fusion(liste, taille, milieu);
  25. }

Si on applique cet algorithme au petit jeu de la page précédente, on obtient :



 


La complexité dans le pire des cas du tri fusion est en log2(n).