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.
Ce que vous apprendrez:
déclaration de variables statiques en c ++
- Aperçu
- Algorithme général
- Pseudo code pour le tri par fusion
- Illustration
- Tri de fusion itératif
- Analyse de complexité de l'algorithme de tri par fusion
- Conclusion
- lecture recommandée
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é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
L'illustration ci-dessus peut être présentée sous forme de tableau ci-dessous:
Passe | Liste non triée | diviser | Liste 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 cas O (n * log n) Meilleure complexité temporelle O (n * log n) Complexité temporelle moyenne O (n * log n) Complexité spatiale Sur)
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
- Méthode MongoDB Sort () avec exemples
- Commande de tri Unix avec syntaxe, options et exemples
- Shell tri en C ++ avec des exemples
- Tri de tas en C ++ avec des exemples
- Sélection de tri en C ++ avec des exemples
- Tri à bulles en C ++ avec des exemples
- Tri par insertion en C ++ avec des exemples
- Tri rapide en C ++ avec des exemples