Slå samman sortering

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 6 oktober 2018; kontroller kräver 47 redigeringar .
Slå samman sortering

Exempel på sammanfogning. Först delar vi upp listan i bitar (1 element vardera), sedan jämför vi varje element med dess granne, sorterar och slår samman. Som ett resultat sorteras och kombineras alla element.
Författare John von Neumann
ändamål Sorteringsalgoritm
Datastruktur lista , array
värsta tiden
Lämpligast tid
Snittid
Minneskostnad för lista, för array
 Mediafiler på Wikimedia Commons

Merge sort är en  sorteringsalgoritm som ordnar listor (eller andra datastrukturer vars element endast kan nås sekventiellt , till exempel strömmar ) i en viss ordning. Denna sortering är ett bra exempel på att använda dela och härska principen . Först är uppgiften uppdelad i flera mindre deluppgifter. Dessa uppgifter löses sedan med ett rekursivt anrop eller direkt om deras storlek är tillräckligt liten. Slutligen kombineras deras lösningar och en lösning på det ursprungliga problemet erhålls.

Detaljerad sorteringsalgoritm

För att lösa sorteringsproblemet ser dessa tre steg ut så här:

  1. Arrayen som ska sorteras delas upp i två delar av ungefär samma storlek;
  2. Var och en av de resulterande delarna sorteras separat, till exempel med samma algoritm;
  3. Två halvstora ordnade arrayer slås samman till en.

1.1. — 2.1. Rekursiv partitionering av uppgiften i mindre sker tills storleken på arrayen når en (vilken array som helst med längd 1 kan anses vara ordnad).

3.1. Kombinera två ordnade arrayer till en.
Grundidén med att slå samman två sorterade arrayer kan förklaras med följande exempel. Anta att vi redan har två subarrayer sorterade i stigande ordning. Sedan:
3.2. Sammanfogar två subarrayer till en tredje resulterande array.
Vid varje steg tar vi det minsta av de två första elementen i subarrayerna och skriver det till den resulterande arrayen. Räknarna för antalet element i den resulterande arrayen och subarrayen från vilken elementet togs ökas med 1.
3.3. "Bilaga" av resten.
När en av subarrayerna är över lägger vi till alla återstående element i den andra subarrayen till den resulterande arrayen.

Sorteringsexempel i C

