Hvordan implementere Merge Sort i C ++ med eksempler



Denne artikkelen vil gi deg detaljert og omfattende kunnskap om Merge Sort i C ++, hvordan den fungerer med eksempler.

Hva er sammenslåingssorteringen? Merge sort er en sammenligningsbasert sorteringsalgoritme som tilhører deling og erobringskategorien. Merge sort brukes til å sortere en matrise basert på delings- og erobringsstrategien som kort vil bli dekket i dette innlegget sammen med andre konsepter som algoritmen med et eksempel. Vi vil også se på tidskompleksiteten til sammenslåingen i C ++

Følgende tips vil bli dekket i denne artikkelen,





Fortsetter med denne artikkelen om Merge Sort i C ++

Del og erobre algoritmen

Hvis du allerede er kjent med hvordan quicksort fungerer, kan du være klar over splitte og erobre strategien. Divide and Conquer innebærer tre store trinn. For å forstå disse trinnene, la oss vurdere en matrise Hallo [] som har startindeks 'a' og sluttindeks 'n', og derfor kan vi skrive matrisen vår på følgende måte



Del - Hovedtrekket eller hovedtrinnet for å dele og erobre er å dele det gitte problemet i underproblemer eller underdeler. Fangsten her er at delproblemene skal være lik det opprinnelige problemet og ha mindre størrelse. I vårt tilfelle vil vi dele matrisen vår i to halvdeler [a & hellip.m] [m + 1 & hellip..n] m ligger midt i a og n indeks

Conquer- Når vi er ferdige med å dele problemet vårt i delproblemer. Vi løser disse delproblemene rekursivt.

Kombinere - I dette trinnet kombinerer vi alle løsningene av underproblemene våre på en passende måte. Med andre ord kombinerer vi to forskjellige sorterte matriser for å danne en sortert matrise. Der har vi vårt sorterte utvalg.



Fortsetter med denne artikkelen om Merge Sort i C ++

Forstå sammenslåingsalgoritmen med et eksempel

På dette tidspunktet vet vi hvilken tilnærming som vil bli brukt av sammenslåingssorteringen. Så la oss se på et eksempel og gå gjennom hvert trinn fra Hello [] usortert til en sortert matrise.
Eksempel- Hei [10, 3, 7, 1, 15, 14, 9, 22]

java bryte ut av metoden

Merge-sort-in-C++

I bildet ovenfor betraktet vi en usortert matrise og brukte flettesortering for å få en sortert matrise. La oss nå se på hvert trinn og forstå hele algoritmen

1. Først betraktet vi en matrise Hei [10, 3, 7, 1, 15, 14, 9, 22] i denne matrisen er det totalt 8 elementer

2. Som vi så tidligere, kombinerer sortering delingen og erobrer tilnærmingen for å sortere elementene. Vi fant m som ligger midt i arrayet vårt og delte arrayet vårt fra midten der m = (a - n) / 2 'a' er indeksen til elementet til venstre og n er indeksen til elementet til høyre i vårt array .

3. Etter første divisjon har vi 2 deler bestående av 4 elementer hver. La oss se på første halvdel [10, 3, 7, 1].

4. Vi deler [10, 3, 7, 1] i 2 deler [10, 3] og [7, 1]. Etter det deler vi dem videre i [10], [3], [7], [1]. Ytterligere inndeling er ikke mulig da vi ikke kan beregne m. en liste som inneholder et enkelt element betraktes alltid som sortert.

5. Hvordan foregår sammenslåing? La oss finne det ut. Først [10] og [3] blir sammenlignet og slått sammen i stigende rekkefølge [3, 10] på samme måte som vi får [1, 7]

koblet og ikke-koblet transformasjon i informatica

6. Deretter sammenligner vi [3, 10] og [1, 7]. En gang sammenlignet slår vi dem sammen i stigende rekkefølge, og vi får [1, 3, 7, 10].

7. [15, 14, 9, 2] er også delt og kombinert på en lignende måte for å danne [9, 14, 15, 22].

8. I det siste trinnet sammenligner og kombinerer vi [15, 14, 9, 2] [9, 14, 15, 22] for å gi oss vårt sorterte utvalgdvs. [1, 3, 7, 9, 10, 14, 15, 22].

datastrukturer og algoritmer java

Fortsetter med denne artikkelen om Merge Sort i C ++

Pseudokode for flette sortering

Begynn hvis igjen

Funksjonen mergeSort () kaller seg rekursivt for å dele arrayet vårt til det blir et enkelt element og funksjonen merge () brukes til å slå sammen de sorterte matriser.

Fortsetter med denne artikkelen om Merge Sort i C ++

Slå sammen sorteringsprogram i C ++

#include #include #include ved å bruke navneområdet std void merge (int a [], int Firstindex, int m, int Lastindex) // fusjonerer underarrayene som opprettes mens divisjon void mergeSort (int a [], int Firstindex, int Lastindex) {if (Firstindexstørrelse int Hello [size], i cout<<'Enter the elements of the array one by one:n' for(i=0 i>Hei [i] mergeSort (Hei, 0, størrelse - 1) cout<<'The Sorted List isn' for(i=0 i

Produksjon-

Fortsetter med denne artikkelen om Merge Sort i C ++

Tidskompleksitet

Tidskompleksitet er et viktig aspekt som skal vurderes når vi snakker om algoritmer. Sammenslåing anses å ha stor tidskompleksitet sammenlignet med andre sorteringsalgoritmer.

Verste gangstid - O (n log n)
Beste kjøretid - O (n log n)
Gjennomsnittlig kjøretid - O (n log n)

Med dette kommer vi til en slutt på denne Merge Sort in C ++ - artikkelen. Hvis du ønsker å lære mer, sjekk ut av Edureka, et pålitelig online læringsfirma. Edurekas Java J2EE- og SOA-opplærings- og sertifiseringskurs er designet for å trene deg for både kjerne- og avanserte Java-konsepter sammen med forskjellige Java-rammer som Hibernate & Spring.

Har du et spørsmål til oss? Vennligst nevn det i kommentarfeltet på denne bloggen, så kommer vi tilbake til deg så snart som mulig.