Inhoudsopgave
- Invoering
- Wat is samenvoegen en sorteren in C++
- Verdeel en heers aanpak
- Algoritme voor samenvoegen sorteren
- Implementatie van Merge Sort in C++
- Conclusie
1. Inleiding
Sorteeralgoritmen in de informatica worden gebruikt om gegevens in oplopende of aflopende volgorde te rangschikken. Er zijn meerdere sorteeralgoritmen met verschillende eigenschappen beschikbaar. Merge sort is een van de methoden in C ++ die de arrays kan sorteren.
2. Wat is samenvoegen en sorteren in C++
Merge sort maakt gebruik van de verdeel-en-heers-techniek die de elementen van een array kan rangschikken. Het kan ook de lijst met elementen in C++ sorteren. Het splitst de invoer in twee helften, sorteert elke helft onafhankelijk en voegt ze vervolgens in de juiste volgorde samen.
3. Verdeel en heers aanpak
Het sorteeralgoritme past een verdeel-en-heers-strategie toe, waarbij de invoerarray wordt opgedeeld in kleinere subarrays, deze afzonderlijk worden opgelost en vervolgens de resultaten worden samengevoegd om een gesorteerde uitvoer te produceren. In het geval van samenvoegsortering wordt de array recursief in twee helften verdeeld totdat er in elke helft slechts één element overblijft.
4. Sorteeralgoritme samenvoegen
Het algoritme voor samenvoegen en sorteren bestaat uit twee hoofdstappen: delen en samenvoegen. De stappen zijn als volgt:
4.1 Verdeel
Het samenvoeg-sorteeralgoritme volgt een verdeel-en-heers-strategie voor het sorteren van elementen in een array.
- De eerste stap in het algoritme controleert array-elementen. Als het één element bevat, wordt het al als gesorteerd beschouwd en retourneert het algoritme dezelfde array zonder enige wijziging.
- Als de array meer dan één element bevat, verdeelt het algoritme deze in twee helften: de linkerhelft en de rechterhelft.
- Het samenvoegsorteeralgoritme wordt vervolgens recursief toegepast op de linker- en rechterhelften van de array, waardoor ze effectief in kleinere subarrays worden verdeeld en afzonderlijk worden gesorteerd.
- Dit recursieve proces gaat door totdat de subarrays elk slechts één element bevatten (volgens stap 1), waarna ze kunnen worden samengevoegd om een uiteindelijke, gesorteerde uitvoerarray te produceren.
4.2 Samenvoegen
Nu zullen we de stappen zien om de arrays samen te voegen:
- De eerste stap voor het algoritme voor samenvoegen en sorteren is het maken van een lege array.
- Het algoritme gaat vervolgens verder met het vergelijken van de eerste elementen van de linker- en rechterhelft van de invoerarray.
- De kleinste van de twee elementen wordt toegevoegd aan de nieuwe array en vervolgens verwijderd uit de respectieve helft van de invoerarray.
- Vervolgens worden stap 2-3 herhaald totdat een van de helften leeg is.
- Alle resterende elementen in de niet-lege helft worden vervolgens toegevoegd aan de nieuwe array.
- De resulterende array is nu volledig gesorteerd en vertegenwoordigt de uiteindelijke uitvoer van het algoritme voor samenvoegen.
5. Implementatie van Merge Sort in C++
Om samenvoegsortering in C++ te implementeren, worden twee verschillende methoden gevolgd. De tijdscomplexiteit van beide methoden is gelijk, maar het gebruik van tijdelijke subarrays verschilt.
De eerste methode voor het samenvoegen van sorteringen in C++ gebruikt twee tijdelijke subarrays, terwijl de tweede er slechts één gebruikt. Het is vermeldenswaard dat de totale grootte van de twee tijdelijke subarrays in de eerste methode gelijk is aan de grootte van de originele array in de tweede methode, dus de ruimtelijke complexiteit blijft constant.
Methode 1 - Twee tijdelijke subarrays gebruiken
Hier is een voorbeeldprogramma voor samenvoegsortering in C++ met behulp van methode 1, die twee tijdelijke subarrays gebruikt:
#includenamespace std; gebruiken ;
leegte samenvoegen ( int arr [ ] , int ik , int M , int R )
{
int n1 = M - ik + 1 ;
int n2 = R - M ;
int L [ n1 ] , R [ n2 ] ;
voor ( int i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ ik + i ] ;
voor ( int J = 0 ; J < n2 ; J ++ )
R [ J ] = arr [ M + 1 + J ] ;
int i = 0 , J = 0 , k = ik ;
terwijl ( i < n1 && J < n2 ) {
als ( L [ i ] <= R [ J ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
anders {
arr [ k ] = R [ J ] ;
J ++;
}
k ++;
}
terwijl ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
terwijl ( J < n2 ) {
arr [ k ] = R [ J ] ;
J ++;
k ++;
}
}
leegte samenvoegenSorteren ( int arr [ ] , int ik , int R )
{
als ( ik < R ) {
int M = ik + ( R - ik ) / 2 ;
samenvoegenSorteren ( arr , ik , M ) ;
samenvoegenSorteren ( arr , M + 1 , R ) ;
samenvoegen ( arr , ik , M , R ) ;
}
}
int voornaamst ( )
{
int arr [ ] = { 12 , elf , 13 , 5 , 6 , 7 } ;
int arr_maat = De grootte van ( arr ) / De grootte van ( arr [ 0 ] ) ;
cout << 'Gegeven array is \N ' ;
voor ( int i = 0 ; i < arr_maat ; i ++ )
cout << arr [ i ] << ' ' ;
samenvoegenSorteren ( arr , 0 , arr_maat - 1 ) ;
cout << ' \N Gesorteerde array is \N ' ;
voor ( int i = 0 ; i < arr_maat ; i ++ )
cout << arr [ i ] << ' ' ;
opbrengst 0 ;
}
In dit programma heeft de samenvoegfunctie drie argumenten arr, l en r nodig, die de te sorteren array vertegenwoordigen en de indices toont van de subarray die moet worden samengevoegd. De functie vindt eerst de afmetingen van de twee subarrays die moeten worden samengevoegd, en maakt vervolgens twee tijdelijke subarrays L en R om de elementen van deze subarrays op te slaan. Vervolgens vergelijkt het de elementen in L en R en voegt ze samen in de originele array met de naam arr in oplopende volgorde.
De verdeel-en-heers-techniek wordt gebruikt door de mergeSort-functie om de array recursief in twee helften te splitsen totdat er slechts één element overblijft in de subarray. Vervolgens worden de twee subarrays samengevoegd tot een gesorteerde subarray. De functie gaat door met het samenvoegen van de subarrays, tenzij de volledige array wordt gesorteerd.
In de hoofdfunctie definiëren we een array arr met 6 elementen en roepen we de mergeSort-functie aan om deze te sorteren. Aan het einde van de code wordt de gesorteerde array afgedrukt.
Methode 2 - Eén tijdelijke subarray gebruiken
Hier is een voorbeeldprogramma voor samenvoegsortering in C++ met behulp van methode 2, die een enkele tijdelijke subarray gebruikt:
#includenamespace std; gebruiken ;
leegte samenvoegen ( int arr [ ] , int ik , int M , int R )
{
int i , J , k ;
int n1 = M - ik + 1 ;
int n2 = R - M ;
// Creëer tijdelijke subarrays
int L [ n1 ] , R [ n2 ] ;
// Kopieer gegevens naar subarrays
voor ( i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ ik + i ] ;
voor ( J = 0 ; J < n2 ; J ++ )
R [ J ] = arr [ M + 1 + J ] ;
// Voeg de tijdelijke subarrays weer samen in de oorspronkelijke array
i = 0 ;
J = 0 ;
k = ik ;
terwijl ( i < n1 && J < n2 ) {
als ( L [ i ] <= R [ J ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
anders {
arr [ k ] = R [ J ] ;
J ++;
}
k ++;
}
// Kopieer de overige elementen van L[]
terwijl ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
// Kopieer de overige elementen van R[]
terwijl ( J < n2 ) {
arr [ k ] = R [ J ] ;
J ++;
k ++;
}
}
leegte samenvoegenSorteren ( int arr [ ] , int ik , int R )
{
als ( ik < R ) {
int M = ik + ( R - ik ) / 2 ;
// Sorteer de linker- en rechterhelft recursief
samenvoegenSorteren ( arr , ik , M ) ;
samenvoegenSorteren ( arr , M + 1 , R ) ;
// Voeg de twee gesorteerde helften samen
samenvoegen ( arr , ik , M , R ) ;
}
}
int voornaamst ( )
{
int arr [ ] = { 12 , elf , 13 , 5 , 6 , 7 } ;
int arr_maat = De grootte van ( arr ) / De grootte van ( arr [ 0 ] ) ;
cout << 'Gegeven array is \N ' ;
voor ( int i = 0 ; i < arr_maat ; i ++ )
cout << arr [ i ] << ' ' ;
samenvoegenSorteren ( arr , 0 , arr_maat - 1 ) ;
cout << ' \N Gesorteerde array is \N ' ;
voor ( int i = 0 ; i < arr_maat ; i ++ )
cout << arr [ i ] << ' ' ;
opbrengst 0 ;
}
Dit programma lijkt op het vorige, maar in plaats van twee tijdelijke subarrays L en R te gebruiken, gebruikt het een enkele tijdelijke subarray temp. De samenvoegfunctie werkt op dezelfde manier als voorheen, maar in plaats van de gegevens naar L en R te kopiëren, kopieert het deze naar temp. Vervolgens voegt het tijdelijke array-elementen weer samen in het arr wat de originele array is.
De mergeSort-functie is hetzelfde als voorheen, behalve dat het temp gebruikt in plaats van L en R om de tijdelijke subarray op te slaan.
In de hoofdfunctie definiëren we een array arr met 6 elementen en roepen we de mergeSort-functie aan om deze te sorteren. De uitvoering van de code eindigt door de gesorteerde array op het scherm af te drukken.
Conclusie
Merge sort is een algoritme dat array-elementen sorteert, en het gebruikt de verdeel-en-heers-techniek en maakt vergelijkingen tussen elementen. Merge sort in C++ heeft een tijdscomplexiteit van O(n log n) en is vooral effectief voor het sorteren van grote arrays. Hoewel het extra geheugen vereist om de samengevoegde subarrays op te slaan, maakt de stabiliteit het een populaire keuze voor sorteren.