/** * Sorterar array med rekursiv sammanfogning sortering * upp - pekare till array som ska sorteras * ner - pekare till array med minst samma storlek som 'upp', används som buffert * vänster-vänster kant av array , skicka 0 till sortera arrayen från början * höger - höger kant av arrayen, passera längden på arrayen - 1 för att sortera arrayen till det sista elementet * returnerar: en pekare till den sorterade arrayen. På grund av hur denna implementering fungerar * kan den sorterade versionen av arrayen hamna antingen i 'upp' eller 'ner' **/ int * merge_sort ( int * upp , int * ner , osignerad int vänster , osignerad int höger ) { om ( vänster == höger ) { ner [ vänster ] = upp [ vänster ]; återvända ner ; } unsigned int middle = left + ( höger - vänster ) / 2 ; // split and sort int * l_buff = merge_sort ( upp , ner , vänster , mitten ); int * r_buff = merge_sort ( upp , ner , mitten + 1 , höger ); // slå samman två sorterade halvor int * target = l_buff == upp ? ner : upp ; unsigned int l_cur = vänster , r_cur = mitten + 1 ; för ( osignerad int i = vänster ; i <= höger ; i ++ ) { if ( l_cur <= mitten && r_cur <= höger ) { if ( l_buff [ l_cur ] < r_buff [ r_cur ]) { mål [ i ] = l_buff [ l_cur ]; l_cur ++ ; } annan { mål [ i ] = r_buff [ r_cur ]; r_cur ++ ; } } annat om ( l_cur <= mitten ) { mål [ i ] = l_buff [ l_cur ]; l_cur ++ ; } annan { mål [ i ] = r_buff [ r_cur ]; r_cur ++ ; } } returmål ; _ }

Implementering i C++11 :

#inkludera <algoritm> #include <cstddef> #inkludera <iterator> #inkludera <minne> mall < typnamnT > _ void merge_sort ( T array [], std :: size_t size ) noexcept { if ( storlek > 1 ) { std :: size_t const left_size = storlek / 2 ; std :: size_t const right_size = storlek - left_size ; merge_sort ( & array [ 0 ], left_size ); merge_sort ( & array [ left_size ], right_size ); std :: size_t lidx = 0 , ridx = left_size , idx = 0 ; std :: unik_ptr < T [] > tmp_array ( ny T [ storlek ]); while ( lidx < left_size || ridx < size ) { if ( array [ lidx ] < array [ ridx ]) { tmp_array [ idx ++ ] = std :: flytta ( array [ lidx ]); lidx ++ ; } annan { tmp_array [ idx ++ ] = std :: flytta ( array [ ridx ]); ridx ++ ; } if ( lidx == left_size ) { std :: copy ( std :: make_move_iterator ( & array [ ridx ]), std :: make_move_iterator ( & array [ storlek ]), & tmp_array [ idx ]); bryta ; } if ( ridx == storlek ) { std :: copy ( std :: make_move_iterator ( & array [ lidx ]), std :: make_move_iterator ( & array [ left_size ]), & tmp_array [ idx ]); bryta ; } } std :: copy ( std :: make_move_iterator ( tmp_array ), std :: make_move_iterator ( & tmp_array [ storlek ]), array ); } }

Implementering i C++14 med OpenMP- parallellisering

#inkludera <algoritm> #inkludera <iterator> #include <omp.h> #inkludera <minne> mall < typnamnIterator > _ void mergesort ( Iterator från , Iterator till ) { #pragma omp parallell { #pragma omp singel nu static_assert ( ! std :: is_same < typname std :: iterator_traits < Iterator >:: value_type , void >:: value ); auto n = std :: avstånd ( från , till ); om ( 1 < n ) { #pragma omp uppgift förstprivat (från, till, n) { Iterator l_from = från ; Iterator l_to = l_från ; std :: advance ( l_to , n / 2 ); mergesort ( l_från , l_till ); } #pragma omp uppgift förstprivat (från, till, n) { Iterator r_from = från ; std :: advance ( r_from , n / 2 ); Iterator r_to = r_from ; std :: avancera ( r_to , n - ( n / 2 )); mergesort ( r_från , r_till ); } #pragma omp taskwait auto tmp_array = std :: make_unique < typnamn Iterator :: värde_typ [] > ( n ); Iterator l_iter = från ; Iterator l_end = l_iter ; std :: advance ( l_end , n / 2 ); Iterator r_iter = l_end ; Iterator & r_end = till ; auto tmp_iter = tmp_array . få (); while ( l_iter != l_end || r_iter != r_end ) { if ( * l_iter < * r_iter ) { * tmp_iter = std :: flytta ( * l_iter ); ++ l_iter ; ++ tmp_iter ; } annan { * tmp_iter = std :: flytta ( * r_iter ); ++ r_iter ; ++ tmp_iter ; } if ( l_iter == l_end ) { std :: kopia ( std :: make_move_iterator ( r_iter ), std :: make_move_iterator ( r_end ), tmp_iter ); bryta ; } if ( r_iter == r_end ) { std :: kopia ( std :: make_move_iterator ( l_iter ), std :: make_move_iterator ( l_end ), tmp_iter ); bryta ; } } std :: kopia ( std :: make_move_iterator ( tmp_array.get ( ) ), std :: make_move_iterator ( & tmp_array [ n ]), från ); } } }

Iterativ implementering i C++ :

mall < typnamnT > _ void MergeSort ( T a [], size_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 ; för ( BlockSizeIterator = 1 ; BlockSizeIterator < l ; BlockSizeIterator *= 2 ) { för ( BlockIterator = 0 ; BlockIterator < l - BlockSizeIterator ; BlockIterator += 2 * BlockSizeIterator ) { //Vi slår samman med att sortera ett par block med början från BlockIterator-elementet //det vänstra med storleken BlockSizeIterator, det högra med storleken BlockSizeIterator eller mindre LeftBlockIterator = 0 ; RightBlockIterator = 0 ; LeftBorder = BlockIterator ; MidBorder = BlockIterator + BlockSizeIterator ; RightBorder = BlockIterator + 2 * BlockSizeIterator ; RightBorder = ( RightBorder < l ) ? RightBorder : l ; int * SortedBlock = new int [ RightBorder - LeftBorder ]; //Medan båda arrayerna har element, välj den mindre och placera den i det sorterade blocket medan ( LeftBorder + LeftBlockIterator < MidBorder && MidBorder + RightBlockIterator < RightBorder ) { if ( a [ LeftBorder + LeftBlockIterator ] < a [ MidBorder + RightBlockIterator ]) { SortedBlock [ LeftBlockIterator + RightBlockIterator ] = a [ LeftBorder + LeftBlockIterator ]; LeftBlockIterator += 1 ; } annan { SortedBlock [ LeftBlockIterator + RightBlockIterator ] = a [ MidBorder + RightBlockIterator ]; RightBlockIterator += 1 ; } } //Efter det tar vi in ​​de återstående elementen från vänster eller höger block medan ( LeftBorder + LeftBlockIterator < MidBorder ) { SortedBlock [ LeftBlockIterator + RightBlockIterator ] = a [ LeftBorder + LeftBlockIterator ]; LeftBlockIterator += 1 ; } while ( MidBorder + RightBlockIterator < RightBorder ) { SortedBlock [ LeftBlockIterator + RightBlockIterator ] = a [ MidBorder + RightBlockIterator ]; RightBlockIterator += 1 ; } för ( MergeIterator = 0 ; MergeIterator < LeftBlockIterator + RightBlockIterator ; MergeIterator ++ ) { a [ LeftBorder + MergeIterator ] = SortedBlock [ MergeIterator ]; } ta bort SortedBlock ; } } }


Implementering i Python :

def merge_sort ( A ): om len ( A ) == 1 eller len ( A ) == 0 : tillbaka A L = merge_sort ( A [: len ( A ) // 2 ]) R = merge_sort ( A [ len ( A ) // 2 :]) n = m = k = 0 C = [ 0 ] * ( len ( L ) + len ( R )) medan n < len ( L ) och m < len ( R ): om L [ n ] <= R [ m ]: C [ k ] = L [ n ] n += 1 annat : C [ k ] = R [ m ] m += 1 k += 1 medan n < len ( L ): C [ k ] = L [ n ] n += 1 k += 1 medan m < len ( R ): C [ k ] = R [ m ] m += 1 k += 1 för i inom intervallet ( len ( A )): A [ i ] = C [ i ] tillbaka A


Pseudokod för sammanslagningsalgoritmen utan "bifogning" av resten i ett C++- liknande språk:

L = *Inl; R = *In2; if( L == R ) { *Ut++ = L; In1++; *Ut++ = R; In2++; } annat om(L < R) { *Ut++ = L; In1++; } annat { *Ut++ = R; In2++; }

Algoritmen uppfanns av John von Neumann 1945 [1] .

Ovanstående algoritm i ett C++-liknande språk använder en kontroll för likhet av två jämförda element av subarrayer med ett separat bearbetningsblock i händelse av likhet. En separat jämställdhetskontroll fördubblar antalet jämförelser, vilket komplicerar programkoden. Istället för en separat likhetskontroll och ett separat likhetsbearbetningsblock kan du använda två kontroller if(L <= R) och if(L >= R) , vilket nästan halverar programmets kod.

Pseudokod för en förbättrad sammanslagningsalgoritm utan att "bifoga" resten i ett C++- liknande språk:

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

Antalet kontroller kan halveras genom att ta bort krysset if(L >= R) . I det här fallet, om L och R är lika, kommer L att skrivas till Out i den första iterationen och R - i den andra. Detta alternativ kommer att fungera effektivt om den ursprungliga arrayen inte har dubbletter av element som dominerar över resten av elementen.

Pseudokod för en förkortad sammanslagningsalgoritm utan att "bifoga" resten på ett C++- liknande språk:

L = *Inl; R = *In2; if( L <= R ) { *Ut++ = L; In1++; } annat { *Ut++ = R; In2++; }

De två överföringsoperationerna till variablerna L och R förenklar en del av programposterna, vilket kan vara användbart för undervisningsändamål, men i riktiga program kan de tas bort, vilket kommer att minska programkoden. Du kan också använda den ternära operatorn , vilket kommer att reducera programkoden ytterligare.
Pseudokod för en ännu mer avancerad sammanslagningsalgoritm utan att "bifoga" resten på ett C++- liknande språk:

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

Körtiden för algoritmen är O(n * log n) i frånvaro av försämring på dåliga fall, vilket är en öm punkt för quicksort (också en algoritm av ordningen O(n * log n), men bara för genomsnittsfallet ). Minnesförbrukningen är högre än för snabb sortering, med ett mycket gynnsammare minnesallokeringsmönster - det är möjligt att allokera en minnesregion redan från början och inte att allokera senare.

En populär implementering kräver en engångstilldelad temporär minnesbuffert lika med den array som sorteras och har inga rekursioner. Implementeringssteg:

  1. InputArray = sorterbar array, OutputArray = temporär buffert;
  2. över varje segment av inmatningsmatrisen InputArray[N * MIN_CHUNK_SIZE..(N + 1) * MIN_CHUNK_SIZE] utförs någon extra sorteringsalgoritm, till exempel skalsortering eller snabbsortering;
  3. ställ in ChunkSize = MIN_CHUNK_SIZE;
  4. slå samman två segment InputArray[N * ChunkSize..(N + 1) * ChunkSize] och InputArray[(N + 1) * ChunkSize..(N + 2) * ChunkSize] genom att omväxlande stega åt vänster och höger (se ovan), resultatet placeras i OutputArray[N * ChunkSize..(N + 2) * ChunkSize], och så vidare för alla N tills slutet av arrayen nås;
  5. ChunkSize fördubblas;
  6. om ChunkSize har blivit >= arraystorlek, sedan slut, resultatet är i OutputArray, som (på grund av de permutationer som beskrivs nedan) är antingen en array som ska sorteras eller en temporär buffert, i det andra fallet kopieras den helt till arrayen att sorteras;
  7. annars byts InputArray och OutputArray av permuteringspekare och allt upprepas från punkt 4.

Denna implementering stöder även placering av arrayen som ska sorteras och den temporära bufferten i diskfiler, vilket gör den lämplig för att sortera stora mängder data. Implementeringen av ORDER BY i MySQL i avsaknad av ett lämpligt index fungerar exakt så här (källa: filesort.cc i MySQL-källkoden).

Ett exempel på implementeringen av en enkel tvåvägs sammanslagningsalgoritm i pseudokod:

funktion mergesort(m) var lista vänster, höger, resultat om längd(m) ≤ 1 returnera m annat mitten = längd(m) / 2 för varje x i m upp till mitten lägg till x till vänster för varje x i m efter mitten lägg till x till höger vänster = mergesort(vänster) höger = mergesort(höger) resultat = sammanfoga (vänster, höger) returnera resultat slut om

Det finns flera varianter av merge()-funktionen, den enklaste kan se ut så här:

funktion sammanfoga(vänster,höger) var listresultat medan längd(vänster) > 0 och längd (höger) > 0 om först(vänster) ≤ först(höger) lägg först (vänster) till resultatet vänster = vila (vänster) annan lägg först (höger) till resultatet höger = vila (höger) avsluta om medan längd (vänster) > 0 lägg först (vänster) till resultatet vänster = vila (vänster) medan längd (höger) > 0 lägg först (höger) till resultatet höger = vila (höger) returnera resultatet

Fördelar och nackdelar

Fördelar:

  • Fungerar även på sekventiell åtkomstdatastrukturer.
  • Kombinerar bra med personsökning och minnescache .
  • Fungerar bra parallellt : det är lätt att dela uppgifter lika mellan processorer, men det är svårt att få andra processorer att ta över om en processor är sen.
  • Har inga "svåra" ingångar.
  • Stabil - bevarar ordningen av lika element (tillhör samma ekvivalensklass i jämförelse).

Brister:

  • På "nästan sorterade" arrayer tar det lika lång tid som på kaotiska. Det finns en variant av merge sort som är snabbare på delvis sorterad data, men den kräver ytterligare minne utöver den tillfälliga bufferten som används direkt för sortering.
  • Kräver extra minne för storleken på originalmatrisen.

Anteckningar

  1. ↑ Knuth, D.E. Konsten att programmera. Volym 3 : Sortering och sökning  . — 2:a. - Addison-Wesley , 1998. - P. 159. - ISBN 0-201-89685-0 .

Litteratur

  • Levitin A. V. Kapitel 4. Nedbrytningsmetod: Slå samman sortering // Algoritmer. Introduktion till utveckling och analys - M . : Williams , 2006. - S. 169-172. — 576 sid. — ISBN 978-5-8459-0987-9
  • Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmer: konstruktion och analys = Introduktion till algoritmer / Ed. I. V. Krasikova. - 2:a uppl. - M. : Williams, 2005. - 1296 sid. — ISBN 5-8459-0857-4 .

Länkar

 Sorteringsalgoritmer
Teori Komplexitet O notation Orderförhållande Sorteringstyper hållbar Inre Extern
Utbyta
Val
Insatser
fusion
Inga jämförelser
hybrid
Övrig
opraktisk