Meny

Flett sortering i C ++ med eksempler

merge sort c with examples

Prøv Instrumentet Vårt For Å Eliminere Problemer

C ++ Merge Sort Technique.

Flersorteringsalgoritme bruker “ splitt og hersk ”Strategi der vi deler problemet opp i delproblemer og løser disse underproblemene hver for seg.

Disse delproblemene kombineres eller slås sammen for å danne en enhetlig løsning.

=> Les gjennom den populære C ++ treningsserien her.

Slå sammen Sorter

Hva du vil lære:

hvordan lage en java-applikasjon i formørkelse

Oversikt

Flettesortering utføres ved hjelp av følgende trinn:

#1) Listen som skal sorteres, er delt inn i to matriser av samme lengde ved å dele listen på det midterste elementet. Hvis antall elementer i listen enten er 0 eller 1, anses listen som sortert.

#to) Hver underliste sorteres individuelt ved å bruke flettesorter rekursivt.

# 3) De sorterte underlistene kombineres eller flettes sammen for å danne en komplett sortert liste.

Generell algoritme

Den generelle pseudokoden for fusjonssorteringsteknikken er gitt nedenfor.

Erklær en matrise Arr med lengde N
Hvis N = 1, er Arr allerede sortert
Hvis N> 1,
Venstre = 0, høyre = N-1
Finn midten = (venstre + høyre) / 2
Ring merge_sort (Arr, venstre, midt) => sorter første halvdel rekursivt
Ring merge_sort (Arr, midten + 1, høyre) => sorter andre halvdel rekursivt
Ring sammen (Arr, venstre, midt, høyre) for å slå sammen sorterte matriser i trinnene ovenfor.
Exit

Som vist i den ovennevnte pseudokoden, deler vi i flettesorteringsalgoritmen matrisen i halvparten og sorterer hver halvdel ved hjelp av flettesorter rekursivt. Når underarrayer er sortert individuelt, blir de to underarrayene slått sammen for å danne en komplett sortert matrise.

Pseudokode for sammenslåing

Følgende er pseudokoden for sammenslåingsteknikk. Først har vi en fremgangsmåte for å slå sammen sortering for å dele opp matrisen i halvdeler rekursivt. Så har vi en sammenslåingsrutine som vil slå sammen de sorterte mindre matriser for å få et komplett sortert utvalg.

procedure mergesort( array,N ) array – list of elements to be sorted N – number of elements in the list begin if ( N == 1 ) return array var array1 as array = a[0] ... a[N/2] var array2 as array = a[N/2+1] ... a[N] array1 = mergesort(array1) array2 = mergesort(array2) return merge( array1, array2 ) end procedure procedure merge(array1, array2 ) array1 – first array array2 – second array begin var c as array while ( a and b have elements ) if ( array1[0] > array2[0] ) add array2 [0] to the end of c remove array2 [0] from array2 else add array1 [0] to the end of c remove array1 [0] from array1 end if end while while ( a has elements ) add a[0] to the end of c remove a[0] from a end while while ( b has elements ) add b[0] to the end of c remove b[0] from b end while return c end procedure

La oss nå illustrere fusjonssorteringsteknikken med et eksempel.

Illustrasjon

merge sort Illustrasjon

Illustrasjonen ovenfor kan vises i tabellform nedenfor:

SendeUsortert listedele oppSortert liste
en{12, 23,2,43,51,35,19,4}{12,23,2,43}
{51,35,19,4}		{}
to{12,23,2,43}
{51,35,19,4}		{12.23} {2.43}
{51.35} {19.4}		{}
3{12.23} {2.43}
{51.35} {19.4}		{12.23} {2.43}
{35.51} {4.19}		{12.23} {2.43}
{35.51} {4.19}
4{12.23} {2.43}
{35.51} {4.19}		{2,12,23,43}
{4,19,35,51}		{2,12,23,43}
{4,19,35,51}
5{2,12,23,43}
{4,19,35,51}		{2,4,12,19,23,35,43,51}{2,4,12,19,23,35,43,51}
6{}{}{2,4,12,19,23,35,43,51}

Som vist i den ovennevnte representasjon, er matrisen først delt inn i to underarrayer med lengde 4. Hver undergruppe er videre delt inn i to flere underarrayer med lengde 2. Hver undergruppe blir deretter ytterligere delt inn i en undergruppe av ett element hver. Hele denne prosessen er 'Divide' -prosessen.

Når vi har delt opp matrisen i underarrayer av hvert enkelt element hver, må vi nå slå sammen disse matriser i sortert rekkefølge.

Som vist i illustrasjonen ovenfor, vurderer vi hvert underarray av et enkelt element og kombinerer først elementene for å danne underarrayer av to elementer i sortert rekkefølge. Deretter sorteres de sorterte underarrayene av lengde to og kombineres for å danne to underarrayer av lengde fire hver. Deretter kombinerer vi disse to underarrayene for å danne en komplett sortert matrise.

