Turinys
- Įvadas
- Kas yra sujungimo rūšiavimas C++
- „Skaldyk ir valdyk“ metodas
- Sujungti rūšiavimo algoritmą
- Sujungimo rūšiavimo įdiegimas C++
- Išvada
1. Įvadas
Informatikos rūšiavimo algoritmai naudojami duomenims išdėstyti didėjančia arba mažėjančia tvarka. Yra keli rūšiavimo algoritmai su skirtingomis savybėmis. Sujungti rūšiavimą yra vienas iš C++ metodų, kuris gali rūšiuoti masyvus.
2. Kas yra Merge Sort programoje C++
Sujungimo rūšiavimas naudoja padalijimo ir užkariauk techniką, kuri gali išdėstyti masyvo elementus. Jis taip pat gali rūšiuoti elementų sąrašą C++. Jis padalija įvestį į dvi dalis, surūšiuoja kiekvieną pusę atskirai ir sujungia jas tinkama tvarka.
3. „Skaldyk ir valdyk“ metodas
Rūšiavimo algoritmas taiko „skaldyk ir užkariauk“ strategiją, kuri apima įvesties masyvo padalijimą į mažesnius pogrupius, juos išsprendžiant atskirai ir rezultatų sujungimą, kad gautų surūšiuotą išvestį. Sujungimo rūšiavimo atveju masyvas rekursyviai padalinamas į dvi dalis, kol kiekvienoje pusėje lieka tik vienas elementas.
4. Sujungimo rūšiavimo algoritmas
Sujungimo rūšiavimo algoritmas susideda iš dviejų pagrindinių žingsnių: padalijimo ir sujungimo. Veiksmai yra tokie:
4.1 Padalinti
Sujungimo rūšiavimo algoritmas, rūšiuodamas elementus masyve, vadovaujasi „skaldyk ir užkariauk“ strategija.
- Pirmasis algoritmo veiksmas patikrins masyvo elementus. Jei jame yra vienas elementas, jis jau laikomas surūšiuotu, o algoritmas grąžins tą patį masyvą be jokių pakeitimų.
- Jei masyve yra daugiau nei vienas elementas, algoritmas padalija jį į dvi dalis: kairiąją ir dešiniąją.
- Tada sujungimo rūšiavimo algoritmas rekursyviai taikomas kairėje ir dešinėje masyvo pusėje, efektyviai padalijant jas į mažesnes pogrupes ir rūšiuojant atskirai.
- Šis rekursinis procesas tęsiasi tol, kol pogrupiuose yra tik vienas elementas (kaip nurodyta 1 veiksme), tada juos galima sujungti, kad būtų sukurtas galutinis surūšiuotas išvesties masyvas.
4.2 Sujungti
Dabar pamatysime masyvų sujungimo veiksmus:
- Pirmasis sujungimo rūšiavimo algoritmo žingsnis apima tuščio masyvo sukūrimą.
- Tada algoritmas lygina pirmuosius kairiosios ir dešiniosios įvesties masyvo dalių elementus.
- Mažesnis iš dviejų elementų pridedamas prie naujo masyvo ir pašalinamas iš atitinkamos įvesties masyvo pusės.
- Tada 2–3 žingsniai kartojami tol, kol viena iš pusių ištuštėja.
- Tada visi likę netuščios pusės elementai pridedami prie naujo masyvo.
- Gautas masyvas dabar yra visiškai surūšiuotas ir atspindi galutinę sujungimo rūšiavimo algoritmo išvestį.
5. Merge Sort įdiegimas C++
Norint įgyvendinti sujungimo rūšiavimą C++, taikomi du skirtingi metodai. Abiejų metodų sudėtingumas laike yra lygiavertis, tačiau jų laikinųjų pogrupių naudojimas skiriasi.
Pirmasis sujungimo rūšiavimo metodas C++ naudoja du laikinus pogrupius, o antrasis – tik vieną. Verta pažymėti, kad bendras dviejų laikinų pogrupių dydis pirmuoju metodu yra lygus pradinio masyvo dydžiui pagal antrąjį metodą, todėl erdvės sudėtingumas išlieka pastovus.
1 būdas – dviejų laikinųjų pogrupių naudojimas
Štai programos pavyzdys, skirtas sujungimo rūšiavimui C++ naudojant 1 metodą, kuris naudoja dvi laikinąsias pogrupes:
#includenaudojant vardų sritį std ;
tuštuma sujungti ( tarpt arr [ ] , tarpt l , tarpt m , tarpt r )
{
tarpt n1 = m - l + 1 ;
tarpt n2 = r - m ;
tarpt L [ n1 ] , R [ n2 ] ;
dėl ( tarpt i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ l + i ] ;
dėl ( tarpt j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
tarpt i = 0 , j = 0 , k = l ;
kol ( i < n1 && j < n2 ) {
jeigu ( L [ i ] <= R [ j ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
Kitas {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
kol ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
kol ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
tuštuma mergeSort ( tarpt arr [ ] , tarpt l , tarpt r )
{
jeigu ( l < r ) {
tarpt m = l + ( r - l ) / 2 ;
mergeSort ( arr , l , m ) ;
mergeSort ( arr , m + 1 , r ) ;
sujungti ( arr , l , m , r ) ;
}
}
tarpt pagrindinis ( )
{
tarpt arr [ ] = { 12 , vienuolika , 13 , 5 , 6 , 7 } ;
tarpt arr_size = dydis ( arr ) / dydis ( arr [ 0 ] ) ;
cout << „Duotas masyvas yra \n “ ;
dėl ( tarpt i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
mergeSort ( arr , 0 , arr_size - 1 ) ;
cout << “ \n Rūšiuotas masyvas yra \n “ ;
dėl ( tarpt i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
grąžinti 0 ;
}
Šioje programoje sujungimo funkcija naudoja tris argumentus arr, l ir r, kurie nurodo rūšiuojamą masyvą ir rodo sujungimo pogrupio indeksus. Funkcija pirmiausia suranda dviejų sujungiamų pogrupių dydžius, tada sukuria dvi laikinąsias pogrupes L ir R, kuriose saugomi šių posistemių elementai. Tada lygina L ir R elementus ir sujungia juos į pradinį pavadintą masyvą arr didėjimo tvarka.
Skaldyk ir valdyk technika naudojama mergeSort funkcijai, kad masyvas rekursyviai padalijamas į dvi dalis, kol pogrupyje lieka tik vienas elementas. Tada jis sujungia du pogrupius į surūšiuotą pogrupį. Funkcija ir toliau sujungia pogrupius, nebent surūšiuoja visą masyvą.
Pagrindinėje funkcijoje apibrėžiame masyvą arr su 6 elementais ir iškviečiame funkciją mergeSort, kad jį surūšiuotume. Kodo pabaigoje atspausdinamas surūšiuotas masyvas.
2 būdas – vieno laikinojo pogrupio naudojimas
Štai programos pavyzdys, skirtas sujungimui rūšiuoti C++ naudojant 2 metodą, kuris naudoja vieną laikiną pogrupį:
#includenaudojant vardų sritį std ;
tuštuma sujungti ( tarpt arr [ ] , tarpt l , tarpt m , tarpt r )
{
tarpt i , j , k ;
tarpt n1 = m - l + 1 ;
tarpt n2 = r - m ;
// Sukurti laikinus pogrupius
tarpt L [ n1 ] , R [ n2 ] ;
// Kopijuoti duomenis į pogrupius
dėl ( i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ l + i ] ;
dėl ( j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
// Sujunkite laikinus pogrupius atgal į pradinį masyvą
i = 0 ;
j = 0 ;
k = l ;
kol ( i < n1 && j < n2 ) {
jeigu ( L [ i ] <= R [ j ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
Kitas {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
// Nukopijuokite likusius L[] elementus
kol ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
// Nukopijuokite likusius R elementus[]
kol ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
tuštuma mergeSort ( tarpt arr [ ] , tarpt l , tarpt r )
{
jeigu ( l < r ) {
tarpt m = l + ( r - l ) / 2 ;
// Rekursyviai rūšiuokite kairę ir dešinę puses
mergeSort ( arr , l , m ) ;
mergeSort ( arr , m + 1 , r ) ;
// Sujungti dvi surūšiuotas puses
sujungti ( arr , l , m , r ) ;
}
}
tarpt pagrindinis ( )
{
tarpt arr [ ] = { 12 , vienuolika , 13 , 5 , 6 , 7 } ;
tarpt arr_size = dydis ( arr ) / dydis ( arr [ 0 ] ) ;
cout << „Duotas masyvas yra \n “ ;
dėl ( tarpt i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
mergeSort ( arr , 0 , arr_size - 1 ) ;
cout << “ \n Rūšiuotas masyvas yra \n “ ;
dėl ( tarpt i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
grąžinti 0 ;
}
Ši programa yra kaip ir ankstesnė, tačiau vietoj dviejų laikinų pogrupių L ir R ji naudoja vieną laikiną pogrupio temp. Sujungimo funkcija veikia taip pat, kaip ir anksčiau, tačiau užuot nukopijavusi duomenis į L ir R, nukopijuoja juos į temp. Tada jis sujungia laikinojo masyvo elementus atgal į arr kuris yra pradinis masyvas.
Funkcija mergeSort yra tokia pati kaip ir anksčiau, išskyrus tai, kad laikinam pogrupiui saugoti naudojama temp, o ne L ir R.
Pagrindinėje funkcijoje apibrėžiame masyvą arr su 6 elementais ir iškviečiame funkciją mergeSort, kad jį surūšiuotume. Kodo vykdymas baigiamas atspausdinus surūšiuotą masyvą ekrane.
Išvada
Sujungimo rūšiavimas yra algoritmas, rūšiuojantis masyvo elementus, naudojant „skaldyk ir užkariauk“ techniką bei palyginus elementus. Sujungimo rūšiavimo C++ laiko sudėtingumas yra O(n log n) ir yra ypač efektyvus rūšiuojant didelius masyvus. Nors norint išsaugoti sujungtus pogrupius reikia papildomos atminties, dėl stabilumo tai yra populiarus pasirinkimas rūšiuojant.