Innehållsförteckning
- Introduktion
- Vad är Merge Sort i C++
- Dela och erövra tillvägagångssätt
- Slå samman sorteringsalgoritm
- Implementering av Merge Sort i C++
- Slutsats
1. Introduktion
Sorteringsalgoritmer inom datavetenskap används för att ordna data i stigande eller fallande ordning. Det finns flera sorteringsalgoritmer med distinkta egenskaper tillgängliga. Merge sort är en av metoderna i C++ som kan sortera arrayerna.
2. Vad är Merge Sort i C++
Merge sort använder dela-och-härska-tekniken som kan ordna elementen i en array. Det kan också sortera listan med element i C++. Den delar upp inmatningen i två halvor, sorterar varje halva oberoende och slår sedan samman dem i rätt ordning.
3. Dela och erövra strategi
Sorteringsalgoritmen tillämpar en dela-och-härska-strategi, som innebär att inmatningsmatrisen partitioneras i mindre subarrayer, lösa dem separat och sedan slå samman resultaten för att producera en sorterad utdata. I fallet med merge-sort delas arrayen rekursivt i två halvor tills endast ett element finns kvar i varje halva.
4. Sammanfoga sorteringsalgoritm
Algoritmen för sammanslagning består av två huvudsteg: dividera och sammanfoga. Stegen är som följer:
4.1 Dela
Algoritmen för sammanslagning följer en dela-och-härska-strategi för att sortera element i en array.
- Det första steget i algoritmen kommer att kontrollera arrayelement. Om det innehåller ett element anses det redan vara sorterat, och algoritmen kommer att returnera samma array utan någon förändring.
- Om matrisen innehåller mer än ett element fortsätter algoritmen att dela upp den i två halvor: den vänstra halvan och den högra halvan.
- Algoritmen för sammanslagningssortering appliceras sedan rekursivt på den vänstra och högra halvan av arrayen, vilket effektivt delar upp dem i mindre underarrayer och sorterar dem individuellt.
- Denna rekursiva process fortsätter tills subarrayerna endast innehåller ett element vardera (enligt steg 1), vid vilken punkt de kan slås samman för att producera en slutlig, sorterad utmatris.
4.2 Sammanfoga
Nu kommer vi att se stegen för att slå samman arrayerna:
- Det första steget för sammanslagningssorteringsalgoritmen innebär att skapa en tom array.
- Algoritmen fortsätter sedan med att jämföra de första elementen i den vänstra och högra halvan av inmatningsmatrisen.
- Det minsta av de två elementen läggs till i den nya matrisen och tas sedan bort från dess respektive halva av inmatningsmatrisen.
- Steg 2-3 upprepas sedan tills en av halvorna är tömd.
- Eventuella återstående element i den icke-tomma halvan läggs sedan till i den nya arrayen.
- Den resulterande matrisen är nu helt sorterad och representerar den slutliga utmatningen av sammanslagningssorteringsalgoritmen.
5. Implementering av Merge Sort i C++
För att implementera merge sort i C++ följs två olika metoder. Tidskomplexiteten för båda metoderna är likvärdig, men deras användning av tillfälliga subarrayer skiljer sig åt.
Den första metoden för sammanslagningssorteringen i C++ använder två temporära subarrayer, medan den andra bara använder en. Det är värt att notera att den totala storleken på de två temporära subarrayerna i den första metoden är lika med storleken på den ursprungliga arrayen i den andra metoden, så rymdkomplexiteten förblir konstant.
Metod 1 – Användning av två temporära subarrayer
Här är ett exempelprogram för merge sort i C++ med metod 1, som använder två temporära subarrays:
#includeanvänder namnutrymme std ;
tomhet sammanfoga ( int arr [ ] , int l , int m , int r )
{
int n1 = m - l + 1 ;
int n2 = r - m ;
int L [ n1 ] , R [ n2 ] ;
för ( int i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ l + i ] ;
för ( int j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
int i = 0 , j = 0 , k = l ;
medan ( i < n1 && j < n2 ) {
om ( L [ i ] <= R [ j ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
annan {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
medan ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
medan ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
tomhet slå sammanSortera ( int arr [ ] , int l , int r )
{
om ( l < r ) {
int m = l + ( r - l ) / 2 ;
slå sammanSortera ( arr , l , m ) ;
slå sammanSortera ( arr , m + 1 , r ) ;
sammanfoga ( arr , l , m , r ) ;
}
}
int huvud ( )
{
int arr [ ] = { 12 , elva , 13 , 5 , 6 , 7 } ;
int arr_size = storlek av ( arr ) / storlek av ( arr [ 0 ] ) ;
cout << 'Given array är \n ' ;
för ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
slå sammanSortera ( arr , 0 , arr_size - 1 ) ;
cout << ' \n Sorterad array är \n ' ;
för ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
lämna tillbaka 0 ;
}
I det här programmet tar sammanslagningsfunktionen tre argument arr, l och r, som representerar arrayen som ska sorteras och visar indexen för underarrayen som behöver slås samman. Funktionen hittar först storlekarna på de två subarrayerna som ska slås samman, och skapar sedan två temporära subarrayer L och R för att lagra elementen i dessa subarrayer. Den jämför sedan elementen i L och R och slår samman dem till den ursprungliga namngivna arrayen arr i stigande ordning.
Dela-och-härska-tekniken används av mergeSort-funktionen för att dela upp arrayen i två halvor rekursivt tills det bara finns ett element kvar i underarrayen. Den slår sedan samman de två subarrayerna till en sorterad subarray. Funktionen fortsätter att slå samman subarrayerna såvida den inte sorterar hela arrayen.
I huvudfunktionen definierar vi en array arr med 6 element och anropar mergeSort-funktionen för att sortera den. I slutet av koden skrivs den sorterade matrisen ut.
Metod 2 – Använda en Temp Subarray
Här är ett exempelprogram för merge-sort i C++ med metod 2, som använder en enda temporär subarray:
#includeanvänder namnutrymme std ;
tomhet sammanfoga ( int arr [ ] , int l , int m , int r )
{
int i , j , k ;
int n1 = m - l + 1 ;
int n2 = r - m ;
// Skapa tillfälliga subarrayer
int L [ n1 ] , R [ n2 ] ;
// Kopiera data till subarrays
för ( i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ l + i ] ;
för ( j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
// Slå ihop de temporära subarrayerna tillbaka till den ursprungliga arrayen
i = 0 ;
j = 0 ;
k = l ;
medan ( i < n1 && j < n2 ) {
om ( L [ i ] <= R [ j ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
annan {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
// Kopiera de återstående elementen i L[]
medan ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
// Kopiera de återstående elementen i R[]
medan ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
tomhet slå sammanSortera ( int arr [ ] , int l , int r )
{
om ( l < r ) {
int m = l + ( r - l ) / 2 ;
// Sortera vänster och höger halvor rekursivt
slå sammanSortera ( arr , l , m ) ;
slå sammanSortera ( arr , m + 1 , r ) ;
// Slå samman de två sorterade halvorna
sammanfoga ( arr , l , m , r ) ;
}
}
int huvud ( )
{
int arr [ ] = { 12 , elva , 13 , 5 , 6 , 7 } ;
int arr_size = storlek av ( arr ) / storlek av ( arr [ 0 ] ) ;
cout << 'Given array är \n ' ;
för ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
slå sammanSortera ( arr , 0 , arr_size - 1 ) ;
cout << ' \n Sorterad array är \n ' ;
för ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
lämna tillbaka 0 ;
}
Det här programmet är som det föregående, men istället för att använda två temporära subarrays L och R, använder det en enda temporär subarraytemp. Merge-funktionen fungerar på samma sätt som tidigare, men istället för att kopiera data till L och R, kopierar den till temp. Den slår sedan samman temp array-element tillbaka till arr som är den ursprungliga arrayen.
MergeSort-funktionen är densamma som tidigare, förutom att den använder temp istället för L och R för att lagra den tillfälliga subarrayen.
I huvudfunktionen definierar vi en array arr med 6 element och anropar mergeSort-funktionen för att sortera den. Kodexekveringen avslutas med att den sorterade arrayen skrivs ut på skärmen.
Slutsats
Merge sort är en algoritm som sorterar arrayelement, och den använder dela-och-härska-tekniken och gör jämförelser mellan element. Merge sort i C++ har en tidskomplexitet på O(n log n) och är särskilt effektiv för att sortera stora arrayer. Även om det kräver ytterligare minne för att lagra de sammanslagna subarrayerna, gör dess stabilitet det till ett populärt val för sortering.