Implémentation d'algorithmes classiques/Algorithmes de tri/Tri fusion

C

Une mise en œuvre simple du tri fusion sur un tableau d'entiers en C. Cette implémentation effectue une fusion vers un tableau temporaire puis recopie les données fusionnées dans le tableau principal.

#define MAX 50

typedef int tab_entiers[MAX];
 
// Fusion des listes t(de1..vers1) et t(de2..vers2) dans tmp(posInTmp..posInTmp+count-1)
void fusion(tab_entiers t, tab_entiers tmp, int de1, int vers1, int de2, int vers2, int count, int posInTmp) 
{
     int i;
     for(i = 0 ; i < count ; i++)
     {
              if (de2 > vers2)   // Si fin de la liste 2, on prend dans liste 1
                      tmp[posInTmp++] = t[de1++];
              else if (de1 > vers1)   // Idem si fin de la liste 1
                      tmp[posInTmp++] = t[de2++];
              else if (t[de1] <= t[de2])   // Enfin, sinon, on compare
                      tmp[posInTmp++] = t[de1++];
              else 
                      tmp[posInTmp++] = t[de2++];
      }
}
 
// Tri de tout le tableau t par fusions successives
void trifusion(tab_entiers t)
{
      tab_entiers tmp;
      int sortLength = 1, de1, de2, de3, i;
      while(sortLength < MAX)
      {
              de1 = 0;
              while(de1 < MAX)
              {
                    de2 = de1 + sortLength;
                    de3 = de2 + sortLength;
                    if(de2>MAX) de2 = MAX;
                    if(de3>MAX) de3 = MAX;
                    fusion(t, tmp, de1, de2-1, de2, de3-1, de3-de1, de1);
                    de1 = de3;
              }
              for(i = 0 ; i < MAX ; i++) t[i] = tmp[i];
              sortLength *= 2;
       }
 }

Haskell

Mise en œuvre en sur des listes d'un type quelconque ordonnable :

tri []  =  []
tri [x] =  [x]
tri xs  =  fusion (tri ys) (tri zs)
  where (ys,zs) =  splitAt (length xs `div` 2) xs
  
        fusion a [] = a
        fusion [] b = b
        fusion a@(x:xs) b@(y:ys) | x <= y     = x : fusion xs b
                                 | otherwise  = y : fusion a ys

Java ou C#

Mise en œuvre Java ou C# :

public static void triFusion(int[] tab, int début, int fin)
{
	if (début < fin)
	{
		int milieu = (début + fin) / 2;
		triFusion(tab, début, milieu);
		triFusion(tab, milieu + 1, fin);
		fusionner (tab, début, milieu, fin);
	}
}

public static void fusionner(int[] tab, int début, int milieu, int fin)
{
	int[] copie = (int[]) tab.clone(); 
        // tab.clone est très gourmand en temps d’exécution surtout dans un algo récursif
        // il faudrait passer par un tableau temporaire pour stocker les données triées.
        // puis recopier la partie triée à la fin de la méthode.

	int i1 = début;      // indice dans la première moitié de copie
	int i2 = milieu + 1; // indice dans la deuxième moitié de copie
	int i = début;       // indice dans le tableau tab

	while (i1 <= milieu && i2 <= fin)
	{
		//quelle est la plus petite tête de liste?
		if (copie[i1] <= copie[i2])
		{
			tab[i] = copie[i1];
			i1++;
		}
		else
		{
			tab[i] = copie[i2];
			i2++;
		}
		i++;
	}
	if (i <= fin)
	{
		while (i1 <= milieu)  // le reste de la première moitié
		{
			tab[i] = copie[i1];
			i1++;
			i++;
		}
		while (i2 <= fin) // le reste de la deuxième moitié
		{
			tab[i] = copie[i2];
			i2++;
			i++;
		}
	}
}

Caml

Tri fusion de vecteurs en Caml :

