Yhdistä lajittelu

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 6. lokakuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 47 muokkausta .
Yhdistä lajittelu

Yhdistämislajitteluesimerkki. Ensin jaetaan lista osiin (1 elementti kussakin), sitten verrataan jokaista elementtiä naapuriinsa, lajitellaan ja yhdistetään. Tämän seurauksena kaikki elementit lajitellaan ja yhdistetään yhteen.
Tekijä Johannes von Neumann
tarkoitus Lajittelualgoritmi
Tietorakenne lista , joukko
pahin aika
Paras aika
Keskimääräinen aika
Muistin hinta listalle, taulukolle
 Mediatiedostot Wikimedia Commonsissa

Yhdistämislajittelu on lajittelualgoritmi  , joka järjestää luettelot (tai muut tietorakenteet , joiden elementteihin pääsee vain peräkkäin , esimerkiksi virrat ) tiettyyn järjestykseen. Tämä lajittelu on hyvä esimerkki hajota ja hallitse -periaatteen käytöstä . Ensin tehtävä on jaettu useisiin pienempiin osatehtäviin. Nämä tehtävät ratkaistaan ​​sitten rekursiivisella kutsulla tai suoraan, jos niiden koko on tarpeeksi pieni. Lopuksi niiden ratkaisut yhdistetään ja saadaan ratkaisu alkuperäiseen ongelmaan.

Yksityiskohtainen lajittelualgoritmi

Lajitteluongelman ratkaisemiseksi nämä kolme vaihetta näyttävät tältä:

  1. Lajiteltava taulukko jaetaan kahteen suunnilleen samankokoiseen osaan;
  2. Jokainen tuloksena olevista osista lajitellaan erikseen, esimerkiksi samalla algoritmilla;
  3. Kaksi puolikokoista järjestettyä taulukkoa yhdistetään yhdeksi.

1.1. — 2.1. Tehtävän rekursiivinen osiointi pienempiin osioihin tapahtuu, kunnes taulukon koko saavuttaa yhden (mikä tahansa taulukko, jonka pituus on 1, voidaan katsoa järjestetyksi).

3.1. Kahden järjestetyn taulukon yhdistäminen yhdeksi.
Perusidea kahden lajitellun taulukon yhdistämisestä voidaan selittää seuraavalla esimerkillä. Oletetaan, että meillä on kaksi aliryhmää jo lajiteltuna nousevaan järjestykseen. Sitten:
3.2. Kahden alitaulukon yhdistäminen kolmanteen tuloksena olevaan taulukkoon.
Jokaisessa vaiheessa otamme pienemmän alitaulukoiden kahdesta ensimmäisestä elementistä ja kirjoitamme sen tuloksena olevaan taulukkoon. Tuloksena olevan taulukon ja alitaulukon, josta elementti on otettu, alkioiden lukumäärän laskureita kasvatetaan yhdellä.
3.3. Lopun "liittäminen".
Kun yksi alitaulukoista on ohi, lisäämme kaikki toisen alitaulukon jäljellä olevat elementit tuloksena olevaan taulukkoon.

Lajitteluesimerkki C:ssä

