Hoe Merge Sort in C ++ te implementeren met voorbeelden

Wat is de samenvoegsortering? Samenvoegsortering is een op vergelijkingen gebaseerd sorteeralgoritme dat tot de categorie verdeel en heers behoort. Samenvoegsortering wordt gebruikt om een ​​array te sorteren op basis van de verdeel en heersstrategie die in dit bericht kort wordt behandeld, samen met andere concepten, zoals het algoritme met een voorbeeld. We zullen ook kijken naar de tijdcomplexiteit van het samenvoegen in C ++

De volgende tips komen in dit artikel aan bod:

• Verdeel en heers-algoritme
• Inzicht in het sorteeralgoritme samenvoegen met een voorbeeld
• Pseudocode voor samenvoegsortering
• Programma in C ++ voor samenvoegen sorteren
• De tijdcomplexiteit voor samenvoegsortering

Verder gaan met dit artikel over Merge Sort in C ++

Verdeel en heers-algoritme

Als je al bekend bent met hoe quicksort werkt, ben je misschien op de hoogte van de verdeel en heersstrategie. Verdeel en heers omvat drie grote stappen. Om deze stappen te begrijpen, laten we eens kijken naar een array Hallo [] met startindex ‘a’ en eindindex ‘n’. Daarom kunnen we onze array op de volgende manier schrijven Hallo [a & hellip..n]

Verdeel- De belangrijkste zet of de belangrijkste stap van verdeel en heers is het opdelen van het gegeven probleem in subproblemen of subdelen. De vangst hier is dat de subproblemen vergelijkbaar moeten zijn met het oorspronkelijke probleem en kleiner van omvang. In ons geval zullen we onze array in 2 helften verdelen [a & hellip.m] [m + 1 & hellip..n] m ligt in het midden van a en n index

Veroveren - Als we klaar zijn met het verdelen van ons probleem in deelproblemen. We lossen deze deelproblemen recursief op.

verschil tussen css en css3

Combineren- In deze stap combineren we alle oplossingen van onze deelproblemen op een passende manier. Met andere woorden, we combineren 2 verschillende gesorteerde arrays om één gesorteerde array te vormen. Daar hebben we onze gesorteerde reeks.

Verder gaan met dit artikel over Merge Sort in C ++

Inzicht in het samenvoegsorteeralgoritme aan de hand van een voorbeeld

Op dit punt weten we welke benadering zal worden gebruikt door de samenvoegsortering. Laten we dus een voorbeeld bekijken en elke stap doorlopen, van Hallo [] ongesorteerd tot een gesorteerde array.
Voorbeeld: Hallo [10, 3, 7, 1, 15, 14, 9, 22]

In de bovenstaande afbeelding hebben we een ongesorteerde array overwogen en samenvoegsortering gebruikt om een ​​gesorteerde array te verkrijgen. Laten we nu naar elke stap kijken en het hele algoritme begrijpen

1. We hebben eerst een array beschouwd Hallo [10, 3, 7, 1, 15, 14, 9, 22] in deze array zijn er in totaal 8 elementen

2. Zoals we eerder zagen, gebruikt samenvoegen sorteren de verdeel en heers benadering om de elementen te sorteren. We vonden m die in het midden van onze array ligt en verdeelden onze array vanuit het midden, waarbij m = (a - n) / 2 'a' de index is van het meest linkse element en n de index is van het meest rechtse element van onze array .

3. Na de eerste indeling hebben we 2 delen die elk uit 4 elementen bestaan. Laten we eens kijken naar de eerste helft [10, 3, 7, 1].

4. We verdelen [10, 3, 7, 1] in 2 delen [10, 3] en [7, 1]. Daarna verdelen we ze verder in [10], [3], [7], [1]. Verdere deling is niet mogelijk omdat we m niet kunnen berekenen. een lijst met een enkel element wordt altijd als gesorteerd beschouwd.

5. Hoe vindt het samenvoegen plaats? Laten wij het uitzoeken. De eerste [10] en [3] worden vergeleken en samengevoegd in oplopende volgorde [3, 10] op dezelfde manier waarop we [1, 7] krijgen

6. Daarna vergelijken we [3, 10] en [1, 7]. Eenmaal vergeleken voegen we ze samen in oplopende volgorde en krijgen we [1, 3, 7, 10].

7. [15, 14, 9, 2] wordt ook op dezelfde manier verdeeld en gecombineerd om [9, 14, 15, 22] te vormen.

8. In de laatste stap vergelijken en combineren we [15, 14, 9, 2] [9, 14, 15, 22] om ons onze gesorteerde reeks te gevendat wil zeggen [1, 3, 7, 9, 10, 14, 15, 22].

Verder gaan met dit artikel over Merge Sort in C ++

Pseudocode voor samenvoegsortering

Begin als je weg bent
De functie mergeSort () roept zichzelf recursief op om onze array te verdelen totdat het een enkel element wordt en de functie merge () wordt gebruikt om de gesorteerde arrays samen te voegen.
  Verder gaan met dit artikel over Merge Sort in C ++
 Voeg sorteerprogramma samen in C ++ 
#include #include #include met gebruik van namespace std void merge (int a [], int Firstindex, int m, int Lastindex) // voegt de sub-arrays samen die zijn gemaakt terwijl divisie void mergeSort (int a [], int Firstindex, int Lastindex) {if (Firstindexsize int Hallo [size], ik cout<<'Enter the elements of the array one by one:n' for(i=0 i>Hallo [i] mergeSort (Hallo, 0, maat - 1) cout<<'The Sorted List isn' for(i=0 i
 Uitgang 
Verder gaan met dit artikel over Merge Sort in C ++
 Tijdscomplexiteit 
Tijdscomplexiteit is een belangrijk aspect waarmee we rekening moeten houden als we het hebben over algoritmen. Samenvoegsortering wordt beschouwd als een grote tijdscomplexiteit in vergelijking met andere sorteeralgoritmen.
Looptijd in het slechtste geval - O (n log n) 
Best case looptijd - O (n log n) 
Gemiddelde looptijd - O (n log n)
Hiermee komen we aan het einde van dit Merge Sort in C ++ -artikel. Als je meer wilt weten, bekijk dan de   door Edureka, een vertrouwd online leerbedrijf. Edureka's Java J2EE- en SOA-trainings- en certificeringscursus is ontworpen om u te trainen in zowel kern- als geavanceerde Java-concepten, samen met verschillende Java-frameworks zoals Hibernate & Spring.
 Heeft u een vraag voor ons? Vermeld het in het opmerkingengedeelte van deze blog en we nemen zo snel mogelijk contact met je op.