Satura rādītājs
- Ievads
- Kas ir sapludināšanas kārtošana programmā C++
- Skaldi un valdi pieeja
- Sapludināt kārtošanas algoritmu
- Merge Sort ieviešana programmā C++
- Secinājums
1. Ievads
Datorzinātņu kārtošanas algoritmi tiek izmantoti, lai sakārtotu datus augošā vai dilstošā secībā. Ir pieejami vairāki šķirošanas algoritmi ar atšķirīgām īpašībām. Sapludināšanas kārtošana ir viena no C++ metodēm, kas var kārtot masīvus.
2. Kas ir sapludināšanas kārtošana programmā C++
Sapludināšanas kārtošana izmanto sadalīšanas un iekarošanas paņēmienu, kas var sakārtot masīva elementus. Tas var arī kārtot elementu sarakstu C++. Tas sadala ievadi divās daļās, šķiro katru pusi atsevišķi un pēc tam apvieno tās pareizajā secībā.
3. Skaldi un valdi pieeja
Šķirošanas algoritms izmanto sadali un iekaro stratēģiju, kas ietver ievades masīva sadalīšanu mazākos apakšmasīvos, to atrisināšanu atsevišķi un rezultātu apvienošanu, lai iegūtu sakārtotu izvadi. Sapludināšanas kārtošanas gadījumā masīvs tiek rekursīvi sadalīts divās daļās, līdz katrā pusē paliek tikai viens elements.
4. Sapludināšanas kārtošanas algoritms
Sapludināšanas kārtošanas algoritms sastāv no diviem galvenajiem soļiem: sadalīšanas un sapludināšanas. Darbības ir šādas:
4.1. Sadalīt
Sapludināšanas kārtošanas algoritms masīva elementu šķirošanai ievēro sadalīšanas un iekarošanas stratēģiju.
- Pirmajā algoritma darbībā tiks pārbaudīti masīva elementi. Ja tajā ir viens elements, tas jau tiek uzskatīts par sakārtotu, un algoritms atgriezīs to pašu masīvu bez izmaiņām.
- Ja masīvā ir vairāk nekā viens elements, algoritms to sadala divās daļās: kreisajā pusē un labajā pusē.
- Pēc tam sapludināšanas kārtošanas algoritms tiek rekursīvi piemērots masīva kreisajā un labajā pusē, efektīvi sadalot tos mazākos apakšblokos un šķirojot tos atsevišķi.
- Šis rekursīvais process turpinās, līdz katrā apakšmasīvā ir tikai viens elements (kā norādīts 1. darbībā), un tad tos var apvienot, lai izveidotu galīgo, sakārtotu izvades masīvu.
4.2 Apvienot
Tagad mēs redzēsim masīvu sapludināšanas darbības:
- Pirmais sapludināšanas kārtošanas algoritma solis ietver tukša masīva izveidi.
- Pēc tam algoritms salīdzina ievades masīva kreisās un labās puses pirmos elementus.
- Mazākais no diviem elementiem tiek pievienots jaunajam masīvam un pēc tam noņemts no attiecīgās ievades masīva puses.
- Pēc tam 2.-3. darbību atkārto, līdz viena no pusēm ir iztukšota.
- Visi atlikušie elementi netukšā pusē pēc tam tiek pievienoti jaunajam masīvam.
- Iegūtais masīvs tagad ir pilnībā sakārtots un atspoguļo sapludināšanas kārtošanas algoritma galīgo izvadi.
5. Merge Sort ieviešana programmā C++
Lai ieviestu sapludināšanas kārtošanu programmā C++, tiek izmantotas divas dažādas metodes. Abu metožu laika sarežģītība ir līdzvērtīga, taču to pagaidu apakšgrupu izmantošana atšķiras.
Pirmā sapludināšanas kārtošanas metode programmā C++ izmanto divus pagaidu apakšmasīvus, bet otrā izmanto tikai vienu. Ir vērts atzīmēt, ka divu pagaidu apakšmasīvu kopējais izmērs pirmajā metodē ir vienāds ar sākotnējā masīva lielumu otrajā metodē, tāpēc telpas sarežģītība paliek nemainīga.
1. metode – divu temp apakšreižu izmantošana
Šeit ir programmas piemērs sapludināšanas kārtošanai programmā C++, izmantojot 1. metodi, kurā tiek izmantoti divi pagaidu apakšbloki:
#includeizmantojot namespace std ;
nederīgs sapludināt ( starpt arr [ ] , starpt l , starpt m , starpt r )
{
starpt n1 = m - l + 1 ;
starpt n2 = r - m ;
starpt L [ n1 ] , R [ n2 ] ;
priekš ( starpt i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ l + i ] ;
priekš ( starpt j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
starpt i = 0 , j = 0 , k = l ;
kamēr ( i < n1 && j < n2 ) {
ja ( L [ i ] <= R [ j ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
cits {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
kamēr ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
kamēr ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
nederīgs sapludinātSort ( starpt arr [ ] , starpt l , starpt r )
{
ja ( l < r ) {
starpt m = l + ( r - l ) / 2 ;
sapludinātSort ( arr , l , m ) ;
sapludinātSort ( arr , m + 1 , r ) ;
sapludināt ( arr , l , m , r ) ;
}
}
starpt galvenais ( )
{
starpt arr [ ] = { 12 , vienpadsmit , 13 , 5 , 6 , 7 } ;
starpt arr_size = izmērs ( arr ) / izmērs ( arr [ 0 ] ) ;
cout << 'Dotais masīvs ir \n ' ;
priekš ( starpt i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
sapludinātSort ( arr , 0 , arr_size - 1 ) ;
cout << ' \n Sakārtots masīvs ir \n ' ;
priekš ( starpt i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
atgriezties 0 ;
}
Šajā programmā sapludināšanas funkcija izmanto trīs argumentus arr, l un r, kas attēlo kārtojamo masīvu un parāda apvienojamās apakšmasīvas indeksus. Funkcija vispirms atrod divu sapludināmo apakšbloku izmērus, pēc tam izveido divus pagaidu apakšblokus L un R, lai saglabātu šo apakšbloku elementus. Pēc tam tas salīdzina L un R elementus un apvieno tos sākotnējā masīvā ar nosaukumu arr augošā secībā.
Dalīšanas un iekarošanas paņēmienu izmanto funkcija mergeSort, lai sadalītu masīvu divās daļās rekursīvi, līdz apakšmasīvā paliek tikai viens elements. Pēc tam tas apvieno abas apakšgrupas sakārtotā apakšgrupā. Funkcija turpina apvienot apakšmasīvus, ja vien tā nekārto visu masīvu.
Galvenajā funkcijā mēs definējam masīvu arr ar 6 elementiem un izsaucam mergeSort funkciju, lai to sakārtotu. Koda beigās tiek izdrukāts sakārtotais masīvs.
2. metode — vienas pagaidu apakšsistēmas izmantošana
Šeit ir programmas piemērs sapludināšanas kārtošanai programmā C++, izmantojot 2. metodi, kas izmanto vienu pagaidu apakšmasu:
#includeizmantojot namespace std ;
nederīgs sapludināt ( starpt arr [ ] , starpt l , starpt m , starpt r )
{
starpt i , j , k ;
starpt n1 = m - l + 1 ;
starpt n2 = r - m ;
// Izveidot pagaidu apakšgrupas
starpt L [ n1 ] , R [ n2 ] ;
// Kopēt datus apakšblokos
priekš ( i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ l + i ] ;
priekš ( j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
// Apvienojiet pagaidu apakšmasīvus atpakaļ sākotnējā masīvā
i = 0 ;
j = 0 ;
k = l ;
kamēr ( i < n1 && j < n2 ) {
ja ( L [ i ] <= R [ j ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
cits {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
// Kopējiet atlikušos L[] elementus
kamēr ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
// Kopējiet atlikušos R [] elementus
kamēr ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
nederīgs sapludinātSort ( starpt arr [ ] , starpt l , starpt r )
{
ja ( l < r ) {
starpt m = l + ( r - l ) / 2 ;
// Kārtot kreiso un labo pusi rekursīvi
sapludinātSort ( arr , l , m ) ;
sapludinātSort ( arr , m + 1 , r ) ;
// Apvienojiet abas sakārtotās puses
sapludināt ( arr , l , m , r ) ;
}
}
starpt galvenais ( )
{
starpt arr [ ] = { 12 , vienpadsmit , 13 , 5 , 6 , 7 } ;
starpt arr_size = izmērs ( arr ) / izmērs ( arr [ 0 ] ) ;
cout << 'Dotais masīvs ir \n ' ;
priekš ( starpt i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
sapludinātSort ( arr , 0 , arr_size - 1 ) ;
cout << ' \n Sakārtots masīvs ir \n ' ;
priekš ( starpt i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
atgriezties 0 ;
}
Šī programma ir līdzīga iepriekšējai, bet tā vietā, lai izmantotu divus pagaidu apakšgrupas L un R, tā izmanto vienu pagaidu apakšstrāvas temp. Apvienošanas funkcija darbojas tāpat kā iepriekš, taču tā vietā, lai kopētu datus uz L un R, tā kopē tos uz temp. Pēc tam tas apvieno pagaidu masīva elementus atpakaļ arr kas ir sākotnējais masīvs.
Funkcija mergeSort ir tāda pati kā iepriekš, izņemot to, ka pagaidu apakšgrupas glabāšanai tā izmanto temp, nevis L un R.
Galvenajā funkcijā mēs definējam masīvu arr ar 6 elementiem un izsaucam mergeSort funkciju, lai to sakārtotu. Koda izpilde beidzas, izdrukājot sakārtoto masīvu uz ekrāna.
Secinājums
Sapludināšanas kārtošana ir algoritms, kas kārto masīva elementus, un tas izmanto sadalīšanas un iekarošanas paņēmienu un salīdzina elementus. Sapludināšanas kārtošanai programmā C++ ir laika sarežģītība O(n log n), un tā ir īpaši efektīva lielu masīvu kārtošanai. Lai gan tam ir nepieciešama papildu atmiņa, lai saglabātu apvienotos apakšblokus, tā stabilitāte padara to par populāru izvēli šķirošanai.