Prog-Info > C++ > Tri et Recherche > Tri fusion.

Le tri fusion

Le principe de cet algorithme est de diviser le tableau en sous tableaux de les traiter et ensuite de les fusionner. Cet algorithme est récursif. On divise le tableau en deux sous tableaux qui sont eux mêmes sont divisés en deux sous tableaux, etc.. La condition d'arrêt est lorsque le tableau ne comporte plus qu'un seul élément.
L'algorithme contient plusieurs parties : la division du tableau en deux, le tri des deux tableaux et la fusion des deux tableaux.

void fusion(int 
        tableau[],const int debut1,const 
        int fin1,const int fin2)

        {

           int *tableau2;

           int debut2 = fin1+1;

           int compteur1 = debut1;

           int compteur2 = debut2;

           int i;

        

           tableau2 = (int*)malloc((fin1-debut1+1)*sizeof(int));

        

           // copie des éléments 
        du début de tableau

           for(i=debut1; i<=fin1; 
        i++)

              tableau2[i-debut1] = tableau[i];

        

           // fusion des deux tableaux

           for(i=debut1; i<=fin2; 
        i++)

           { 

              if(compteur1==debut2) 
        // éléments du 1er tableau tous utilisés

                 break; 
        // éléments tous classés

              else if(compteur2==(fin2+1)) 
        // éléments du 2nd tableau tous utilisés

              { // copie en 
        fin de tableau des éléments du 1er sous tableau

                 tableau[i] = tableau2[compteur1-debut1];

                 compteur1++;

              }

              else if(tableau2[compteur1-debut1]<tableau[compteur2])



              { // ajout d'1 
        élément du 1er sous tableau

                 tableau[i] = tableau2[compteur1-debut1];

                 compteur1++; // 
        on avance ds le 1er sous tableau

              }

              else

              { // copie de 
        l'élément à la suite du tableau

                 tableau[i] = tableau[compteur2];

                 compteur2++; // 
        on avance ds le 2nd sous tableau

              }

           }

           free(tableau2);

        }


        void triFusionAux(int 
        tableau[], const int debut, const 
        int fin)

        {

           if(debut!=fin) // 
        condition d'arrêt

           {

              int milieu 
        = (debut+fin)/2;

              triFusionAux(tableau, 
        debut, milieu); // trie partie1

              triFusionAux(tableau, 
        milieu+1, fin); // trie partie2

              fusion(tableau, debut, 
        milieu, fin); // fusion des deux parties

           }

        }


        void triFusion(int 
        tableau[], const int longueur)

        {

           if(longueur>0)

              triFusionAux(tableau, 
        0, longueur-1);

        }

Exemple :
Les grandes étapes de l'algorithme :

53	31	10	87	13	59	62	26	47	38
53	31	10	87	13	59	62	26	47	38
53	31	10	87	13	59	62	26	47	38
53	31	10	87	13	59	62	26	47	38
31	53	10	87	13	59	62	26	47	38
10	31	53	87	13	59	62	26	47	38
10	31	53	13	87	59	62	26	47	38
10	13	31	53	87	59	62	26	47	38
etc...
10	13	31	53	87	26	38	47	59	62
etc...
10	13	26	31	38	47	53	59	62	87

Complexité :
Le nombre d'opérations effectuées dans cet algorithme est fixe.
Le nombre d'opérations est de l'ordre de n*log(n). (logarithme népérien en base 2)
En ce qui concerne la mémoire, c'est un algorithme récursif donc un peu de mémoire. Cela dépend de la taille du tableau en partie.