Hur man implementerar Merge Sort i C ++ med exempel



Den här artikeln ger dig detaljerad och omfattande kunskap om Merge Sort i C ++, hur den fungerar med exempel.

Vad är sammanslagningen? Merge sort är en jämförelsebaserad sorteringsalgoritm som tillhör kategorin divide and conquer. Merge sort används för att sortera en matris baserad på delnings- och erövringsstrategin som kommer att behandlas kort i det här inlägget tillsammans med andra begrepp som dess algoritm med ett exempel. Vi kommer också att titta på tidskomplexiteten för sammanslagningssorteringen i C ++

Följande tips kommer att behandlas i den här artikeln,





Fortsätter med den här artikeln om Merge Sort i C ++

Dela och erövra algoritmen

Om du redan är bekant med hur quicksort fungerar kan du vara medveten om dela och erövra-strategin. Divide and Conquer innebär tre stora steg. För att förstå dessa steg, låt oss överväga en matris Hej [] med startindex 'a' och slutindex 'n', därför kan vi skriva vår matris på följande sätt Hej [a & hellip..n]



Dela - Det primära steget eller det främsta steget att dela och erövra är att dela upp det givna problemet i delproblem eller underdelar. Fångsten här är att delproblemen ska likna det ursprungliga problemet och vara mindre i storlek. I vårt fall delar vi vårt array i två halvor [a & hellip.m] [m + 1 & hellip..n] m ligger i mitten av ett och n-index

Conquer- När vi är klara att dela upp vårt problem i delproblem. Vi löser dessa delproblem rekursivt.

ködatastruktur i java

Kombinera - I det här steget kombinerar vi alla lösningar på våra delproblem på ett lämpligt sätt. Med andra ord kombinerar vi två olika sorterade matriser för att bilda en sorterad matris. Där har vi vårt sorterade utbud.



Fortsätter med den här artikeln om Merge Sort i C ++

Förstå algoritmen för sammanslagningssortering med ett exempel

Vid denna tidpunkt vet vi vilken metod som kommer att användas av sammanslagningssorteringen. Så, låt oss överväga ett exempel och gå igenom varje steg från Hello [] osorterat till en sorterad matris.
Exempel- Hej [10, 3, 7, 1, 15, 14, 9, 22]

Merge-sort-in-C++

I bilden ovan betraktade vi en osorterad array och använde merge sort för att få en sorterad array. Nu ska vi titta på varje steg och förstå hela algoritmen

1. Först betraktade vi en array Hej [10, 3, 7, 1, 15, 14, 9, 22] i denna array finns totalt 8 element

2. Som vi såg tidigare använder merge-sortering delnings- och erövringsmetoden för att sortera elementen. Vi hittade m som ligger i mitten av vårt array och delade vårt array från mitten där m = (a - n) / 2 'a' är indexet för elementet längst till vänster och n är indexet för elementet längst till höger i vårt array .

3. Efter den första divisionen har vi två delar bestående av fyra element vardera. Låt oss titta på den första halvan [10, 3, 7, 1].

4. Vi delar upp [10, 3, 7, 1] i 2 delar [10, 3] och [7, 1]. Därefter delar vi dem vidare i [10], [3], [7], [1]. Ytterligare uppdelning är inte möjlig eftersom vi inte kan beräkna m. en lista som innehåller ett enda element anses alltid vara sorterad.

5. Hur sker sammanslagning? Låt oss ta reda på. Först [10] och [3] jämförs och slås samman i stigande ordning [3, 10] på samma sätt som vi får [1, 7]

6. Därefter jämför vi [3, 10] och [1, 7]. En gång jämfört sammanfogar vi dem i stigande ordning och vi får [1, 3, 7, 10].

7. [15, 14, 9, 2] delas också upp och kombineras på liknande sätt för att bilda [9, 14, 15, 22].

hur man varnar i javascript

8. I det sista steget jämför vi och kombinerar [15, 14, 9, 2] [9, 14, 15, 22] för att ge oss vår sorterade matrisdvs [1, 3, 7, 9, 10, 14, 15, 22].

Fortsätter med den här artikeln om Merge Sort i C ++

Pseudokod för Merge Sort

Börja om vänster

Funktionen mergeSort () kallar sig rekursivt för att dela vår array tills den blir ett enda element och funktionsfusionen () används för att slå samman de sorterade matriserna.

Fortsätter med den här artikeln om Merge Sort i C ++

Slå ihop sorteringsprogram i C ++

#include #include #include med hjälp av namnutrymme std void merge (int a [], int Firstindex, int m, int Lastindex) // sammanfogar de underarrayer som skapas medan division void mergeSort (int a [], int Firstindex, int Lastindex) {if (Firstindexstorlek int Hej [storlek], jag cout<<'Enter the elements of the array one by one:n' for(i=0 i>Hej [i] mergeSort (Hej, 0, storlek - 1) cout<<'The Sorted List isn' for(i=0 i

Produktion-

Fortsätter med den här artikeln om Merge Sort i C ++

Tidskomplexitet

Tidskomplexitet är en viktig aspekt som ska beaktas när vi pratar om algoritmer. Sammanfogningssortering anses ha stor tidskomplexitet jämfört med andra sorteringsalgoritmer.

Värsta gångtid - O (n log n)
Bästa falltid - O (n log n)
Genomsnittlig körtid - O (n log n)

Med detta kommer vi till ett slut på denna Merge Sort in C ++ - artikel. Om du vill veta mer, kolla in av Edureka, ett pålitligt online-lärande företag. Edurekas Java J2EE- och SOA-utbildning och certifieringskurs är utformad för att träna dig för både grundläggande och avancerade Java-koncept tillsammans med olika Java-ramverk som Hibernate & Spring.

Har du en fråga till oss? Vänligen nämna det i kommentarsektionen på den här bloggen så kommer vi tillbaka till dig så snart som möjligt.