>
Menu

Fusionner le tri en C ++ avec des exemples

merge sort c with examples

Technique de tri par fusion C ++.

L'algorithme de tri par fusion utilise le ' diviser et conquérir ”Stratégie dans laquelle nous divisons le problème en sous-problèmes et résolvons ces sous-problèmes individuellement.

Ces sous-problèmes sont ensuite combinés ou fusionnés pour former une solution unifiée.

=> Lisez la série de formations populaires C ++ ici.

Tri par fusion

Ce que vous apprendrez:

Aperçu

Le tri par fusion est effectué en suivant les étapes suivantes:

#1) La liste à trier est divisée en deux tableaux de longueur égale en divisant la liste sur l'élément du milieu. Si le nombre d'éléments de la liste est égal à 0 ou à 1, la liste est considérée comme triée.

#deux) Chaque sous-liste est triée individuellement en utilisant le tri par fusion de manière récursive.

# 3) Les sous-listes triées sont ensuite combinées ou fusionnées pour former une liste triée complète.

Algorithme général

Le pseudo-code général de la technique de tri par fusion est donné ci-dessous.

déclaration de variables statiques en c ++

Déclarer un tableau Arr de longueur N
Si N = 1, Arr est déjà trié
Si N> 1,
Gauche = 0, droite = N-1
Trouver le milieu = (gauche + droite) / 2
Appeler merge_sort (Arr, left, middle) => trier la première moitié de manière récursive
Appeler merge_sort (Arr, middle + 1, right) => trier la seconde moitié de manière récursive
Appelez merge (Arr, gauche, milieu, droite) pour fusionner les tableaux triés dans les étapes ci-dessus.
Sortir

Comme indiqué dans le pseudo code ci-dessus, dans l'algorithme de tri par fusion, nous divisons le tableau en deux et trions chaque moitié en utilisant le tri par fusion de manière récursive. Une fois que les sous-tableaux sont triés individuellement, les deux sous-tableaux sont fusionnés pour former un tableau trié complet.

Pseudo code pour le tri par fusion

Voici le pseudo code de la technique de tri par fusion. Tout d'abord, nous avons une procédure de tri par fusion pour diviser le tableau en deux de manière récursive. Ensuite, nous avons une routine de fusion qui fusionnera les petits tableaux triés pour obtenir un tableau trié complet.

procedure mergesort( array,N ) array – list of elements to be sorted N – number of elements in the list begin if ( N == 1 ) return array var array1 as array = a[0] ... a[N/2] var array2 as array = a[N/2+1] ... a[N] array1 = mergesort(array1) array2 = mergesort(array2) return merge( array1, array2 ) end procedure procedure merge(array1, array2 ) array1 – first array array2 – second array begin var c as array while ( a and b have elements ) if ( array1[0] > array2[0] ) add array2 [0] to the end of c remove array2 [0] from array2 else add array1 [0] to the end of c remove array1 [0] from array1 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

Illustrons maintenant la technique de tri par fusion avec un exemple.

Illustration

fusion de tri Illustration

L'illustration ci-dessus peut être présentée sous forme de tableau ci-dessous:

PasseListe non triéediviserListe triée
1{12, 23,2,43,51,35,19,4}{12,23,2,43}
{51,35,19,4}		{}
deux{12,23,2,43}
{51,35,19,4}		{12.23} {2.43}
{51,35} {19,4}		{}
3{12.23} {2.43}
{51,35} {19,4}		{12.23} {2.43}
{35.51} {4.19}		{12.23} {2.43}
{35.51} {4.19}
4{12.23} {2.43}
{35.51} {4.19}		{2,12,23,43}
{4,19,35,51}		{2,12,23,43}
{4,19,35,51}
5{2,12,23,43}
{4,19,35,51}		{2,4,12,19,23,35,43,51}{2,4,12,19,23,35,43,51}
6{}{}{2,4,12,19,23,35,43,51}

Comme le montre la représentation ci-dessus, le tableau est d'abord divisé en deux sous-tableaux de longueur 4. Chaque sous-tableau est en outre divisé en deux autres sous-tableaux de longueur 2. Chaque sous-tableau est ensuite divisé en un sous-tableau d'un élément chacun. Tout ce processus est le processus de «division».

Une fois que nous avons divisé le tableau en sous-tableaux d'un seul élément chacun, nous devons maintenant fusionner ces tableaux dans l'ordre trié.

Comme le montre l'illustration ci-dessus, nous considérons chaque sous-tableau d'un seul élément et combinons d'abord les éléments pour former des sous-tableaux de deux éléments dans l'ordre trié. Ensuite, les sous-tableaux triés de longueur deux sont triés et combinés pour former deux sous-tableaux de longueur quatre chacun. Ensuite, nous combinons ces deux sous-tableaux pour former un tableau trié complet.

Tri de fusion itératif

