Sådan implementeres Merge Sort i C ++ med eksempler



Denne artikel giver dig en detaljeret og omfattende viden om Merge Sort i C ++, hvordan det fungerer med eksempler.

Hvad er fusionssorteringen? Flet sortering er en sammenligningsbaseret sorteringsalgoritme, der hører til kategorien opdele og erobre. Flettsortering bruges til at sortere en matrix baseret på opdelings- og erobringsstrategien, som kort vil blive dækket i dette indlæg sammen med andre begreber, såsom dens algoritme med et eksempel. Vi vil også se på tidskompleksiteten af ​​flettsorteringen i C ++

Følgende punkter vil blive dækket i denne artikel,





Fortsætter med denne artikel om Merge Sort i C ++

Opdel og erobre algoritme

Hvis du allerede er bekendt med, hvordan quicksort fungerer, er du muligvis opmærksom på skillelinjen og erobringsstrategien. Divide and Conquer involverer tre store trin. For at forstå disse trin, lad os overveje en matrix Hej [] med startindeks 'a' og afslutningsindeks 'n', og derfor kan vi skrive vores matrix på følgende måde Hej [a & hellip..n]



Opdel - Det primære træk eller det primære trin for opdeling og erobring er at opdele det givne problem i underproblemer eller underdele. Fangsten her er, at delproblemerne skal svare til det oprindelige problem og have mindre størrelse. I vores tilfælde deler vi vores array i 2 halvdele [a & hellip.m] [m + 1 & hellip..n] m ligger midt i et og n-indeks

Conquer- Når vi er færdige med at opdele vores problem i delproblemer. Vi løser disse delproblemer rekursivt.

Kombiner - I dette trin kombinerer vi alle løsningerne på vores underproblemer på en passende måde. Med andre ord kombinerer vi 2 forskellige sorterede arrays for at danne et sorteret array. Der har vi vores sorterede array.



Fortsætter med denne artikel om Merge Sort i C ++

Forstå flettsorteringsalgoritmen med et eksempel

På dette tidspunkt ved vi, hvilken tilgang der vil blive brugt af fusionssorteringen. Så lad os overveje et eksempel og gennemgå hvert trin fra Hej [] usorteret til et sorteret array.
Eksempel- Hej [10, 3, 7, 1, 15, 14, 9, 22]

Merge-sort-in-C++

I ovenstående billede betragtede vi et usorteret array og brugte merge sort for at opnå et sorteret array. Lad os nu se på hvert trin og forstå hele algoritmen

1. For det første betragtede vi en matrix Hej [10, 3, 7, 1, 15, 14, 9, 22] i denne matrix er der i alt 8 elementer

dataindvinding c ++

2. Som vi så tidligere, fusionerer sort bruger divide and conquer tilgangen til at sortere elementerne. Vi fandt m, der ligger midt i vores array og delte vores array fra midten, hvor m = (a - n) / 2 'a' er indekset for det venstre element og n er indekset for det højre element i vores array .

3. Efter den første division har vi to dele bestående af 4 elementer hver. Lad os se på første halvdel [10, 3, 7, 1].

4. Vi deler [10, 3, 7, 1] i 2 dele [10, 3] og [7, 1]. Derefter opdeler vi dem yderligere i [10], [3], [7], [1]. Yderligere opdeling er ikke mulig, da vi ikke kan beregne m. en liste, der indeholder et enkelt element, betragtes altid som sorteret.

5. Hvordan foregår fusion? Lad os finde ud af det. Første [10] og [3] sammenlignes og flettes i stigende rækkefølge [3, 10] på samme måde som vi får [1, 7]

6. Derefter sammenligner vi [3, 10] og [1, 7]. Når de er sammenlignet, fusionerer vi dem i stigende rækkefølge, og vi får [1, 3, 7, 10].

7. [15, 14, 9, 2] er også opdelt og kombineret på en lignende måde til form [9, 14, 15, 22].

8. I det sidste trin sammenligner og kombinerer vi [15, 14, 9, 2] [9, 14, 15, 22] for at give os vores sorterede matrixdvs. [1, 3, 7, 9, 10, 14, 15, 22].

Fortsætter med denne artikel om Merge Sort i C ++

Pseudokode til flettsortering

Begynd hvis venstre

Funktionen mergeSort () kalder sig selv rekursivt til at opdele vores array, indtil det bliver et enkelt element, og funktionen merge () bruges til at flette de sorterede arrays.

Fortsætter med denne artikel om Merge Sort i C ++

Flet sorteringsprogram i C ++

#include #include #include ved hjælp af namespace std void merge (int a [], int Firstindex, int m, int Lastindex) // fusionerer de underarrays, der oprettes, mens division ugyldig mergeSort (int a [], int Firstindex, int Lastindex) {if (Firstindexstørrelse int Hej [størrelse], jeg cout<<'Enter the elements of the array one by one:n' for(i=0 i>Hej [i] mergeSort (Hej, 0, størrelse - 1) cout<<'The Sorted List isn' for(i=0 i

Produktion-

Fortsætter med denne artikel om Merge Sort i C ++

Tidskompleksitet

Tidskompleksitet er et vigtigt aspekt, der skal overvejes, når vi taler om algoritmer. Flettsortering anses for at have stor tidskompleksitet sammenlignet med andre sorteringsalgoritmer.

Worst-case driftstid - O (n log n)
Bedste driftstid - O (n log n)
Gennemsnitlig køretid - O (n log n)

Med dette kommer vi til en afslutning på denne Merge Sort i C ++ - artikel. Hvis du ønsker at lære mere, skal du tjekke af Edureka, et pålideligt online læringsfirma. Edurekas Java J2EE- og SOA-uddannelses- og certificeringskursus er designet til at træne dig til både kerne- og avancerede Java-koncepter sammen med forskellige Java-rammer som Hibernate & Spring.

Har du et spørgsmål til os? Nævn det i kommentarsektionen på denne blog, og vi vender tilbage til dig hurtigst muligt.