Sisällysluettelo
- Johdanto
- Mikä on Merge Sort C++:ssa
- hajota ja hallitse -lähestymistapa
- Yhdistä lajittelualgoritmi
- Merge Sort -sovelluksen käyttöönotto C++:ssa
- Johtopäätös
1. Esittely
Tietojenkäsittelytieteen lajittelualgoritmeja käytetään tietojen järjestämiseen nousevaan tai laskevaan järjestykseen. Saatavilla on useita lajittelualgoritmeja, joilla on erilliset ominaisuudet. Yhdistämislajittelu on yksi C++:n menetelmistä, joka voi lajitella taulukoita.
2. Mikä on Merge Sort C++:ssa
Yhdistämislajittelu käyttää jakaa ja hallitse -tekniikkaa, jolla voidaan järjestää taulukon elementit. Se voi myös lajitella elementtiluettelon C++:ssa. Se jakaa syötteen kahteen puolikkaaseen, lajittelee molemmat puolikkaat itsenäisesti ja yhdistää ne sitten oikeaan järjestykseen.
3. hajota ja hallitse -lähestymistapa
Lajittelualgoritmi soveltaa jaa ja hallitse -strategiaa, joka tarkoittaa syötetaulukon osiointia pienempiin aliryhmiin, niiden ratkaisemista erikseen ja tulosten yhdistämistä lajiteltujen tulosteiden tuottamiseksi. Yhdistetyssä lajittelussa taulukko jaetaan rekursiivisesti kahteen puolikkaaseen, kunnes kumpaankin puolikkaaseen jää vain yksi elementti.
4. Yhdistä lajittelualgoritmi
Yhdistämislajittelualgoritmi koostuu kahdesta päävaiheesta: jakamisesta ja yhdistämisestä. Vaiheet ovat seuraavat:
4.1 Jaa
Yhdistämislajittelualgoritmi noudattaa jakaa ja hallitse -strategiaa taulukon elementtien lajittelussa.
- Algoritmin ensimmäinen vaihe tarkistaa taulukon elementit. Jos se sisältää yhden elementin, sitä pidetään jo lajiteltuna ja algoritmi palauttaa saman taulukon ilman muutoksia.
- Jos taulukko sisältää useamman kuin yhden elementin, algoritmi jakaa sen kahteen puolikkaaseen: vasempaan ja oikeaan.
- Yhdistämislajittelualgoritmia sovelletaan sitten rekursiivisesti taulukon vasempaan ja oikeaan puoliskoon, jakaen ne tehokkaasti pienempiin aliryhmiin ja lajittelevat ne yksitellen.
- Tämä rekursiivinen prosessi jatkuu, kunnes alitaulukot sisältävät vain yhden elementin kukin (vaiheen 1 mukaisesti), jolloin ne voidaan yhdistää lopullisen, lajiteltujen tulosteiden muodostamiseksi.
4.2 Yhdistä
Nyt näemme vaiheet taulukoiden yhdistämiseksi:
- Yhdistämislajittelualgoritmin ensimmäinen vaihe sisältää tyhjän taulukon luomisen.
- Tämän jälkeen algoritmi vertailee syötetaulukon vasemman ja oikean puoliskon ensimmäisiä elementtejä.
- Pienempi kahdesta elementistä lisätään uuteen taulukkoon ja poistetaan sitten vastaavasta puoliskosta syöttötaulukosta.
- Vaiheet 2-3 toistetaan sitten, kunnes toinen puoliskoista on tyhjennetty.
- Muut kuin tyhjän puolikkaan jäljellä olevat elementit lisätään sitten uuteen taulukkoon.
- Tuloksena oleva matriisi on nyt täysin lajiteltu ja edustaa yhdistämislajittelualgoritmin lopullista tulosta.
5. Yhdistämislajittelun toteutus C++:ssa
Yhdistämisen toteuttamiseksi C++:ssa noudatetaan kahta eri menetelmää. Molempien menetelmien aikamonimutkaisuus on sama, mutta niiden käyttö väliaikaisten aliryhmien välillä on erilaista.
Ensimmäinen yhdistelylajittelumenetelmä C++:ssa käyttää kahta väliaikaista alitaulukkoa, kun taas toinen vain yhtä. On syytä huomata, että kahden väliaikaisen alitaulukon kokonaiskoko ensimmäisessä menetelmässä on yhtä suuri kuin alkuperäisen taulukon koko toisessa menetelmässä, joten tilan monimutkaisuus pysyy vakiona.
- Tapa 1 – Kahden lämpötila-alijärjestelmän käyttäminen
- Tapa 2 – Yhden tilapäisen alijärjestelmän käyttäminen
Tapa 1 – Kahden lämpötila-alijärjestelmän käyttäminen
Tässä on esimerkkiohjelma C++:n yhdistämislajittelulle menetelmällä 1, joka käyttää kahta väliaikaista aliryhmää:
#includekäyttäen nimiavaruutta std ;
mitätön yhdistää ( int arr [ ] , int l , int m , int r )
{
int n1 = m - l + 1 ;
int n2 = r - m ;
int L [ n1 ] , R [ n2 ] ;
varten ( int i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ l + i ] ;
varten ( int j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
int i = 0 , j = 0 , k = l ;
sillä aikaa ( i < n1 && j < n2 ) {
jos ( L [ i ] <= R [ j ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
muu {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
sillä aikaa ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
sillä aikaa ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
mitätön Yhdistä lajittelu ( int arr [ ] , int l , int r )
{
jos ( l < r ) {
int m = l + ( r - l ) / 2 ;
Yhdistä lajittelu ( arr , l , m ) ;
Yhdistä lajittelu ( arr , m + 1 , r ) ;
yhdistää ( arr , l , m , r ) ;
}
}
int pää ( )
{
int arr [ ] = { 12 , yksitoista , 13 , 5 , 6 , 7 } ;
int arr_size = koko ( arr ) / koko ( arr [ 0 ] ) ;
cout << 'Annettu joukko on \n ' ;
varten ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
Yhdistä lajittelu ( arr , 0 , arr_size - 1 ) ;
cout << ' \n Lajiteltu matriisi on \n ' ;
varten ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
palata 0 ;
}
Tässä ohjelmassa yhdistämisfunktio ottaa kolme argumenttia arr, l ja r, jotka edustavat lajiteltavaa taulukkoa ja näyttävät yhdistettävän alitaulukon indeksit. Funktio etsii ensin kahden yhdistettävän alitaulukon koot ja luo sitten kaksi väliaikaista alitaulukkoa L ja R näiden aliryhmien elementtien tallentamiseksi. Sitten se vertaa L:n ja R:n elementtejä ja yhdistää ne alkuperäiseen taulukkoon nimeltä arr nousevassa järjestyksessä.
MergeSort-funktio käyttää jakaa ja hallitse -tekniikkaa taulukon jakamiseen rekursiivisesti kahteen puolikkaaseen, kunnes alitaulukosta on jäljellä vain yksi elementti. Sitten se yhdistää kaksi aliryhmää lajiteltuun alitaulukkoon. Funktio jatkaa aliryhmien yhdistämistä, ellei se lajittele koko taulukkoa.
Pääfunktiossa määrittelemme taulukon arr, jossa on 6 elementtiä ja kutsumme mergeSort-funktiota lajittelemaan sen. Koodin lopussa tulostetaan lajiteltu matriisi.
Tapa 2 – Yhden tilapäisen alijärjestelmän käyttäminen
Tässä on esimerkkiohjelma C++:n yhdistämislajittelulle menetelmällä 2, joka käyttää yhtä väliaikaista alitaulukkoa:
#includekäyttäen nimiavaruutta std ;
mitätön yhdistää ( int arr [ ] , int l , int m , int r )
{
int i , j , k ;
int n1 = m - l + 1 ;
int n2 = r - m ;
// Luo väliaikaisia aliryhmiä
int L [ n1 ] , R [ n2 ] ;
// Kopioi tiedot aliryhmiin
varten ( i = 0 ; i < n1 ; i ++ )
L [ i ] = arr [ l + i ] ;
varten ( j = 0 ; j < n2 ; j ++ )
R [ j ] = arr [ m + 1 + j ] ;
// Yhdistä väliaikaiset aliryhmät takaisin alkuperäiseen taulukkoon
i = 0 ;
j = 0 ;
k = l ;
sillä aikaa ( i < n1 && j < n2 ) {
jos ( L [ i ] <= R [ j ] ) {
arr [ k ] = L [ i ] ;
i ++;
}
muu {
arr [ k ] = R [ j ] ;
j ++;
}
k ++;
}
// Kopioi L[]:n loput elementit
sillä aikaa ( i < n1 ) {
arr [ k ] = L [ i ] ;
i ++;
k ++;
}
// Kopioi loput R[]:n elementit
sillä aikaa ( j < n2 ) {
arr [ k ] = R [ j ] ;
j ++;
k ++;
}
}
mitätön Yhdistä lajittelu ( int arr [ ] , int l , int r )
{
jos ( l < r ) {
int m = l + ( r - l ) / 2 ;
// Lajittele vasen ja oikea puolisko rekursiivisesti
Yhdistä lajittelu ( arr , l , m ) ;
Yhdistä lajittelu ( arr , m + 1 , r ) ;
// Yhdistä kaksi lajiteltua puolikasta
yhdistää ( arr , l , m , r ) ;
}
}
int pää ( )
{
int arr [ ] = { 12 , yksitoista , 13 , 5 , 6 , 7 } ;
int arr_size = koko ( arr ) / koko ( arr [ 0 ] ) ;
cout << 'Annettu joukko on \n ' ;
varten ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
Yhdistä lajittelu ( arr , 0 , arr_size - 1 ) ;
cout << ' \n Lajiteltu matriisi on \n ' ;
varten ( int i = 0 ; i < arr_size ; i ++ )
cout << arr [ i ] << ' ' ;
palata 0 ;
}
Tämä ohjelma on kuin edellinen, mutta kahden väliaikaisen aliryhmän L ja R sijasta se käyttää yhtä väliaikaista aliryhmälämpötilaa. Yhdistämistoiminto toimii samalla tavalla kuin ennenkin, mutta sen sijaan, että se kopioi tiedot L- ja R-kirjaimeen, se kopioi sen temp. Sitten se yhdistää väliaikaiset taulukon elementit takaisin arr joka on alkuperäinen taulukko.
MergeSort-funktio on sama kuin ennen, paitsi että se käyttää temp-komentoa L:n ja R:n sijaan väliaikaisen alitaulukon tallentamiseen.
Pääfunktiossa määrittelemme taulukon arr, jossa on 6 elementtiä ja kutsumme mergeSort-funktiota lajittelemaan sen. Koodin suoritus päättyy tulostamalla lajiteltu matriisi näytölle.
Johtopäätös
Yhdistämislajittelu on taulukon elementtejä lajitteleva algoritmi, joka käyttää jaa ja hallitse -tekniikkaa ja vertailee elementtejä. C++:n yhdistämislajittelun aikamonimutkaisuus on O(n log n), ja se on erityisen tehokas suurten taulukoiden lajittelussa. Vaikka se vaatii lisämuistia yhdistettyjen aliryhmien tallentamiseen, sen vakaus tekee siitä suositun valinnan lajitteluun.