let tri_fusion tab =
  let tmp = Array.copy tab in
  let fusion debut milieu fin =
    (* on copie 'tab' dans 'tmp' avant la fusion *)
    Array.blit tab debut tmp debut (fin - debut + 1);
    let gauche, droite = ref debut, ref (milieu + 1) in
    for i = debut to fin do
      let choix =
        if !gauche > milieu then droite
        else if !droite > fin then gauche
        else if tmp.(!gauche) < tmp.(!droite) then gauche else droite in
      tab.(i) <- tmp.(!choix);
      incr choix
    done in
  let rec tri debut fin =
    if debut < fin then
      let milieu = (debut + fin) / 2 in
      tri debut milieu;
      tri (milieu+1) fin;
      fusion debut milieu fin in
  tri 0 (Array.length tab - 1);
  tab

Ce tri fusion sur les vecteurs ne se fait pas exactement en place : on utilise une copie du tableau initial pendant l'opération de fusion. C'est un algorithme impératif : le tableau passé en paramètre est modifié en place.

Tri fusion en utilisant les listes chaînées avec Ocaml :

Le code est séparé en trois fonctions pour plus de clarté. couperListe : prend une liste non triée en paramètre et sépare son contenu en deux listes toujours non triées, dont les longueurs diffèrent d'un élément au maximum. fusionnerListes : prend deux listes triées en paramètre et renvoie une liste triée contenant l'ensemble des éléments des deux listes. triFusion : fonction qui se charge d'appeler les deux autres, elle découpe une liste non triée avec couperListe puis trie récursivement les deux listes résultantes avec triFusion, qu'elle fusionne ensuite avec fusionnerListes.

let rec couperListe = function
  | ([] | [_]) as singleton ->
      (* Il serait strictement identique de renvoyer ([], singleton) *)
      (singleton, [])
  | element1 :: element2 :: queue -> 
      let liste1, liste2 = couperListe queue in
      (* On rajoute chaque élément dans une des deux listes *) 
      (element2 :: liste1, element1 :: liste2)
;;
 
let rec fusionnerListes (liste1, liste2) = match (liste1, liste2) with
  | ([], liste) | (liste, []) ->
      (* Si une des deux listes à fusionner est vide, on renvoie tout simplement la liste non-vide *)
      liste
  | (tete1 :: queue1, tete2 :: queue2) ->
     (* On met la plus petite tête des deux listes en tête de la liste finale
        et on fusionne le reste de la même manière *)
      if tete1 < tete2
      then tete1 :: fusionnerListes (queue1, liste2) 
      else tete2 :: fusionnerListes (queue2, liste1)
;;
 
let rec triFusion= function
  | ([_] | []) as singleton ->
      (* Si la liste ne contient qu'un élément, elle est forcément déjà triée *)
      singleton
  | liste ->
      let liste1, liste2 = couperListe liste in
      (* On trie les deux listes avec triFusion et on les assemble *)
      fusionnerListes (triFusion liste1, triFusion liste2)
;;

Python

# La fonction ''insere'' prend en argument un élément x et une liste triée par ordre croissant.
# Elle insère l'élément x dans la liste

def insere(x,liste):

    if liste==[]:
        return [x]
    elif x<=liste[0]:
        return [x] + liste
    else:
        return [liste[0]] + insere(x,liste[1:len(liste)])

# La fonction ''fusion'' prend en argument deux listes triées par ordre croissant liste1 et liste2
# Elle renvoie la liste obtenue en fusionnant liste1 et liste2 de manière à ce qu'elle soit triée

def fusion(liste1,liste2):

    if liste1==[]:
        return liste2
    elif liste2==[]:
        return liste1
    else:
        return fusion(liste1[1:len(liste1)],insere(liste1[0],liste2))

# La fonction ''tri_fusion'' prend en argument une liste
# Elle renvoie la liste triée. Pour cela, on sépare la liste en deux, on les trie séparément
# puis on les fusionne grâce à la fonction ''fusion'' définie précédemment

def tri_fusion(liste):

    n=len(liste)

    if n==0 or n==1:
        return liste
    else:
        return fusion(tri_fusion(liste[0:n//2]),tri_fusion(liste[n//2:n]))

Tout ou partie de cette page est issue de l'article Wikipédia « Tri fusion » dans sa version du 23/04/2010.