Sadržaj
- Uvod
- Što je sortiranje spajanjem u C++
- Pristup zavadi pa vladaj
- Algoritam sortiranja spajanjem
- Implementacija Sortiranja spajanjem u C++
- Zaključak
1. Uvod
Algoritmi sortiranja u računalnoj znanosti koriste se za raspoređivanje podataka uzlaznim ili silaznim redoslijedom. Dostupno je više algoritama za sortiranje s različitim svojstvima. Sortiranje spajanjem je jedna od metoda u C++ koja može sortirati nizove.
2. Što je sortiranje spajanjem u C++
Sortiranje spajanjem koristi tehniku podijeli i vladaj kojom se mogu rasporediti elementi niza. Također može sortirati popis elemenata u C++. Dijeli ulaz na dvije polovice, razvrstava svaku polovicu neovisno, a zatim ih spaja ispravnim redoslijedom.
3. Pristup zavadi pa vladaj
Algoritam razvrstavanja primjenjuje strategiju zavadi i vladaj, što uključuje dijeljenje ulaznog niza na manje podnizove, njihovo zasebno rješavanje, a zatim spajanje rezultata kako bi se dobio sortirani izlaz. U slučaju sortiranja spajanjem, niz se rekurzivno dijeli na dvije polovice sve dok u svakoj polovici ne ostane samo jedan element.
4. Algoritam sortiranja spajanjem
Algoritam sortiranja spajanjem sastoji se od dva glavna koraka: dijeljenja i spajanja. Koraci su sljedeći:
4.1 Podijelite
Algoritam sortiranja spajanjem slijedi strategiju podijeli i vladaj za sortiranje elemenata u nizu.
- Prvi korak u algoritmu će provjeriti elemente niza. Ako sadrži jedan element, tada se već smatra sortiranim, a algoritam će vratiti isti niz bez ikakvih promjena.
- Ako niz sadrži više od jednog elementa, algoritam ga dijeli na dvije polovice: lijevu polovicu i desnu polovicu.
- Algoritam sortiranja spajanjem zatim se rekurzivno primjenjuje na lijevu i desnu polovicu niza, učinkovito ih dijeleći u manje podnizove i sortirajući pojedinačno.
- Ovaj se rekurzivni proces nastavlja sve dok podnizovi ne sadrže samo jedan element svaki (kao u koraku 1), a tada se mogu spojiti kako bi proizveli konačni, razvrstani izlazni niz.
4.2 Spajanje
Sada ćemo vidjeti korake za spajanje nizova:
- Prvi korak za algoritam sortiranja spajanjem uključuje stvaranje praznog niza.
- Algoritam zatim nastavlja uspoređivati prve elemente lijeve i desne polovice ulaznog niza.
- Manji od ta dva elementa dodaje se u novi niz, a zatim se uklanja iz odgovarajuće polovice ulaznog niza.
- Zatim se ponavljaju koraci 2-3 dok se jedna od polovica ne isprazni.
- Svi preostali elementi u nepraznoj polovici tada se dodaju u novi niz.
- Rezultirajući niz sada je potpuno sortiran i predstavlja konačni izlaz algoritma za sortiranje spajanjem.
5. Implementacija Sortiranja spajanjem u C++
Za implementaciju sortiranja spajanjem u C++ slijede dvije različite metode. Vremenska složenost obje metode je jednaka, ali se njihova upotreba privremenih podnizova razlikuje.
Prva metoda za sortiranje spajanjem u C++ koristi dvije privremene podnizove, dok druga koristi samo jednu. Vrijedno je napomenuti da je ukupna veličina dvaju privremenih podnizova u prvoj metodi jednaka veličini izvornog niza u drugoj metodi, tako da složenost prostora ostaje konstantna.
Metoda 1 – korištenje dvije privremene podnize
Evo primjera programa za sortiranje spajanjem u C++ koristeći Metodu 1, koja koristi dvije privremene podnizove:
#includekoristeći prostor imena std ;
poništiti sjediniti ( int arr [ ] , int l , int m , int r )
{
int n1 = m - l + 1 ;
int n2 = r - m ;
int L [ n1 ] , R [ n2 ] ;
za ( int ja = 0 ; ja < n1 ; ja ++ )
L [ ja ] = arr [ l + ja ] ;
za ( int j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
int ja = 0 , j = 0 , k = l ;
dok ( ja < n1 && j < n2 ) {
ako ( L [ ja ] <= R [ j ] ) {
arr [ k ] = L [ ja ] ;
ja ++;
}
drugo {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
dok ( ja < n1 ) {
arr [ k ] = L [ ja ] ;
ja ++;
k ++;
}
dok ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
poništiti mergeSort ( int arr [ ] , int l , int r )
{
ako ( l < r ) {
int m = l + ( r - l ) / 2 ;
mergeSort ( arr , l , m ) ;
mergeSort ( arr , m + 1 , r ) ;
sjediniti ( arr , l , m , r ) ;
}
}
int glavni ( )
{
int arr [ ] = { 12 , jedanaest , 13 , 5 , 6 , 7 } ;
int arr_veličina = veličina ( arr ) / veličina ( arr [ 0 ] ) ;
cout << 'Zadani niz je \n ' ;
za ( int ja = 0 ; ja < arr_veličina ; ja ++ )
cout << arr [ ja ] << ' ' ;
mergeSort ( arr , 0 , arr_veličina - 1 ) ;
cout << ' \n Sortirani niz je \n ' ;
za ( int ja = 0 ; ja < arr_veličina ; ja ++ )
cout << arr [ ja ] << ' ' ;
povratak 0 ;
}
U ovom programu, funkcija spajanja uzima tri argumenta arr, l i r, koji predstavljaju niz koji treba sortirati i pokazuju indekse podniza koji treba spojiti. Funkcija prvo pronalazi veličine dviju podnizova koje treba spojiti, zatim stvara dvije privremene podnizove L i R za pohranjivanje elemenata tih podnizova. Zatim uspoređuje elemente u L i R i spaja ih u izvorno imenovano polje arr uzlaznim redoslijedom.
Tehniku podijeli i vladaj koristi funkcija mergeSort za rekurzivno dijeljenje niza na dvije polovice sve dok u podnizu ne ostane samo jedan element. Zatim spaja dvije podniske u sortiranu podnizu. Funkcija nastavlja spajati podnizove osim ako ne sortira cijeli niz.
U glavnoj funkciji definiramo polje arr sa 6 elemenata i pozivamo funkciju mergeSort da ga sortiramo. Na kraju koda ispisuje se sortirani niz.
Metoda 2 – korištenje jedne privremene podniske
Evo primjera programa za sortiranje spajanjem u C++ koristeći metodu 2, koja koristi jednu privremenu podnizu:
#includekoristeći prostor imena std ;
poništiti sjediniti ( int arr [ ] , int l , int m , int r )
{
int ja , j , k ;
int n1 = m - l + 1 ;
int n2 = r - m ;
// Stvaranje privremenih podnizova
int L [ n1 ] , R [ n2 ] ;
// Kopiraj podatke u podnizove
za ( ja = 0 ; ja < n1 ; ja ++ )
L [ ja ] = arr [ l + ja ] ;
za ( j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
// Spajanje privremenih podnizova natrag u izvorno polje
ja = 0 ;
j = 0 ;
k = l ;
dok ( ja < n1 && j < n2 ) {
ako ( L [ ja ] <= R [ j ] ) {
arr [ k ] = L [ ja ] ;
ja ++;
}
drugo {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
// Kopiraj preostale elemente od L[]
dok ( ja < n1 ) {
arr [ k ] = L [ ja ] ;
ja ++;
k ++;
}
// Kopiraj preostale elemente R[]
dok ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
poništiti mergeSort ( int arr [ ] , int l , int r )
{
ako ( l < r ) {
int m = l + ( r - l ) / 2 ;
// Poredaj lijevu i desnu polovicu rekurzivno
mergeSort ( arr , l , m ) ;
mergeSort ( arr , m + 1 , r ) ;
// Spojite dvije sortirane polovice
sjediniti ( arr , l , m , r ) ;
}
}
int glavni ( )
{
int arr [ ] = { 12 , jedanaest , 13 , 5 , 6 , 7 } ;
int arr_veličina = veličina ( arr ) / veličina ( arr [ 0 ] ) ;
cout << 'Zadani niz je \n ' ;
za ( int ja = 0 ; ja < arr_veličina ; ja ++ )
cout << arr [ ja ] << ' ' ;
mergeSort ( arr , 0 , arr_veličina - 1 ) ;
cout << ' \n Sortirani niz je \n ' ;
za ( int ja = 0 ; ja < arr_veličina ; ja ++ )
cout << arr [ ja ] << ' ' ;
povratak 0 ;
}
Ovaj program je poput prethodnog, ali umjesto da koristi dvije privremene podnize L i R, koristi jednu privremenu podnizu temp. Funkcija spajanja radi na isti način kao i prije, ali umjesto kopiranja podataka u L i R, ona ih kopira u temp. Zatim spaja privremene elemente niza natrag u arr koji je izvorni niz.
Funkcija mergeSort ista je kao prije, osim što koristi temp umjesto L i R za pohranjivanje privremene podmarice.
U glavnoj funkciji definiramo polje arr sa 6 elemenata i pozivamo funkciju mergeSort da ga sortiramo. Izvršenje koda završava ispisom sortiranog niza na ekranu.
Zaključak
Merge sort je algoritam koji razvrstava elemente niza, a koristi tehniku podijeli i vladaj i uspoređuje elemente. Sortiranje spajanjem u C++ ima vremensku složenost od O(n log n) i posebno je učinkovito za sortiranje velikih nizova. Iako zahtijeva dodatnu memoriju za pohranjivanje spojenih podnizova, njegova stabilnost čini ga popularnim izborom za sortiranje.