Comment implémenter le tri par fusion en C ++ avec des exemples



Cet article vous fournira une connaissance détaillée et complète de Merge Sort en C ++, comment cela fonctionne avec des exemples.

Quel est le tri de fusion? Le tri par fusion est un algorithme de tri basé sur la comparaison qui appartient à la catégorie diviser pour conquérir. Le tri par fusion est utilisé pour trier un tableau en fonction de la stratégie de division et de conquête qui sera brièvement abordée dans cet article avec d'autres concepts tels que son algorithme avec un exemple. Nous examinerons également la complexité temporelle du tri par fusion en C ++

Les pointeurs suivants seront traités dans cet article,





Passer à cet article sur le tri par fusion en C ++

Algorithme Divide and Conquer

Si vous connaissez déjà le fonctionnement du tri rapide, vous connaissez peut-être la stratégie de division pour vaincre. Divide and Conquer comporte trois étapes majeures. Pour comprendre ces étapes, considérons un tableau Hello [] ayant l’index de début «a» et l’index de fin «n», nous pouvons donc écrire notre tableau de la manière suivante Hello [a & hellip..n]



Diviser - Le premier mouvement ou la première étape de diviser pour conquérir est de diviser le problème donné en sous-problèmes ou sous-parties. Le hic ici est que les sous-problèmes doivent être similaires au problème d'origine et de plus petite taille. Dans notre cas, nous allons diviser notre tableau en 2 moitiés [a & hellip.m] [m + 1 & hellip..n] m se trouve au milieu d'un et n index

Conquérir - Une fois que nous avons fini de diviser notre problème en sous-problèmes. Nous résolvons ces sous-problèmes de manière récursive.

est une relation en java

Combiner - Dans cette étape, nous combinons toutes les solutions de nos sous-problèmes de manière appropriée. En d'autres termes, nous combinons 2 tableaux triés différents pour former un tableau trié. Là, nous avons notre tableau trié.



Passer à cet article sur le tri par fusion en C ++

Comprendre l'algorithme de tri par fusion avec un exemple

À ce stade, nous savons quelle approche sera utilisée par le tri par fusion. Prenons donc un exemple et parcourons chaque étape de Hello [] non trié à un tableau trié.
Exemple - Bonjour [10, 3, 7, 1, 15, 14, 9, 22]

Merge-sort-in-C++

Dans l'image ci-dessus, nous avons considéré un tableau non trié et utilisé le tri par fusion pour obtenir un tableau trié. Examinons maintenant chaque étape et comprenons l'ensemble de l'algorithme

1. Premièrement, nous avons considéré un tableau Hello [10, 3, 7, 1, 15, 14, 9, 22] dans ce tableau, il y a au total 8 éléments

2. Comme nous l'avons vu précédemment, le tri par fusion utilise l'approche de division et de conquête pour trier les éléments. Nous avons trouvé m qui se trouve au milieu de notre tableau et avons divisé notre tableau à partir du milieu où m = (a - n) / 2 'a' est l'indice de l'élément le plus à gauche et n est l'indice de l'élément le plus à droite de notre tableau .

programmation de socket tcp en java

3. Après la première division, nous avons 2 parties composées de 4 éléments chacune. Regardons la première moitié [10, 3, 7, 1].

4. Nous divisons [10, 3, 7, 1] en 2 parties [10, 3] et [7, 1]. Après cela, nous les divisons encore en [10], [3], [7], [1]. Une division supplémentaire n'est pas possible car nous ne pouvons pas calculer m. une liste contenant un seul élément est toujours considérée comme triée.

5. Comment se déroule la fusion? Découvrons-le. Les premiers [10] et [3] sont comparés et fusionnés par ordre croissant [3, 10] de la même manière que nous obtenons [1, 7]

6. Après cela, nous comparons [3, 10] et [1, 7]. Une fois comparés, nous les fusionnons par ordre croissant et nous obtenons [1, 3, 7, 10].

7. [15, 14, 9, 2] est également divisé et combiné de la même manière pour former [9, 14, 15, 22].

8. Dans la dernière étape, nous comparons et combinons [15, 14, 9, 2] [9, 14, 15, 22] pour nous donner notre tableau triéc'est-à-dire [1, 3, 7, 9, 10, 14, 15, 22].

Passer à cet article sur le tri par fusion en C ++

Pseudocode pour le tri par fusion

Commencer si à gauche

La fonction mergeSort () s'appelle récursivement pour diviser notre tableau jusqu'à ce qu'il devienne un élément unique et la fonction merge () est utilisée pour fusionner les tableaux triés.

Passer à cet article sur le tri par fusion en C ++

différence entre lancer et lancer

Programme de tri de fusion en C ++

#include #include #include using namespace std void merge (int a [], int Firstindex, int m, int Lastindex) // fusionne les sous-tableaux créés pendant la division void mergeSort (int a [], int Firstindex, int Lastindex) {if (Firstindexsize int Bonjour [size], i cout<<'Enter the elements of the array one by one:n' for(i=0 i>Bonjour [i] mergeSort (Bonjour, 0, taille - 1) cout<<'The Sorted List isn' for(i=0 i

Production-

Passer à cet article sur le tri par fusion en C ++

Complexité temporelle

La complexité temporelle est un aspect important à prendre en compte lorsque nous parlons d'algorithmes. Le tri par fusion est considéré comme ayant une grande complexité temporelle par rapport aux autres algorithmes de tri.

Temps de fonctionnement le plus défavorable - O (n log n)
Meilleur temps d'exécution des cas - O (n log n)
Durée de fonctionnement moyenne - O (n log n)

Avec cela, nous arrivons à la fin de cet article Merge Sort in C ++. Si vous souhaitez en savoir plus, consultez le par Edureka, une entreprise d'apprentissage en ligne de confiance. Le cours de formation et de certification Java J2EE et SOA d'Edureka est conçu pour vous former aux concepts Java de base et avancés ainsi qu'à divers frameworks Java tels que Hibernate et Spring.

Vous avez une question pour nous? Veuillez le mentionner dans la section commentaires de ce blog et nous vous répondrons dans les plus brefs délais.