Iterativ Merge Sort

Algoritmen eller teknikken for sammenslåingssortering vi har sett ovenfor, bruker rekursjon. Det er også kjent som “ rekursiv sammenslåingssortering ”.

Vi vet at rekursive funksjoner bruker funksjonsanropstak for å lagre den mellomliggende tilstanden til anropsfunksjonen. Den lagrer også annen bokføringsinformasjon for parametere osv. Og utgjør overhead når det gjelder lagring av aktiveringsregistrering for å ringe funksjonen, samt gjenoppta utførelsen.

Alle disse overheadene kan bli kvitt hvis vi bruker iterative funksjoner i stedet for rekursive. Ovennevnte flettesorteringsalgoritme kan også enkelt konverteres til iterative trinn ved hjelp av sløyfer og beslutningstaking.

I likhet med rekursiv sammenslåingssortering, har iterativ sammenslåingssortering også O (nlogn) kompleksitet, og dermed ytelsesmessig, de utfører på nivå med hverandre. Vi er ganske enkelt i stand til å senke overhead.

I denne opplæringen har vi konsentrert oss om rekursiv sammenslåingssortering, og neste gang vil vi implementere rekursiv sammenslåingssortering ved hjelp av C ++ og Java-språk.

Nedenfor er en implementering av sammenslåingssorteringsteknikk ved bruk av C ++.

#include using namespace std; void merge(int *,int, int , int ); void merge_sort(int *arr, int low, int high) { int mid; if (low num; cout<<'Enter '<myarray[i]; } merge_sort(myarray, 0, num-1); cout<<'Sorted array '; for (int i = 0; i < num; i++) { cout<

Produksjon:

Angi antall elementer som skal sorteres: 10

Skriv inn 10 elementer som skal sorteres: 101 10 2 43 12 54 34 64 89 76

Sortert utvalg

2 10 12 34 43 54 64 76 89 101

I dette programmet har vi definert to funksjoner, merge_sort og gå . I merge_sort-funksjonen deler vi matrisen i to like matriser og kalles sammenslåingsfunksjon på hver av disse underarrayene. I flettefunksjon gjør vi den faktiske sorteringen på disse underarrayene og slår dem sammen i en komplett sortert matrise.

Deretter implementerer vi Merge Sort-teknikken på Java-språk.

class MergeSort { void merge(int arr[], int beg, int mid, int end) { int left = mid - beg + 1; int right = end - mid; int Left_arr[] = new int [left]; int Right_arr[] = new int [right]; for (int i=0; i

Produksjon:

Input Array

101 10 2 43 12 54 34 64 89 76

Array sortert ved hjelp av flettesortering

2 10 12 34 43 54 64 76 89 101

Også i Java-implementering bruker vi samme logikk som vi brukte i C ++ implementering.

Slå sammen sortering er en effektiv måte å sortere lister på og brukes hovedsakelig til å sortere sammenkoblede lister. Ettersom den bruker en deling og erobring tilnærming, fungerer flettesorteringsteknikk like effektivt for mindre som større matriser.

Kompleksitetsanalyse av sammenslåingsalgoritmen

Vi vet at for å utføre sortering ved å bruke flettesortering, deler vi først matrisen i to like halvdeler. Dette representeres av 'log n', som er en logaritmisk funksjon og antall trinn som er tatt er log (n + 1) på det meste.

Neste for å finne det midterste elementet i matrisen krever vi enkelt trinn, dvs. O (1).

For å slå sammen underarrayene i en rekke n-elementer, tar vi O (n) mengde kjøretid.

Dermed vil den totale tiden for å utføre sammenslåingssortering være n (log n + 1), noe som gir oss tidskompleksiteten til O (n * logn).

Kompleksitet i verste fallO (n * log n)
Kompleksitet i beste tilfelleO (n * log n)
Gjennomsnittlig tidskompleksitetO (n * log n)
RomkompleksitetPå)

Tidskompleksiteten for sammenslåingssortering er den samme i alle tre tilfeller (verste, beste og gjennomsnittlige), da den alltid deler opp matrisen i underarrayer og deretter fletter underarrayene og tar lineær tid.

Flettesortering tar alltid like mye plass som usorterte matriser. Derfor, når listen som skal sorteres, er en matrise, bør flettesortering ikke brukes til veldig store matriser. Imidlertid kan flettesortering brukes mer effektivt for sortering av koblede lister.

Konklusjon

Merge sort bruker 'divide and conquer' -strategien som deler arrayet eller listen i flere underarrayer og sorterer dem individuelt og deretter smelter sammen i en komplett sortert array.

Merge sort fungerer raskere enn andre sorteringsmetoder og fungerer også effektivt for mindre og større arrays.

Vi vil utforske mer om Quick Sort i vår kommende opplæring!

=> Se opp nybegynnere C ++ treningsguide her.

Anbefalt lesing

^