Technique de tri par fusion expliquée en C

Le tri est le processus de disposition des éléments par ordre croissant (ou) décroissant.

Types de tri

Le langage C propose cinq techniques de tri comme suit -

• Tri à bulles (ou) tri par échange
• Tri par sélection
• Tri par insertion (ou) Tri linéaire
• Tri rapide (ou) Tri par échange de partitionnement
• Tri par fusion (ou) tri externe

Tri par fusion

Le tri par fusion est une méthode diviser pour régner. Il divise le tableau en deux, le conquiert et le fusionne (combine) de manière récursive.

Considérons un exemple donné ci-dessous -

Prenez un tableau non trié et appliquez la technique de tri par fusion pour trier le tableau.

38, 27, 43, 3, 9, 82, 10

Maintenant, combinez les tableaux en triant comme indiqué ci-dessous -

Exemple

Ce qui suit est un programme C pour trier les éléments en utilisant la fusion Technologie de tri -

Démonstration en direct

#include <stdio.h>
#define max 10
int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
int b[10];
void merging(int low, int mid, int high) {
   int l1, l2, i;
   for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
      if(a[l1] <= a[l2])
         b[i] = a[l1++];
      else
         b[i] = a[l2++];
   }
   while(l1 <= mid)
      b[i++] = a[l1++];
   while(l2 <= high)
      b[i++] = a[l2++];
   for(i = low; i <= high; i++)
      a[i] = b[i];
   }
   void sort(int low, int high) {
      int mid;
      if(low < high) {
         mid = (low + high) / 2;
         sort(low, mid);
         sort(mid+1, high);
         merging(low, mid, high);
      } else {
      return;
   }
}
int main() {
   int i;
   printf("List before sorting</p><p>");
   for(i = 0; i <= max; i++)
   printf("%d ", a[i]);
   sort(0, max);
   printf("</p><p>List after sorting</p><p>");
   for(i = 0; i <= max; i++)
   printf("%d ", a[i]);
}

Sortie

Lorsque le programme ci-dessus est exécuté, la sortie suivante est produite -

List before sorting
10 14 19 26 27 31 33 35 42 44 0
List after sorting
0 10 14 19 26 27 31 33 35 42 44

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!