/** * Lajittelee taulukon käyttämällä rekursiivista yhdistämistä lajittelu * ylös - osoitin lajiteltavaan taulukkoon * alas - osoitin taulukkoon, jonka koko on vähintään yhtä suuri kuin 'ylös', käytetään puskurina * taulukon vasen - vasen reuna, välitä 0 lajittele taulukko alusta * oikea - taulukon oikea reuna, välitä taulukon pituus - 1 lajittele taulukko viimeiseen elementtiin * palauttaa: osoitin lajiteltuun taulukkoon. Johtuen tämän toteutuksen toiminnasta * taulukon lajiteltu versio voi päätyä joko ylös tai alas **/ int * merge_sort ( int * ylös , int * alas , unsigned int vasen , unsigned int oikea ) { jos ( vasen == oikea ) { alas [ vasen ] = ylös [ vasen ]; palaa alas ; } unsigned int middle = vasen + ( oikea - vasen ) / 2 ; // jaa ja lajittele int * l_buff = merge_sort ( ylös , alas , vasen , keskellä ); int * r_buff = merge_sort ( ylös , alas , keski + 1 , oikea ); // yhdistää kaksi lajiteltua puolikasta int * target = l_buff == ylös ? alas : ylös ; unsigned int l_cur = vasen , r_cur = keski + 1 ; for ( unsigned int i = vasen ; i <= oikea ; i ++ ) { if ( l_cur <= keski && r_cur <= oikea ) { if ( l_buff [ l_cur ] < r_buff [ r_cur ]) { kohde [ i ] = l_buff [ l_cur ]; l_cur ++ ; } muu { kohde [ i ] = r_buff [ r_cur ]; r_cur ++ ; } } else if ( l_cur <= middle ) { kohde [ i ] = l_buff [ l_cur ]; l_cur ++ ; } muu { kohde [ i ] = r_buff [ r_cur ]; r_cur ++ ; } } paluutavoite ; _ }

Toteutus C++11 :ssä:

#include <algoritmi> #include <cstddef> #include <iteraattori> #sisällytä <muisti> malli < typenameT > _ void merge_sort ( T array [], std :: size_t size ) noexcept { jos ( koko > 1 ) { std :: koko_t const vasen_koko = koko / 2 ; std :: koko_t const oikea_koko = koko - vasen_koko ; merge_sort ( & array [ 0 ], left_size ); merge_sort ( & array [ left_size ], right_size ); std :: koko_t lidx = 0 , ridx = vasen_koko , idx = 0 ; std :: ainutlaatuinen_ptr < T [] > tmp_array ( uusi T [ koko ]); while ( lidx < vasen_koko || ridx < koko ) { if ( array [ lidx ] < array [ ridx ]) { tmp_array [ idx ++ ] = std :: siirrä ( array [ lidx ]); lidx ++ ; } muu { tmp_array [ idx ++ ] = std :: siirrä ( array [ ridx ]); ridx ++ ; } jos ( lidx == vasen_size ) { std :: kopioi ( std :: make_move_iterator ( & array [ ridx ]), std :: make_move_iterator ( & array [ koko ]), & tmp_array [ idx ]); tauko ; } jos ( ridx == koko ) { std :: kopioi ( std :: make_move_iterator ( & array [ lidx ]), std :: make_move_iterator ( & array [ left_size ]), & tmp_array [ idx ]); tauko ; } } std :: kopioi ( std :: make_move_iterator ( tmp_array ), std :: make_move_iterator ( & tmp_array [ koko ]), joukko ); } }

Toteutus C++14 :ssä OpenMP -rinnakkaisuudella

#include <algoritmi> #include <iteraattori> #include <omp.h> #sisällytä <muisti> malli < typenameIterator > _ void mergesort ( Iteraattori alkaen , Iteraattori kohteeseen ) { #pragma omp rinnakkain { #pragma omp single nowait static_assert ( ! std :: on_sama < tyypinnimi std :: iteraattorin_ominaisuudet < Iteraattori >:: arvotyyppi , void >:: arvo ); auto n = std :: etäisyys ( mistä , kohteeseen ); jos ( 1 < n ) { #pragma omp tehtävä firstprivate (from, to, n) { Iteraattori l_from = from ; Iteraattori l_to = l_from ; std :: eteenpäin ( l_to , n / 2 ); mergesort ( l_from , l_to ); } #pragma omp tehtävä firstprivate (from, to, n) { Iteraattori r_from = from ; std :: advance ( r_from , n / 2 ); Iteraattori r_to = r_from ; std :: eteenpäin ( r_to , n - ( n / 2 )); mergesort ( r_from , r_to ); } #pragma omp taskwait auto tmp_array = std :: make_unique < typename Iterator :: value_type [] > ( n ); Iteraattori l_iter = alkaen ; Iteraattori l_end = l_iter ; std :: advance ( l_end , n / 2 ); Iteraattori r_iter = l_end ; Iteraattori & r_end = to ; auto tmp_iter = tmp_array . saada (); while ( l_iter != l_end || r_iter != r_end ) { if ( * l_iter < * r_iter ) { * tmp_iter = std :: siirrä ( * l_iter ); ++ l_iter ; ++ tmp_iter ; } muu { * tmp_iter = std :: siirrä ( * r_iter ); ++ r_iter ; ++ tmp_iter ; } if ( l_iter == l_end ) { std :: kopioi ( std :: make_move_iterator ( r_iter ), std :: make_move_iterator ( r_end ), tmp_iter ); tauko ; } if ( r_iter == r_end ) { std :: kopioi ( std :: make_move_iterator ( l_iter ), std :: make_move_iterator ( l_end ), tmp_iter ); tauko ; } } std :: kopioi ( std :: make_move_iterator ( tmp_array.get ( ) ), std :: make_move_iterator ( & tmp_array [ n ]), alkaen ); } } }

Iteratiivinen toteutus C++ :ssa :

malli < typenameT > _ void MergeSort ( T a [], koko_t l ) { size_t BlockSizeIterator ; size_t BlockIterator ; size_t LeftBlockIterator ; size_t RightBlockIterator ; size_t MergeIterator ; size_t LeftBorder ; size_t MidBorder ; size_t RightBorder ; for ( BlockSizeIterator = 1 ; BlockSizeIterator < l ; BlockSizeIterator *= 2 ) { for ( BlockIterator = 0 ; BlockIterator < l - BlockSizeIterator ; BlockIterator += 2 * BlockSizeIterator ) { //Yhdistetään lajittelemalla lohkopari alkaen BlockIterator-elementistä //vasen BlockSizeIterator-kokoinen, oikea BlockSizeIterator-kokoinen tai pienempi LeftBlockIterator = 0 ; RightBlockIterator = 0 ; LeftBorder = BlockIterator ; MidBorder = BlockIterator + BlockSizeIterator ; RightBorder = BlockIterator + 2 * BlockSizeIterator ; RightBorder = ( RightBorder < l ) ? Oikea reuna : l ; int * SortedBlock = uusi int [ RightBorder - LeftBorder ]; //Kun molemmissa taulukoissa on elementtejä, valitse pienempi ja laita se lajiteltuun lohkoon samalla ( LeftBorder + LeftBlockIterator < MidBorder && MidBorder + RightBlockIterator < RightBorder ) { if ( a [ LeftBorder + LeftBlockIterator ] < a [ MidBorder + RightBlockIterator ]) { SortedBlock [ LeftBlockIterator + RightBlockIterator ] = a [ LeftBorder + LeftBlockIterator ]; LeftBlockIterator += 1 ; } muu { SortedBlock [ LeftBlockIterator + RightBlockIterator ] = a [ MidBorder + RightBlockIterator ]; RightBlockIterator += 1 ; } } //Sen jälkeen tuomme jäljellä olevat elementit vasemmasta tai oikeasta lohkosta samalla kun ( LeftBorder + LeftBlockIterator < MidBorder ) { SortedBlock [ LeftBlockIterator + RightBlockIterator ] = a [ LeftBorder + LeftBlockIterator ]; LeftBlockIterator += 1 ; } while ( MidBorder + RightBlockIterator < RightBorder ) { SortedBlock [ LeftBlockIterator + RightBlockIterator ] = a [ MidBorder + RightBlockIterator ]; RightBlockIterator += 1 ; } for ( MergeIterator = 0 ; MergeIterator < LeftBlockIterator + RightBlockIterator ; MergeIterator ++ ) { a [ LeftBorder + MergeIterator ] = Lajiteltu lohko [ MergeIterator ]; } poista SortedBlock ; } } }


Toteutus Pythonissa :

def merge_sort ( A ): jos len ( A ) == 1 tai len ( A ) == 0 : palauttaa A L = yhdistä_lajittelu ( A [: len ( A ) // 2 ]) R = yhdistä_lajittelu ( A [ len ( A ) // 2 :]) n = m = k = 0 C = [ 0 ] * ( len ( L ) + len ( R )) kun taas n < len ( L ) ja m < len ( R ): jos L [ n ] <= R [ m ]: C [ k ] = L [ n ] n + = 1 muuta : C [ k ] = R [ m ] m + = 1 k + = 1 kun taas n < len ( L ): C [ k ] = L [ n ] n + = 1 k + = 1 kun m < len ( R ): C [ k ] = R [ m ] m + = 1 k + = 1 i :lle alueella ( len ( A ) ): A [ i ] = C [ i ] palauttaa A


Yhdistämisalgoritmin pseudokoodi ilman jäännöksen "liittämistä" C++- kaltaisella kielellä:

L = *In1; R = *In2; jos( L == R ) { *Out++ = L; In1++; *Out++ = R; In2++; } else if(L < R) { *Out++ = L; In1++; } muu { *Out++ = R; In2++; }

Algoritmin keksi John von Neumann vuonna 1945 [1] .

Yllä oleva algoritmi C++-kaltaisessa kielessä käyttää aliryhmien kahden verratun elementin tasa-arvon tarkistusta erillisellä käsittelylohkolla tasa-arvon tapauksessa. Erillinen tasa-arvotarkistus kaksinkertaistaa vertailujen määrän, mikä monimutkaistaa ohjelmakoodia. Erillisen tasa-arvotarkistuksen ja erillisen tasa-arvon käsittelylohkon sijasta voidaan käyttää kahta tarkistusta if(L <= R) ja if(L >= R) , mikä melkein puolittaa ohjelman koodin.

Parannetun yhdistämisalgoritmin pseudokoodi ilman "liittämistä" C++- kaltaiseen kieleen:

L = *In1; R = *In2; if( L <= R ) { *Out++ = L; In1++; } if( L >= R ) { *Out++ = R; In2++; }

Sekkien määrä voidaan puolittaa poistamalla if(L >= R) -shekki . Tässä tapauksessa, jos L ja R ovat yhtä suuret, L kirjoitetaan Out ensimmäisessä iteraatiossa ja R - toisessa. Tämä vaihtoehto toimii tehokkaasti, jos alkuperäisessä taulukossa ei ole päällekkäisiä elementtejä, jotka hallitsevat muita elementtejä.

Pseudokoodi lyhennetylle yhdistämisalgoritmille ilman "liittämistä" C++- kaltaisella kielellä:

L = *In1; R = *In2; if( L <= R ) { *Out++ = L; In1++; } muu { *Out++ = R; In2++; }

Kaksi siirtooperaatiota muuttujiin L ja R yksinkertaistavat joitain ohjelmamerkintöjä, joista voi olla hyötyä opetustarkoituksiin, mutta todellisissa ohjelmissa ne voidaan poistaa, mikä vähentää ohjelmakoodia. Voit myös käyttää kolmiosaista operaattoria , joka vähentää ohjelmakoodia entisestään.
Pseudokoodi vieläkin edistyneempään yhdistämisalgoritmiin "liittämättä" loput C++ :n kaltaisella kielellä:

*Out++ = *In1 <= *In2 ? In1++ : In2++;

Algoritmin ajoaika on O(n * log n) huonojen tapausten huonontumisen puuttuessa, mikä on arkaluonteinen pikalajittelupiste (myös algoritmi, jonka suuruus on O(n * log n), mutta vain keskimääräiselle tapaukselle ). Muistin kulutus on korkeampi kuin nopealla lajittelulla, paljon edullisemmalla muistinvarauskuviolla - yksi muistialue on mahdollista varata alusta alkaen ja olla varaamatta myöhemmin.

Suosittu toteutus vaatii kertaluonteisen varatun väliaikaisen muistipuskurin, joka on sama kuin lajiteltava taulukko, eikä siinä ole rekursioita. Käyttöönoton vaiheet:

  1. InputArray = lajiteltava matriisi, OutputArray = väliaikainen puskuri;
  2. jokaiselle syöttötaulukon segmentille InputArray[N * MIN_CHUNK_SIZE..(N + 1) * MIN_CHUNK_SIZE] suoritetaan jokin apulajittelualgoritmi, esimerkiksi Shell-lajittelu tai pikalajittelu;
  3. aseta ChunkSize = MIN_CHUNK_SIZE;
  4. yhdistä kaksi segmenttiä InputArray[N * ChunkSize..(N + 1) * ChunkSize] ja InputArray[(N + 1) * ChunkSize..(N + 2) * ChunkSize] siirtymällä vuorotellen vasemmalle ja oikealle (katso yllä), tulos sijoitetaan OutputArray[N * ChunkSize..(N + 2) * ChunkSize], ja niin edelleen kaikille N, kunnes taulukon loppu saavutetaan;
  5. ChunkSize kaksinkertaistuu;
  6. jos ChunkSizesta on tullut >= taulukon koko, niin loppu, tulos on OutputArrayssa, joka (alla kuvatuista permutaatioista johtuen) on joko lajiteltava taulukko tai väliaikainen puskuri, toisessa tapauksessa se kopioidaan kokonaan taulukkoon lajitellaan;
  7. muussa tapauksessa InputArray ja OutputArray vaihdetaan permutointiosoittimilla, ja kaikki toistetaan kohdasta 4.

Tämä toteutus tukee myös lajiteltavan taulukon ja väliaikaisen puskurin sijoittamista levytiedostoihin, mikä tekee siitä sopivan suurten tietomäärien lajitteluun. ORDER BY:n toteutus MySQL :ssä sopivan indeksin puuttuessa toimii täsmälleen näin (lähde: filesort.cc MySQL-lähdekoodissa).

Esimerkki yksinkertaisen kaksisuuntaisen yhdistämisalgoritmin toteutuksesta pseudokoodissa:

funktio mergesort(m) var lista vasen, oikea, tulos jos pituus(m) ≤ 1 palauttaa m else keski = pituus (m) / 2 jokaiselle x :lle m : ssä keskikohtaan asti lisää x vasemmalle jokaiselle x :lle metreissä keskikohdan jälkeen lisää x oikealle vasen = yhdistä (vasemmalla) oikea = yhdistä (oikea) tulos = yhdistä (vasen, oikea) palauta tulos loppu jos

Merge()-funktiosta on useita muunnelmia, yksinkertaisin voisi näyttää tältä:

funktio yhdistä(vasen,oikea) var listatulos , kun pituus(vasen) > 0 ja pituus (oikea) > 0 , jos ensimmäinen(vasen) ≤ ensimmäinen(oikea) liitä ensimmäinen (vasen) tulokseen vasen = lepo (vasen) muu liitä ensimmäinen (oikea) tulokseen oikea = lepo (oikea) end if while pituus (vasemmalla) > 0 liitä ensimmäinen (vasen) tulokseen vasen = lepo (vasen) kun taas pituus (oikealla) > 0 liitä ensimmäinen (oikea) tulokseen oikea = lepo (oikea) palauttaa tuloksen

Edut ja haitat

Edut:

  • Toimii jopa peräkkäisissä tietorakenteissa.
  • Yhdistää hyvin sivun ja muistin välimuistin kanssa.
  • Toimii hyvin rinnakkain : on helppo jakaa tehtävät prosessorien kesken tasapuolisesti, mutta on vaikea saada muita prosessoreita ottamaan haltuunsa, jos yksi prosessori viivästyy.
  • Siinä ei ole "vaikeita" tuloja.
  • Vakaa - säilyttää yhtäläisten elementtien järjestyksen (kuuluu vertailuun samaan ekvivalenssiluokkaan).

Virheet:

  • "Melkein lajiteltujen" taulukoiden kohdalla se kestää yhtä kauan kuin kaoottisissa. Yhdistämislajittelusta on olemassa muunnos, joka on nopeampi osittain lajitetulla tiedolla, mutta se vaatii lisämuistia väliaikaisen puskurin lisäksi, jota käytetään suoraan lajitteluun.
  • Vaatii lisämuistia alkuperäisen taulukon kokoon nähden.

Muistiinpanot

  1. ↑ Knuth, D.E. Tietokoneohjelmoinnin taito. Osa 3 : Lajittelu ja haku  . – 2. - Addison-Wesley , 1998. - S. 159. - ISBN 0-201-89685-0 .

Kirjallisuus

  • Levitin A. V. Luku 4. Hajotusmenetelmä: Yhdistä lajittelu // Algoritmit. Johdatus kehittämiseen ja analyysiin - M . : Williams , 2006. - S. 169-172. — 576 s. — ISBN 978-5-8459-0987-9
  • Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmit: rakentaminen ja analyysi = Introduction to Algorithms / Ed. I. V. Krasikova. - 2. painos - M .: Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .

Linkit

 Lajittelualgoritmit
Teoria Monimutkaisuus O merkintä Tilaussuhde Lajittele tyypit kestävää Sisäinen Ulkoinen
Vaihto
Valinta
insertit
fuusio
Ei vertailuja
hybridi
muu
epäkäytännöllistä