Obsah
- Úvod
- Co je Merge Sort v C++
- Přístup rozděl a panuj
- Algoritmus řazení sloučení
- Implementace Merge Sort v C++
- Závěr
1. Úvod
Algoritmy řazení v informatice se používají k uspořádání dat ve vzestupném nebo sestupném pořadí. K dispozici je několik třídicích algoritmů s odlišnými vlastnostmi. Merge sort je jednou z metod v C++, která dokáže třídit pole.
2. Co je Merge Sort v C++
Sloučit řazení používá techniku rozděl a panuj, která dokáže uspořádat prvky pole. Může také třídit seznam prvků v C++. Rozdělí vstup na dvě poloviny, každou polovinu seřadí samostatně a poté je sloučí ve správném pořadí.
3. Přístup rozděl a panuj
Algoritmus řazení používá strategii rozděl a panuj, která zahrnuje rozdělení vstupního pole na menší podpole, jejich samostatné řešení a následné sloučení výsledků, aby se vytvořil setříděný výstup. V případě slučovacího řazení je pole rekurzivně rozděleno na dvě poloviny, dokud v každé polovině nezůstane pouze jeden prvek.
4. Algoritmus řazení sloučení
Algoritmus řazení sloučení se skládá ze dvou hlavních kroků: rozdělení a sloučení. Postup je následující:
4.1 Rozdělit
Algoritmus řazení sloučení se řídí strategií rozděl a panuj pro řazení prvků v poli.
- První krok v algoritmu zkontroluje prvky pole. Pokud obsahuje jeden prvek, pak je již považován za seřazený a algoritmus vrátí stejné pole bez jakékoli změny.
- Pokud pole obsahuje více než jeden prvek, algoritmus jej rozdělí na dvě poloviny: levou polovinu a pravou polovinu.
- Algoritmus slučovacího řazení je pak rekurzivně aplikován na levou a pravou polovinu pole, čímž je efektivně rozděluje na menší podpole a třídí je jednotlivě.
- Tento rekurzivní proces pokračuje, dokud podpole neobsahují každý pouze jeden prvek (podle kroku 1), v tomto okamžiku je lze sloučit a vytvořit konečné setříděné výstupní pole.
4.2 Sloučit
Nyní uvidíme kroky ke sloučení polí:
- První krok pro algoritmus řazení sloučení zahrnuje vytvoření prázdného pole.
- Algoritmus pak pokračuje v porovnání prvních prvků levé a pravé poloviny vstupního pole.
- Menší z těchto dvou prvků se přidá do nového pole a poté se odstraní z jeho příslušné poloviny vstupního pole.
- Kroky 2-3 se pak opakují, dokud se jedna z polovin nevyprázdní.
- Všechny zbývající prvky v neprázdné polovině jsou pak přidány do nového pole.
- Výsledné pole je nyní plně seřazeno a představuje konečný výstup algoritmu řazení sloučení.
5. Implementace Merge Sort v C++
Pro implementaci slučovacího řazení v C++ se používají dvě různé metody. Časová náročnost obou metod je ekvivalentní, liší se však jejich použití dočasných podpolí.
První metoda pro slučovací řazení v C++ používá dvě dočasné podpole, zatímco druhá používá pouze jedno. Stojí za zmínku, že celková velikost dvou dočasných podpolí v první metodě je rovna velikosti původního pole ve druhé metodě, takže prostorová složitost zůstává konstantní.
Metoda 1 – Použití dvou Temp Subarrays
Zde je příklad programu pro řazení sloučení v C++ pomocí metody 1, která používá dvě dočasné podpole:
#includepomocí jmenného prostoru std ;
prázdnota spojit ( int arr [ ] , int l , int m , int r )
{
int n1 = m - l + 1 ;
int n2 = r - m ;
int L [ n1 ] , R [ n2 ] ;
pro ( int i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ l + i ] ;
pro ( int j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
int i = 0 , j = 0 , k = l ;
zatímco ( i < n1 && j < n2 ) {
-li ( L [ i ] <= R [ j ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
jiný {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
zatímco ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
zatímco ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
prázdnota Sloučit třídění ( int arr [ ] , int l , int r )
{
-li ( l < r ) {
int m = l + ( r - l ) / 2 ;
Sloučit třídění ( arr , l , m ) ;
Sloučit třídění ( arr , m + 1 , r ) ;
spojit ( arr , l , m , r ) ;
}
}
int hlavní ( )
{
int arr [ ] = { 12 , jedenáct , 13 , 5 , 6 , 7 } ;
int arr_size = velikost ( arr ) / velikost ( arr [ 0 ] ) ;
cout << 'Dané pole je \n ' ;
pro ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << '' ;
Sloučit třídění ( arr , 0 , arr_size - 1 ) ;
cout << ' \n Seřazené pole je \n ' ;
pro ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << '' ;
vrátit se 0 ;
}
V tomto programu funkce sloučení přebírá tři argumenty arr, l a r, které představují pole, které se má třídit, a ukazuje indexy podpole, které je třeba sloučit. Funkce nejprve najde velikosti dvou podpolí, které mají být sloučeny, a poté vytvoří dvě dočasné podpole L a R pro uložení prvků těchto podpolí. Poté porovná prvky v L a R a sloučí je do původního pojmenovaného pole arr ve vzestupném pořadí.
Technika rozdělení a panování je využívána funkcí mergeSort k rekurzivnímu rozdělení pole na dvě poloviny, dokud v podpole nezůstane pouze jeden prvek. Poté sloučí dvě podpole do seřazeného podpole. Funkce pokračuje ve slučování dílčích polí, pokud nesetřídí celé pole.
Ve funkci main definujeme pole arr se 6 prvky a zavoláme funkci mergeSort, abychom jej seřadili. Na konci kódu je vytištěno setříděné pole.
Metoda 2 – Použití One Temp Subarray
Zde je ukázkový program pro řazení sloučení v C++ pomocí metody 2, která používá jediné dočasné podpole:
#includepomocí jmenného prostoru std ;
prázdnota spojit ( int arr [ ] , int l , int m , int r )
{
int i , j , k ;
int n1 = m - l + 1 ;
int n2 = r - m ;
// Vytvoří dočasné podpole
int L [ n1 ] , R [ n2 ] ;
// Kopírování dat do podpolí
pro ( i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ l + i ] ;
pro ( j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
// Sloučit dočasné podpole zpět do původního pole
i = 0 ;
j = 0 ;
k = l ;
zatímco ( i < n1 && j < n2 ) {
-li ( L [ i ] <= R [ j ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
jiný {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
// Zkopírujte zbývající prvky L[]
zatímco ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
// Zkopírujte zbývající prvky R[]
zatímco ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
prázdnota Sloučit třídění ( int arr [ ] , int l , int r )
{
-li ( l < r ) {
int m = l + ( r - l ) / 2 ;
// Seřadit levou a pravou polovinu rekurzivně
Sloučit třídění ( arr , l , m ) ;
Sloučit třídění ( arr , m + 1 , r ) ;
// Sloučit dvě seřazené poloviny
spojit ( arr , l , m , r ) ;
}
}
int hlavní ( )
{
int arr [ ] = { 12 , jedenáct , 13 , 5 , 6 , 7 } ;
int arr_size = velikost ( arr ) / velikost ( arr [ 0 ] ) ;
cout << 'Dané pole je \n ' ;
pro ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << '' ;
Sloučit třídění ( arr , 0 , arr_size - 1 ) ;
cout << ' \n Seřazené pole je \n ' ;
pro ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << '' ;
vrátit se 0 ;
}
Tento program je jako předchozí, ale místo toho, aby používal dvě dočasné podpole L a R, používá jednu dočasnou podpole temp. Funkce sloučení funguje stejně jako dříve, ale místo zkopírování dat do L a R je zkopíruje do temp. Poté sloučí prvky dočasného pole zpět do arr což je původní pole.
Funkce mergeSort je stejná jako předtím, kromě toho, že k uložení dočasného podpole používá místo L a R temp.
Ve funkci main definujeme pole arr se 6 prvky a zavoláme funkci mergeSort, abychom jej seřadili. Spouštění kódu končí vytištěním setříděného pole na obrazovku.
Závěr
Merge sort je algoritmus, který třídí prvky pole a používá techniku rozděl a panuj a porovnává prvky. Merge sort v C++ má časovou složitost O(n log n) a je zvláště efektivní pro třídění velkých polí. Ačkoli vyžaduje další paměť pro uložení sloučených podpolí, jeho stabilita z něj dělá oblíbenou volbu pro třídění.