Obsah
- Úvod
- Čo je Merge Sort v C++
- Prístup rozdeľuj a panuj
- Algoritmus triedenia zlúčením
- Implementácia Merge Sort v C++
- Záver
1. Úvod
Algoritmy triedenia v informatike sa používajú na usporiadanie údajov vo vzostupnom alebo zostupnom poradí. K dispozícii je viacero triediacich algoritmov s odlišnými vlastnosťami. Merge sort je jednou z metód v C++, ktorá dokáže zoradiť polia.
2. Čo je Merge Sort v C++
Zlúčiť triedenie používa techniku rozdeľuj a panuj, ktorá dokáže usporiadať prvky poľa. Môže tiež triediť zoznam prvkov v C++. Rozdelí vstup na dve polovice, každú polovicu zoradí nezávisle a potom ich zlúči v správnom poradí.
3. Prístup rozdeľuj a panuj
Algoritmus triedenia používa stratégiu rozdelenia a panovania, ktorá zahŕňa rozdelenie vstupného poľa na menšie podpolia, ich samostatné riešenie a následné zlúčenie výsledkov, aby sa vytvoril triedený výstup. V prípade zlučovacieho triedenia je pole rekurzívne rozdelené na dve polovice, až kým v každej polovici nezostane iba jeden prvok.
4. Zlúčiť triediaci algoritmus
Algoritmus triedenia zlúčenia pozostáva z dvoch hlavných krokov: rozdelenie a zlúčenie. Kroky sú nasledovné:
4.1 Rozdeliť
Algoritmus zlučovania sa riadi stratégiou rozdeľovania a panovania na triedenie prvkov v poli.
- Prvý krok v algoritme skontroluje prvky poľa. Ak obsahuje jeden prvok, potom sa už považuje za triedený a algoritmus vráti rovnaké pole bez akejkoľvek zmeny.
- Ak pole obsahuje viac ako jeden prvok, algoritmus ho rozdelí na dve polovice: ľavú polovicu a pravú polovicu.
- Algoritmus zlučovacieho triedenia sa potom rekurzívne aplikuje na ľavú a pravú polovicu poľa, čím ich efektívne rozdelí na menšie podpolia a zoradí ich jednotlivo.
- Tento rekurzívny proces pokračuje, až kým podpolia neobsahujú iba jeden prvok (podľa kroku 1), v tomto bode môžu byť zlúčené, aby sa vytvorilo konečné, triedené výstupné pole.
4.2 Zlúčiť
Teraz uvidíme kroky na zlúčenie polí:
- Prvý krok pre algoritmus triedenia zlúčenia zahŕňa vytvorenie prázdneho poľa.
- Algoritmus potom pokračuje v porovnaní prvých prvkov ľavej a pravej polovice vstupného poľa.
- Menší z dvoch prvkov sa pridá do nového poľa a potom sa odstráni z príslušnej polovice vstupného poľa.
- Kroky 2-3 sa potom opakujú, kým sa jedna z polovíc nevyprázdni.
- Všetky zostávajúce prvky v neprázdnej polovici sa potom pridajú do nového poľa.
- Výsledné pole je teraz úplne zoradené a predstavuje konečný výstup algoritmu zlučovania.
5. Implementácia Merge Sort v C++
Na implementáciu zlučovacieho triedenia v C++ sa používajú dve rôzne metódy. Časová náročnosť oboch metód je ekvivalentná, ale ich použitie dočasných podpolí sa líši.
Prvá metóda na triedenie zlúčenia v C++ používa dve dočasné podpole, zatiaľ čo druhá používa iba jedno. Stojí za zmienku, že celková veľkosť dvoch dočasných podpolí v prvej metóde sa rovná veľkosti pôvodného poľa v druhej metóde, takže priestorová zložitosť zostáva konštantná.
Metóda 1 – Použitie dvoch dočasných podpolí
Tu je príklad programu na triedenie zlúčenia v C++ pomocou metódy 1, ktorá používa dve dočasné podpolia:
#includepomocou menného priestoru std ;
neplatné zlúčiť ( int arr [ ] , int l , int m , int r )
{
int n1 = m - l + 1 ;
int n2 = r - m ;
int L [ n1 ] , R [ n2 ] ;
pre ( int i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ l + i ] ;
pre ( int j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
int i = 0 , j = 0 , k = l ;
zatiaľ čo ( i < n1 && j < n2 ) {
ak ( L [ i ] <= R [ j ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
inak {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
zatiaľ čo ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
zatiaľ čo ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
neplatné mergeSort ( int arr [ ] , int l , int r )
{
ak ( l < r ) {
int m = l + ( r - l ) / 2 ;
mergeSort ( arr , l , m ) ;
mergeSort ( arr , m + 1 , r ) ;
zlúčiť ( arr , l , m , r ) ;
}
}
int Hlavná ( )
{
int arr [ ] = { 12 , jedenásť , 13 , 5 , 6 , 7 } ;
int arr_size = veľkosť ( arr ) / veľkosť ( arr [ 0 ] ) ;
cout << Dané pole je \n ' ;
pre ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << '' ;
mergeSort ( arr , 0 , arr_size - 1 ) ;
cout << ' \n Zoradené pole je \n ' ;
pre ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << '' ;
vrátiť 0 ;
}
V tomto programe funkcia zlúčenia preberá tri argumenty arr, l a r, ktoré predstavujú pole, ktoré sa má triediť, a zobrazujú indexy podpolia, ktoré je potrebné zlúčiť. Funkcia najprv nájde veľkosti dvoch podpolí, ktoré sa majú zlúčiť, a potom vytvorí dve dočasné podpole L a R na uloženie prvkov týchto podpolí. Potom porovná prvky v L a R a zlúči ich do pôvodného pomenovaného poľa arr vo vzostupnom poradí.
Funkcia mergeSort využíva techniku rozdeľuj a panuj na rozdelenie poľa na dve polovice rekurzívne, až kým v podpole nezostane len jeden prvok. Potom zlúči dve podpole do triedeného podpolia. Funkcia pokračuje v zlučovaní podpolí, pokiaľ neroztriedi celé pole.
V hlavnej funkcii definujeme pole arr so 6 prvkami a zavoláme funkciu mergeSort na jeho zoradenie. Na konci kódu sa vytlačí zoradené pole.
Metóda 2 – Použitie One Temp Subarray
Tu je príklad programu na triedenie zlúčenia v C++ pomocou metódy 2, ktorá používa jednu dočasnú podpolu:
#includepomocou menného priestoru std ;
neplatné zlúčiť ( int arr [ ] , int l , int m , int r )
{
int i , j , k ;
int n1 = m - l + 1 ;
int n2 = r - m ;
// Vytvorenie dočasných podpolí
int L [ n1 ] , R [ n2 ] ;
// Kopírovanie údajov do podpolí
pre ( i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ l + i ] ;
pre ( j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
// Zlúčte dočasné podpolia späť do pôvodného poľa
i = 0 ;
j = 0 ;
k = l ;
zatiaľ čo ( i < n1 && j < n2 ) {
ak ( L [ i ] <= R [ j ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
inak {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
// Skopírujte zostávajúce prvky L[]
zatiaľ čo ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
// Skopírujte zostávajúce prvky R[]
zatiaľ čo ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
neplatné mergeSort ( int arr [ ] , int l , int r )
{
ak ( l < r ) {
int m = l + ( r - l ) / 2 ;
// Zoradiť ľavú a pravú polovicu rekurzívne
mergeSort ( arr , l , m ) ;
mergeSort ( arr , m + 1 , r ) ;
// Zlúčte dve zoradené polovice
zlúčiť ( arr , l , m , r ) ;
}
}
int Hlavná ( )
{
int arr [ ] = { 12 , jedenásť , 13 , 5 , 6 , 7 } ;
int arr_size = veľkosť ( arr ) / veľkosť ( arr [ 0 ] ) ;
cout << Dané pole je \n ' ;
pre ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << '' ;
mergeSort ( arr , 0 , arr_size - 1 ) ;
cout << ' \n Zoradené pole je \n ' ;
pre ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << '' ;
vrátiť 0 ;
}
Tento program je ako predchádzajúci, ale namiesto použitia dvoch dočasných podpolí L a R používa jednu dočasnú podpolia temp. Funkcia zlúčenia funguje rovnakým spôsobom ako predtým, ale namiesto kopírovania údajov do L a R ich skopíruje do temp. Potom zlúči prvky dočasného poľa späť do arr čo je pôvodné pole.
Funkcia mergeSort je rovnaká ako predtým, okrem toho, že na uloženie dočasného podpola používa namiesto L a R temp.
V hlavnej funkcii definujeme pole arr so 6 prvkami a zavoláme funkciu mergeSort, aby sme ho zoradili. Spustenie kódu končí vytlačením zoradeného poľa na obrazovku.
Záver
Merge sort je algoritmus, ktorý triedi prvky poľa a používa techniku rozdeľuj a panuj a porovnáva medzi prvkami. Merge sort v C++ má časovú zložitosť O(n log n) a je obzvlášť účinný pri triedení veľkých polí. Hoci si vyžaduje dodatočnú pamäť na uloženie zlúčených podpolí, jeho stabilita z neho robí obľúbenú voľbu triedenia.