Meny

Slå ihop sortering i C ++ med exempel

merge sort c with examples

Prova Vårt Instrument För Att Eliminera Problem

C ++ Merge Sort Technique.

Algoritmen för sorteringssorter använder “ söndra och erövra ”Strategi där vi delar upp problemet i delproblem och löser dessa delproblem individuellt.

Dessa delproblem kombineras eller slås sedan samman för att bilda en enhetlig lösning.

=> Läs igenom den populära C ++ träningsserien här.

Slå ihop sortering

Vad du kommer att lära dig:

vad är betatestning och hur används det?

Översikt

Sammanfoga sortering utförs med följande steg:

# 1) Listan som ska sorteras är uppdelad i två grupper av lika längd genom att dela listan på mittelementet. Om antalet element i listan antingen är 0 eller 1, anses listan vara sorterad.

#två) Varje underlista sorteras individuellt med hjälp av sammanslagningssortering rekursivt.

# 3) De sorterade underlistorna kombineras eller slås sedan samman för att bilda en komplett sorterad lista.

Allmän algoritm

Den allmänna pseudokoden för sammanslagningstekniken ges nedan.

Förklara en matris Arr av längd N
Om N = 1 är Arr redan sorterad
Om N> 1,
Vänster = 0, höger = N-1
Hitta mitten = (vänster + höger) / 2
Ring merge_sort (Arr, vänster, mitt) => sortera första halvlek rekursivt
Ring merge_sort (Arr, mitten + 1, höger) => sortera andra halvan rekursivt
Ring samman (Arr, vänster, mitten, höger) för att slå samman sorterade matriser i ovanstående steg.
Utgång

Som visas i ovanstående pseudokod delar vi i sammanslagningssorteringsalgoritmen matrisen i hälften och sorterar varje halva med hjälp av sammanslagningssortering rekursivt. När undergrupper har sorterats individuellt slås de två undergrupperna samman för att bilda en komplett sorterad matris.

Pseudokod för sammanslagningssortering

Följande är pseudokoden för merge sort-teknik. Först har vi en procedur sammanslagningssortering för att dela upp arrayen i halvor rekursivt. Sedan har vi en sammanslagningsrutin som slår samman de sorterade mindre matriserna för att få en komplett sorterad matris.

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

Låt oss nu illustrera sammanslagningssorteringstekniken med ett exempel.

Illustration

sammanfoga sortera Illustration

Ovanstående illustration kan visas i tabellform nedan:

PasseraOsorterad listadela uppSorterad lista
1{12, 23,2,43,51,35,19,4}{12,23,2,43}
{51,35,19,4}		{}
två{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}

Såsom visas i ovanstående representation delas arrayen först i två undergrupper med längd 4. Varje undergrupp delas vidare upp i ytterligare två undergrupper med längd 2. Varje undergrupp delas sedan vidare i en undergrupp av ett element vardera. Hela denna process är 'Divide' -processen.

När vi väl har delat upp matrisen i underarrangemang för ett enda element vardera, måste vi nu slå samman dessa matriser i sorterad ordning.

Som visas i illustrationen ovan betraktar vi varje undergrupp av ett enda element och kombinerar först elementen för att bilda undergrupper av två element i sorterad ordning. Därefter sorteras de sorterade undergrupperna av längd två och kombineras för att bilda två undergrupper med längden fyra vardera. Sedan kombinerar vi dessa två underarrayer för att bilda en komplett sorterad matris.

Iterativ sammanslagningssortering

Algoritmen eller tekniken för sammanslagningssortering som vi har sett ovan använder rekursion. Det är också känt som “ rekursiv sammanslagningssortering ”.

Vi vet att rekursiva funktioner använder funktionssamtalstack för att lagra det mellanliggande tillståndet för samtalsfunktionen. Den lagrar också annan bokföringsinformation för parametrar etc. och poserar över huvudet när det gäller att lagra aktiveringsposten för att anropa funktionen samt återuppta körningen.

Alla dessa omkostnader kan bli av med om vi använder iterativa funktioner istället för rekursiva. Ovanstående sorteringsalgoritm kan också enkelt konverteras till iterativa steg med hjälp av loopar och beslutsfattande.

Liksom rekursiv sammanslagningssortering har iterativ sammanslagningssortering också O (nlogn) -komplexitet, och därmed prestationsmässigt, de utför i nivå med varandra. Vi kan helt enkelt sänka omkostnaderna.

I denna handledning har vi koncentrerat oss på rekursiv sammanslagningssortering och nästa kommer vi att implementera rekursiv sammanslagningssortering med C ++ och Java-språk.

Nedan följer en implementering av merge sort-teknik med 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<

Produktion:

Ange antalet element som ska sorteras: 10

Ange 10 element som ska sorteras: 101 10 2 43 12 54 34 64 89 76

Sorterad matris

2 10 12 34 43 54 64 76 89 101

I detta program har vi definierat två funktioner, merge_sort och gå . I funktionen merge_sort delar vi matrisen i två lika matriser och kallar sammanslagningsfunktionen på var och en av dessa undermatriser. I sammanslagningsfunktion gör vi den faktiska sorteringen på dessa undermatriser och slår sedan samman dem i en komplett sorterad matris.

Därefter implementerar vi Merge Sort-tekniken 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

Produktion:

Inmatningsmatris

101 10 2 43 12 54 34 64 89 76

Array sorterad med merge sort

2 10 12 34 43 54 64 76 89 101

Även i Java-implementering använder vi samma logik som vi använde vid C ++ -implementering.

Sammanfoga sortering är ett effektivt sätt att sortera listor och används mest för att sortera länkade listor. Eftersom den använder en delnings- och erövringsstrategi, fungerar sammanslagningssorteringsteknik lika effektivt för mindre som större matriser.

Komplexitetsanalys av sammanslagningssorteringsalgoritmen

Vi vet att för att utföra sortering med merge sort, delar vi först arrayen i två lika stora halvor. Detta representeras av 'log n' som är en logaritmisk funktion och antalet steg som tagits är högst log (n + 1).

Nästa för att hitta mittelementet i matrisen kräver vi ett steg, dvs. O (1).

För att slå samman undermatriserna i en uppsättning n-element tar vi O (n) mängden körtid.

Således blir den totala tiden för att utföra sammanslagningssortering n (log n + 1), vilket ger oss tidskomplexiteten för O (n * logn).

Värsta fallets tidskomplexitetO (n * log n)
Komplexitet i bästa fallO (n * log n)
Genomsnittlig tidskomplexitetO (n * log n)
RymdkomplexitetPå)

Tidskomplexiteten för sammanslagningssortering är densamma i alla tre fall (värsta, bästa och genomsnittliga) eftersom den alltid delar upp matrisen i undermatriser och sedan sammanfogar undergrupperna med linjär tid.

Sammanfogningssortering tar alltid lika mycket utrymme som osorterade matriser. Därför när listan som ska sorteras är en matris, ska sortering av sammanslagning inte användas för mycket stora matriser. Sammanslagningssortering kan dock användas mer effektivt för sortering av länkade listor.

Slutsats

Sammanfoga sorterar använder 'dela och erövra' -strategin som delar upp matrisen eller listan i flera undermatriser och sorterar dem individuellt och smälter sedan samman i en komplett sorterad matris.

Merge sort fungerar snabbare än andra sorteringsmetoder och fungerar också effektivt för mindre och större arrays.

Vi kommer att utforska mer om Snabbsortering i vår kommande handledning!

=> Se upp för nybörjare C ++ träningsguide här.

Rekommenderad läsning

^