L'algorithme ou la technique de tri par fusion que nous avons vu ci-dessus utilise la récursivité. Il est également connu sous le nom de ' tri par fusion récursif ».

Nous savons que les fonctions récursives utilisent la pile d'appels de fonction pour stocker l'état intermédiaire de la fonction appelante. Il stocke également d'autres informations de comptabilité pour les paramètres, etc. et pose des frais généraux en termes de stockage de l'enregistrement d'activation de l'appel de la fonction ainsi que de la reprise de l'exécution.

Tous ces frais généraux peuvent être éliminés si nous utilisons des fonctions itératives au lieu de fonctions récursives. L'algorithme de tri par fusion ci-dessus peut également être facilement converti en étapes itératives à l'aide de boucles et de prise de décision.

Comme le tri par fusion récursif, le tri par fusion itératif a également une complexité O (nlogn), donc en termes de performances, ils fonctionnent au pair les uns avec les autres. Nous pouvons simplement réduire les frais généraux.

Dans ce didacticiel, nous nous sommes concentrés sur le tri de fusion récursif et ensuite, nous allons implémenter le tri de fusion récursif en utilisant les langages C ++ et Java.

Vous trouverez ci-dessous une implémentation de la technique de tri par fusion utilisant C ++.

#include using namespace std; void merge(int *,int, int , int ); void merge_sort(int *arr, int low, int high) { int mid; if (low num; cout<<'Enter '<myarray[i]; } merge_sort(myarray, 0, num-1); cout<<'Sorted array '; for (int i = 0; i < num; i++) { cout<

Production:

Saisissez le nombre d'éléments à trier: 10

Saisissez 10 éléments à trier: 101 10 2 43 12 54 34 64 89 76

Tableau trié

2 10 12 34 43 54 64 76 89101

Dans ce programme, nous avons défini deux fonctions, tri par fusion et aller . Dans la fonction merge_sort, nous divisons le tableau en deux tableaux égaux et appelons la fonction de fusion sur chacun de ces sous-tableaux. Dans la fonction de fusion, nous effectuons le tri réel sur ces sous-tableaux, puis les fusionnons en un seul tableau trié complet.

Ensuite, nous implémentons la technique Merge Sort en langage Java.

class MergeSort { void merge(int arr[], int beg, int mid, int end) { int left = mid - beg + 1; int right = end - mid; int Left_arr[] = new int [left]; int Right_arr[] = new int [right]; for (int i=0; i

Production:

Tableau d'entrée

101 10 2 43 12 54 34 64 89 76

Tableau trié à l'aide du tri par fusion

2 10 12 34 43 54 64 76 89101

Dans l'implémentation Java également, nous utilisons la même logique que celle utilisée dans l'implémentation C ++.

Le tri par fusion est un moyen efficace de trier les listes et est principalement utilisé pour trier les listes liées. Comme elle utilise une approche de division et de conquête, la technique de tri par fusion est aussi efficace pour les tableaux plus petits que plus grands.

Analyse de complexité de l'algorithme de tri par fusion

Nous savons que pour effectuer le tri à l'aide du tri par fusion, nous divisons d'abord le tableau en deux moitiés égales. Ceci est représenté par «log n» qui est une fonction logarithmique et le nombre de pas effectués est au maximum log (n + 1).

Ensuite, pour trouver l'élément central du tableau, nous avons besoin d'une seule étape, c'est-à-dire O (1).

Ensuite, pour fusionner les sous-tableaux en un tableau de n éléments, nous prendrons O (n) temps d'exécution.

Ainsi, le temps total pour effectuer le tri par fusion sera n (log n + 1), ce qui nous donne la complexité temporelle de O (n * logn).

Pire complexité temporelle des casO (n * log n)
Meilleure complexité temporelleO (n * log n)
Complexité temporelle moyenneO (n * log n)
Complexité spatialeSur)

La complexité temporelle du tri par fusion est la même dans les trois cas (pire, meilleur et moyen) car elle divise toujours le tableau en sous-tableaux, puis fusionne les sous-tableaux en prenant un temps linéaire.

Le tri par fusion prend toujours une quantité d'espace égale à celle des tableaux non triés. Par conséquent, lorsque la liste à trier est un tableau, le tri par fusion ne doit pas être utilisé pour les très grands tableaux. Cependant, le tri par fusion peut être utilisé plus efficacement pour le tri des listes liées.

Conclusion

Le tri par fusion utilise la stratégie «diviser et conquérir» qui divise le tableau ou la liste en de nombreux sous-tableaux et les trie individuellement, puis les fusionne en un tableau trié complet.

Le tri par fusion est plus rapide que les autres méthodes de tri et fonctionne également efficacement pour les tableaux plus petits et plus grands.

Nous en explorerons plus sur le tri rapide dans notre prochain tutoriel!

=> Regardez le guide de formation C ++ pour débutants ici.

lecture recommandée

^