Indholdsfortegnelse
- Introduktion
- Hvad er Merge Sort i C++
- Del og hersk tilgang
- Flet sorteringsalgoritme
- Implementering af Merge Sort i C++
- Konklusion
1. Introduktion
Sorteringsalgoritmer i datalogi bruges til at arrangere data i stigende eller faldende rækkefølge. Der er flere sorteringsalgoritmer med forskellige egenskaber tilgængelige. Merge sort er en af metoderne i C++, som kan sortere arrays.
2. Hvad er Merge Sort i C++
Merge sort bruger opdel-og-hersk-teknikken, der kan arrangere elementerne i en matrix. Det kan også sortere listen over elementer i C++. Den opdeler inputtet i to halvdele, sorterer hver halvdel uafhængigt og flettes derefter sammen i den rigtige rækkefølge.
3. Del og hersk tilgang
Sorteringsalgoritmen anvender en divide-and-conquer-strategi, som indebærer opdeling af input-arrayet i mindre subarrays, løse dem separat og derefter flette resultaterne for at producere et sorteret output. I tilfælde af flettesortering opdeles arrayet rekursivt i to halvdele, indtil der kun er et element tilbage i hver halvdel.
4. Flet sorteringsalgoritme
Fletsorteringsalgoritmen består af to hovedtrin: divider og flet. Trinene er som følger:
4.1 Opdel
Fletningssorteringsalgoritmen følger en opdel-og-hersk-strategi til sortering af elementer i et array.
- Det første trin i algoritmen vil kontrollere array-elementer. Hvis det indeholder et element, betragtes det allerede som sorteret, og algoritmen vil returnere det samme array uden nogen ændring.
- Hvis arrayet indeholder mere end ét element, fortsætter algoritmen med at opdele det i to halvdele: den venstre halvdel og den højre halvdel.
- Merge-sorteringsalgoritmen anvendes derefter rekursivt til venstre og højre halvdel af arrayet, og opdeler dem effektivt i mindre underarrays og sorterer dem individuelt.
- Denne rekursive proces fortsætter, indtil underarrayerne kun indeholder ét element hver (i henhold til trin 1), på hvilket tidspunkt de kan slås sammen for at producere et endeligt, sorteret output-array.
4.2 Flet sammen
Nu vil vi se trinene til at flette arrays:
- Det første trin for flettesorteringsalgoritmen involverer oprettelse af et tomt array.
- Algoritmen fortsætter derefter med at sammenligne de første elementer i venstre og højre halvdel af input-arrayet.
- Det mindste af de to elementer føjes til det nye array og fjernes derefter fra dets respektive halvdel af input-arrayet.
- Trin 2-3 gentages derefter, indtil en af halvdelene er tømt.
- Eventuelle resterende elementer i den ikke-tomme halvdel tilføjes derefter til det nye array.
- Det resulterende array er nu fuldt sorteret og repræsenterer det endelige output fra flettesorteringsalgoritmen.
5. Implementering af Merge Sort i C++
For at implementere merge sort i C++ følges to forskellige metoder. Tidskompleksiteten af begge metoder er ækvivalent, men deres brug af midlertidige subarrays er forskellig.
Den første metode til flettesorteringen i C++ bruger to midlertidige subarrays, mens den anden kun bruger én. Det er værd at bemærke, at den samlede størrelse af de to midlertidige subarrays i den første metode er lig med størrelsen af den originale array i den anden metode, så pladskompleksiteten forbliver konstant.
Metode 1 - Brug af to Temp-underpaneler
Her er et eksempelprogram til flettesortering i C++ ved hjælp af metode 1, som bruger to midlertidige underarrays:
#includebruger navneområde std ;
ugyldig fusionere ( int arr [ ] , int l , int m , int r )
{
int n1 = m - l + 1 ;
int n2 = r - m ;
int L [ n1 ] , R [ n2 ] ;
til ( int jeg = 0 ; jeg < n1 ; jeg ++ )
L [ jeg ] = arr [ l + jeg ] ;
til ( int j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
int jeg = 0 , j = 0 , k = l ;
mens ( jeg < n1 && j < n2 ) {
hvis ( L [ jeg ] <= R [ j ] ) {
arr [ k ] = L [ jeg ] ;
jeg ++;
}
andet {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
mens ( jeg < n1 ) {
arr [ k ] = L [ jeg ] ;
jeg ++;
k ++;
}
mens ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
ugyldig fletteSortér ( int arr [ ] , int l , int r )
{
hvis ( l < r ) {
int m = l + ( r - l ) / 2 ;
fletteSortér ( arr , l , m ) ;
fletteSortér ( arr , m + 1 , r ) ;
fusionere ( arr , l , m , r ) ;
}
}
int vigtigste ( )
{
int arr [ ] = { 12 , elleve , 13 , 5 , 6 , 7 } ;
int arr_size = størrelse på ( arr ) / størrelse på ( arr [ 0 ] ) ;
cout << 'Given matrix er \n ' ;
til ( int jeg = 0 ; jeg < arr_size ; jeg ++ )
cout << arr [ jeg ] << ' ' ;
fletteSortér ( arr , 0 , arr_size - 1 ) ;
cout << ' \n Sorteret array er \n ' ;
til ( int jeg = 0 ; jeg < arr_size ; jeg ++ )
cout << arr [ jeg ] << ' ' ;
Vend tilbage 0 ;
}
I dette program tager flettefunktionen tre argumenter arr, l og r, som repræsenterer det array, der skal sorteres, og viser indekserne for underarrayet, der skal flettes. Funktionen finder først størrelserne på de to underarrays, der skal flettes, og opretter derefter to midlertidige underarrays L og R for at gemme elementerne i disse underarrays. Den sammenligner derefter elementerne i L og R og fusionerer dem til det oprindelige navngivne array arr i stigende rækkefølge.
Opdel-og-hersk-teknikken anvendes af funktionen MergeSort til at opdele arrayet i to halvdele rekursivt, indtil der kun er ét element udeladt i underarrayet. Den fletter derefter de to subarrays til et sorteret subarray. Funktionen fortsætter med at flette undergrupperne, medmindre den sorterer hele arrayet.
I hovedfunktionen definerer vi en array arr med 6 elementer og kalder funktionen mergeSort for at sortere den. I slutningen af koden udskrives det sorterede array.
Metode 2 - Brug af One Temp Subarray
Her er et eksempelprogram til flettesortering i C++ ved hjælp af metode 2, som bruger en enkelt midlertidig subarray:
#includebruger navneområde std ;
ugyldig fusionere ( int arr [ ] , int l , int m , int r )
{
int jeg , j , k ;
int n1 = m - l + 1 ;
int n2 = r - m ;
// Opret midlertidige subarrays
int L [ n1 ] , R [ n2 ] ;
// Kopier data til subarrays
til ( jeg = 0 ; jeg < n1 ; jeg ++ )
L [ jeg ] = arr [ l + jeg ] ;
til ( j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
// Flet de midlertidige underarrays tilbage til det oprindelige array
jeg = 0 ;
j = 0 ;
k = l ;
mens ( jeg < n1 && j < n2 ) {
hvis ( L [ jeg ] <= R [ j ] ) {
arr [ k ] = L [ jeg ] ;
jeg ++;
}
andet {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
// Kopier de resterende elementer i L[]
mens ( jeg < n1 ) {
arr [ k ] = L [ jeg ] ;
jeg ++;
k ++;
}
// Kopier de resterende elementer af R[]
mens ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
ugyldig fletteSortér ( int arr [ ] , int l , int r )
{
hvis ( l < r ) {
int m = l + ( r - l ) / 2 ;
// Sorter venstre og højre halvdel rekursivt
fletteSortér ( arr , l , m ) ;
fletteSortér ( arr , m + 1 , r ) ;
// Flet de to sorterede halvdele sammen
fusionere ( arr , l , m , r ) ;
}
}
int vigtigste ( )
{
int arr [ ] = { 12 , elleve , 13 , 5 , 6 , 7 } ;
int arr_size = størrelse på ( arr ) / størrelse på ( arr [ 0 ] ) ;
cout << 'Given matrix er \n ' ;
til ( int jeg = 0 ; jeg < arr_size ; jeg ++ )
cout << arr [ jeg ] << ' ' ;
fletteSortér ( arr , 0 , arr_size - 1 ) ;
cout << ' \n Sorteret array er \n ' ;
til ( int jeg = 0 ; jeg < arr_size ; jeg ++ )
cout << arr [ jeg ] << ' ' ;
Vend tilbage 0 ;
}
Dette program er ligesom det forrige, men i stedet for at bruge to midlertidige subarrays L og R, bruger det en enkelt midlertidig subarray temp. Merge-funktionen fungerer på samme måde som før, men i stedet for at kopiere dataene til L og R, kopierer den dem til temp. Det fletter derefter temp array-elementer tilbage i arr som er det originale array.
MergeSort-funktionen er den samme som før, bortset fra at den bruger temp i stedet for L og R til at gemme den midlertidige subarray.
I hovedfunktionen definerer vi en array arr med 6 elementer og kalder funktionen mergeSort for at sortere den. Kodeudførelsen afsluttes med at udskrive det sorterede array på skærmen.
Konklusion
Merge sort er en algoritme, der sorterer array-elementer, og den bruger divide-and-conquer-teknikken og foretager sammenligninger mellem elementer. Merge sort i C++ har en tidskompleksitet på O(n log n) og er særligt effektiv til sortering af store arrays. Selvom det kræver ekstra hukommelse at gemme de flettede underarrays, gør dets stabilitet det til et populært valg til sortering.