Sisukord
- Sissejuhatus
- Mis on C++-s Merge Sort
- Jaga ja valluta lähenemisviis
- Sorteerimisalgoritmi ühendamine
- Merge Sort'i rakendamine C++-s
- Järeldus
1. Sissejuhatus
Arvutiteaduses kasutatakse sortimisalgoritme andmete järjestamiseks kasvavas või kahanevas järjekorras. Saadaval on mitu sortimisalgoritmi, millel on erinevad omadused. Ühenda sortimine on üks C++ meetoditest, mis saab massiive sortida.
2. Mis on Merge Sort C++ keeles
Ühenda sortimine kasutab jaga ja valluta tehnikat, mis võimaldab järjestada massiivi elemente. See võib sortida ka C++ elementide loendit. See jagab sisendi kaheks pooleks, sorteerib mõlemad pooled eraldi ja liidab need seejärel õiges järjekorras.
3. Jaga ja valluta lähenemisviis
Sorteerimisalgoritm rakendab jaga ja valluta strateegiat, mis hõlmab sisendmassiivi jaotamist väiksemateks alammassiivideks, nende eraldi lahendamist ja seejärel tulemuste liitmist sorteeritud väljundi saamiseks. Liitmissortimise korral jagatakse massiiv rekursiivselt kaheks pooleks, kuni kummassegi poole jääb ainult üks element.
4. Ühenda sortimise algoritm
Ühendamissortimisalgoritm koosneb kahest põhietapist: jagamine ja liitmine. Toimingud on järgmised.
4.1 Jaga
Ühendamissortimisalgoritm järgib massiivi elementide sortimiseks jaga ja valluta strateegiat.
- Algoritmi esimene samm kontrollib massiivi elemente. Kui see sisaldab ühte elementi, loetakse see juba sorteerituks ja algoritm tagastab sama massiivi ilma muudatusteta.
- Kui massiiv sisaldab rohkem kui ühte elementi, jagab algoritm selle kaheks pooleks: vasak pool ja parem pool.
- Ühendamissortimisalgoritmi rakendatakse seejärel rekursiivselt massiivi vasakule ja paremale poolele, jagades need tõhusalt väiksemateks alamribadeks ja sorteerides need eraldi.
- See rekursiivne protsess jätkub seni, kuni alammassiivid sisaldavad ainult ühte elementi (nagu 1. etapis), misjärel saab need liita lõpliku sorteeritud väljundmassiivi saamiseks.
4.2 Ühenda
Nüüd näeme massiivide liitmise samme:
- Ühendamissortimisalgoritmi esimene samm hõlmab tühja massiivi loomist.
- Seejärel jätkab algoritm sisendmassiivi vasaku ja parema poole esimeste elementide võrdlemist.
- Kahest elemendist väiksem lisatakse uude massiivi ja seejärel eemaldatakse sisendmassiivi vastavast poolest.
- Seejärel korratakse samme 2-3, kuni üks pool on tühjenenud.
- Seejärel lisatakse uude massiivi kõik ülejäänud mittetühja poole elemendid.
- Saadud massiiv on nüüd täielikult sorteeritud ja esindab liitmissortimisalgoritmi lõplikku väljundit.
5. Merge Sorti rakendamine C++ keeles
Ühendamise sortimise rakendamiseks C++-s järgitakse kahte erinevat meetodit. Mõlema meetodi ajaline keerukus on samaväärne, kuid nende ajutiste alamkihtide kasutamine on erinev.
Esimene C++ ühendamise sortimise meetod kasutab kahte ajutist alamkihti, teine aga ainult ühte. Väärib märkimist, et esimese meetodi kahe ajutise alammassiivi kogusuurus on võrdne teise meetodi algse massiivi suurusega, seega jääb ruumi keerukus konstantseks.
1. meetod – kahe temp-alakihi kasutamine
Siin on näide C++-s ühendamise sortimiseks, kasutades meetodit 1, mis kasutab kahte ajutist alamkihti:
#includekasutades nimeruumi std ;
tühine liita ( int arr [ ] , int l , int m , int r )
{
int n1 = m - l + 1 ;
int n2 = r - m ;
int L [ n1 ] , R [ n2 ] ;
jaoks ( int i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ l + i ] ;
jaoks ( int j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
int i = 0 , j = 0 , k = l ;
samal ajal ( i < n1 && j < n2 ) {
kui ( L [ i ] <= R [ j ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
muidu {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
samal ajal ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
samal ajal ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
tühine mergeSort ( int arr [ ] , int l , int r )
{
kui ( l < r ) {
int m = l + ( r - l ) / 2 ;
mergeSort ( arr , l , m ) ;
mergeSort ( arr , m + 1 , r ) ;
liita ( arr , l , m , r ) ;
}
}
int peamine ( )
{
int arr [ ] = { 12 , üksteist , 13 , 5 , 6 , 7 } ;
int arr_size = suurus ( arr ) / suurus ( arr [ 0 ] ) ;
cout << 'Antud massiiv on \n ' ;
jaoks ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
mergeSort ( arr , 0 , arr_size - 1 ) ;
cout << ' \n Sorteeritud massiiv on \n ' ;
jaoks ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
tagasi 0 ;
}
Selles programmis võtab liitmisfunktsioon kolm argumenti arr, l ja r, mis tähistavad sortitavat massiivi ja näitavad ühendatava alammassiivi indekseid. Funktsioon otsib esmalt kahe liidetava alamkiibi suurused, seejärel loob kaks ajutist alamriba L ja R, et salvestada nende alamkiibi elemendid. Seejärel võrdleb see L ja R elemente ning liidab need nimega algsesse massiivi arr kasvavas järjekorras.
Jaga ja valluta tehnikat kasutab mergeSort funktsioon, et jagada massiiv rekursiivselt kaheks pooleks, kuni alammassiivist jääb välja ainult üks element. Seejärel liidab see kaks alamriba sorteeritud alamrehviks. Funktsioon jätkab alammassiivide ühendamist, välja arvatud juhul, kui see sorteerib kogu massiivi.
Põhifunktsioonis defineerime 6 elemendiga massiivi arr ja kutsume selle sortimiseks funktsiooni mergeSort. Koodi lõpus trükitakse sorteeritud massiiv.
2. meetod – ühe ajutise alamriba kasutamine
Siin on näide C++-s ühendamise sortimiseks, kasutades meetodit 2, mis kasutab ühte ajutist alamriba:
#includekasutades nimeruumi std ;
tühine liita ( int arr [ ] , int l , int m , int r )
{
int i , j , k ;
int n1 = m - l + 1 ;
int n2 = r - m ;
// Ajutiste alamkihtide loomine
int L [ n1 ] , R [ n2 ] ;
// Andmete kopeerimine alamkihtidesse
jaoks ( i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ l + i ] ;
jaoks ( j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
// Ühendage ajutised alammassiivid tagasi algsesse massiivi
i = 0 ;
j = 0 ;
k = l ;
samal ajal ( i < n1 && j < n2 ) {
kui ( L [ i ] <= R [ j ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
muidu {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
// Kopeerige L[] ülejäänud elemendid
samal ajal ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
// Kopeerige ülejäänud R[] elemendid
samal ajal ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
tühine mergeSort ( int arr [ ] , int l , int r )
{
kui ( l < r ) {
int m = l + ( r - l ) / 2 ;
// Sorteerib rekursiivselt vasakut ja paremat poolt
mergeSort ( arr , l , m ) ;
mergeSort ( arr , m + 1 , r ) ;
// Ühendage kaks sorteeritud poolt
liita ( arr , l , m , r ) ;
}
}
int peamine ( )
{
int arr [ ] = { 12 , üksteist , 13 , 5 , 6 , 7 } ;
int arr_size = suurus ( arr ) / suurus ( arr [ 0 ] ) ;
cout << 'Antud massiiv on \n ' ;
jaoks ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
mergeSort ( arr , 0 , arr_size - 1 ) ;
cout << ' \n Sorteeritud massiiv on \n ' ;
jaoks ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
tagasi 0 ;
}
See programm on nagu eelmine, kuid kahe ajutise alamriba L ja R asemel kasutab see ühte ajutist alamriba temp. Ühendamise funktsioon töötab samamoodi nagu varem, kuid selle asemel, et kopeerida andmed L ja R, kopeerib see temp. Seejärel liidab see ajutised massiivi elemendid tagasi arr mis on algne massiiv.
Funktsioon mergeSort on sama, mis varem, välja arvatud see, et see kasutab ajutise alamriba salvestamiseks L ja R asemel temp.
Põhifunktsioonis defineerime 6 elemendiga massiivi arr ja kutsume selle sortimiseks funktsiooni mergeSort. Koodi täitmine lõpeb sorteeritud massiivi printimisega ekraanile.
Järeldus
Ühenda sortimine on algoritm, mis sorteerib massiivi elemente ning kasutab jaga ja valluta tehnikat ning võrdleb elemente. Ühenda sortimise C++ ajaline keerukus on O(n log n) ja see on eriti tõhus suurte massiivide sortimisel. Kuigi see nõuab ühendatud alamkihtide salvestamiseks lisamälu, muudab selle stabiilsus sortimiseks populaarseks valikuks.