Structures de données - Algorithme de tri par fusion

Le tri par fusion est une technique de tri basée sur la technique de division et de conquête. Dans le pire des cas, la complexité temporelle étant Ο (n log n), c'est l'un des algorithmes les plus respectés.

Le tri par fusion divise d'abord le tableau en deux moitiés égales, puis les combine de manière triée.

Comment fonctionne le tri par fusion?

Pour comprendre le tri par fusion, nous prenons un tableau non trié comme suit -

Nous savons que le tri par fusion divise d'abord le tableau entier de manière itérative en deux moitiés égales à moins que les valeurs atomiques ne soient atteintes. On voit ici qu'un tableau de 8 éléments est divisé en deux tableaux de taille 4.

Cela ne modifie pas la séquence d'apparition des éléments dans l'original. Maintenant, nous divisons ces deux tableaux en deux.

Nous divisons encore ces tableaux et nous obtenons une valeur atomique qui ne peut plus être divisée.

Maintenant, nous les combinons exactement de la même manière qu'ils ont été décomposés. Veuillez noter les codes couleurs donnés à ces listes.

Nous comparons d'abord l'élément pour chaque liste, puis nous les combinons dans une autre liste de manière triée. Nous voyons que 14 et 33 sont dans des positions triées. Nous comparons 27 et 10 et dans la liste cible de 2 valeurs, nous mettons 10 en premier, suivi de 27. Nous changeons l'ordre de 19 et 35 alors que 42 et 44 sont placés séquentiellement.

Dans l'itération suivante de la phase de combinaison, nous comparons des listes de deux valeurs de données et les fusionnons dans une liste de valeurs de données trouvées en les plaçant toutes dans un ordre trié.

Après la fusion finale, la liste devrait ressembler à ceci -

Nous devrions maintenant apprendre quelques aspects de programmation du tri par fusion.

Algorithme

Le tri par fusion continue de diviser la liste en deux moitiés égales jusqu'à ce qu'elle ne puisse plus être divisée. Par définition, s'il ne s'agit que d'un élément de la liste, il est trié. Ensuite, le tri par fusion combine les listes triées plus petites en gardant également la nouvelle liste triée.

Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.

Pseudocode

Nous allons maintenant voir les pseudocodes des fonctions de tri par fusion. Comme nos algorithmes le soulignent, deux fonctions principales - diviser et fusionner.

Le tri par fusion fonctionne avec la récursivité et nous verrons notre implémentation de la même manière.

procedure mergesort( var a as array )
   if ( n == 1 ) return a

   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 )
end procedure

procedure merge( var a as array, var b as array )

   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while
   
   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while
   
   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while
   
   return c
	
end procedure

Pour connaître l'implémentation du tri par fusion dans le langage de programmation C, veuillez cliquer ici .