Flet sortering

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 6. oktober 2018; kontroller kræver 47 redigeringer .
Flet sortering

Eksempel på flet sortering. Først opdeler vi listen i stykker (1 element hver), derefter sammenligner vi hvert element med dets nabo, sorterer og flettes. Som et resultat sorteres og kombineres alle elementer.
Forfatter John von Neumann
formål Sorteringsalgoritme
Datastruktur liste , matrix
værste tid
Bedste tid
Gennemsnitlig tid
Hukommelsesomkostninger for liste, for array
 Mediefiler på Wikimedia Commons

Merge sort er en  sorteringsalgoritme , der arrangerer lister (eller andre datastrukturer, hvis elementer kun kan tilgås sekventielt , for eksempel streams ) i en bestemt rækkefølge. Denne sortering er et godt eksempel på brug af opdel og hersk princippet . Først er opgaven opdelt i flere mindre delopgaver. Disse opgaver løses så med et rekursivt kald eller direkte, hvis deres størrelse er lille nok. Til sidst kombineres deres løsninger , og der opnås en løsning på det oprindelige problem.

Detaljeret sorteringsalgoritme

For at løse sorteringsproblemet ser disse tre trin således ud:

  1. Arrayet , der skal sorteres , opdeles i to dele af omtrent samme størrelse;
  2. Hver af de resulterende dele sorteres separat, for eksempel efter den samme algoritme;
  3. To halvstore ordnede arrays slås sammen til én.

1.1. - 2.1. Rekursiv opdeling af opgaven i mindre opstår, indtil størrelsen af ​​arrayet når en (enhver array af længde 1 kan betragtes som ordnet).

3.1. Kombinere to ordnede arrays til én.
Den grundlæggende idé med at flette to sorterede arrays kan forklares med følgende eksempel. Antag, at vi allerede har to subarrays sorteret i stigende rækkefølge. Derefter:
3.2. Sammenlægning af to underarrays til et tredje resulterende array.
Ved hvert trin tager vi det mindste af de to første elementer i underarrayerne og skriver det til det resulterende array. Tællerne for antallet af elementer i det resulterende array og subarrayet, hvorfra elementet blev taget, øges med 1.
3.3. "Vedhæftning" af resten.
Når et af underarrays er forbi, tilføjer vi alle de resterende elementer i det andet underarray til det resulterende array.

Sorteringseksempel i C

/** * Sorterer array ved hjælp af rekursiv flet sortering * op - pegepind til array, der skal sorteres * ned - peger til array med mindst samme størrelse som 'op', bruges som buffer * venstre-venstre kant af array , pass 0 til sorter arrayet fra begyndelsen * højre - højre kant af arrayet, passér længden af ​​arrayet - 1 for at sortere arrayet til det sidste element * returnerer: en pointer til det sorterede array. På grund af hvordan denne implementering fungerer * kan den sorterede version af arrayet ende enten i 'op' eller 'ned' **/ int * merge_sort ( int * op , int * ned , usigneret int venstre , usigneret int højre ) { hvis ( venstre == højre ) { ned [ venstre ] = op [ venstre ]; vende tilbage ned ; } unsigned int middle = left + ( højre - venstre ) / 2 ; // del og sorter int * l_buff = merge_sort ( op , ned , venstre , midt ); int * r_buff = merge_sort ( op , ned , midt + 1 , højre ); // flette to sorterede halvdele int * target = l_buff == op ? ned : op ; usigneret int l_cur = venstre , r_cur = midt + 1 ; for ( usigneret int i = venstre ; i <= højre ; i ++ ) { if ( l_cur <= midt && r_cur <= højre ) { if ( l_buff [ l_cur ] < r_buff [ r_cur ]) { mål [ i ] = l_buff [ l_cur ]; l_cur ++ ; } andet { target [ i ] = r_buff [ r_cur ]; r_cur ++ ; } } else if ( l_cur <= middle ) { mål [ i ] = l_buff [ l_cur ]; l_cur ++ ; } andet { target [ i ] = r_buff [ r_cur ]; r_cur ++ ; } } returmål ; _ }

Implementering i C++11 :

#include <algoritme> #include <cstddef> #inkluder <iterator> #inkluder <hukommelse> skabelon < typenameT > _ void merge_sort ( T array [], std :: size_t size ) noexcept { hvis ( størrelse > 1 ) { std :: size_t const left_size = størrelse / 2 ; std :: størrelse_t const højre_størrelse = størrelse - venstre_størrelse ; merge_sort ( & array [ 0 ], left_size ); merge_sort ( & array [ venstre_størrelse ], højre_størrelse ); std :: størrelse_t lidx = 0 , ridx = venstre_størrelse , idx = 0 ; std :: unik_ptr < T [] > tmp_array ( ny T [ størrelse ]); while ( lidx < left_size || ridx < size ) { if ( array [ lidx ] < array [ ridx ]) { tmp_array [ idx ++ ] = std :: move ( array [ lidx ]); lidx ++ ; } andet { tmp_array [ idx ++ ] = std :: move ( array [ ridx ]); ridx ++ ; } if ( lidx == venstre_størrelse ) { std :: copy ( std :: make_move_iterator ( & array [ ridx ]), std :: make_move_iterator ( & array [ størrelse ]), & tmp_array [ idx ]); bryde ; } if ( ridx == størrelse ) { std :: copy ( std :: make_move_iterator ( & array [ lidx ]), std :: make_move_iterator ( & array [ left_size ]), & tmp_array [ idx ]); bryde ; } } std :: copy ( std :: make_move_iterator ( tmp_array ), std :: make_move_iterator ( & tmp_array [ størrelse ]), array ); } }

Implementering i C++14 med OpenMP parallelisering

#include <algoritme> #inkluder <iterator> #include <omp.h> #inkluder <hukommelse> skabelon < typenameIterator > _ void mergesort ( Iterator fra , Iterator til ) { #pragma omp parallel { #pragma omp single nowait static_assert ( ! std :: er_samme < typenavn std :: iterator_træk < Iterator >:: værditype , ugyldig >:: værdi ); auto n = std :: distance ( fra , til ); hvis ( 1 < n ) { #pragma omp opgave førstprivat (fra, til, n) { Iterator l_fra = fra ; Iterator l_to = l_fra ; std :: advance ( l_to , n / 2 ); mergesort ( l_fra , l_til ); } #pragma omp opgave førstprivat (fra, til, n) { Iterator r_from = fra ; std :: advance ( r_fra , n / 2 ); Iterator r_to = r_fra ; std :: advance ( r_to , n - ( n / 2 )); mergesort ( r_fra , r_til ); } #pragma omp taskwait auto tmp_array = std :: make_unique < typename Iterator :: værditype [] > ( n ); Iterator l_iter = fra ; Iterator l_end = l_iter ; std :: advance ( l_end , n / 2 ); Iterator r_iter = l_end ; Iterator & r_end = til ; auto tmp_iter = tmp_array . få (); mens ( l_iter != l_end || r_iter != r_end ) { if ( * l_iter < * r_iter ) { * tmp_iter = std :: move ( * l_iter ); ++ l_iter ; ++ tmp_iter ; } andet { * tmp_iter = std :: move ( * r_iter ); ++ r_iter ; ++ tmp_iter ; } if ( l_iter == l_end ) { std :: kopi ( std :: make_move_iterator ( r_iter ), std :: make_move_iterator ( r_end ), tmp_iter ); bryde ; } if ( r_iter == r_end ) { std :: kopi ( std :: make_move_iterator ( l_iter ), std :: make_move_iterator ( l_end ), tmp_iter ); bryde ; } } std :: kopi ( std :: make_move_iterator ( tmp_array.get ( ) ), std :: make_move_iterator ( & tmp_array [ n ]), fra ); } } }

Iterativ implementering i C++ :

skabelon < typenameT > _ 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 ; for ( BlockSizeIterator = 1 ; BlockSizeIterator < l ; BlockSizeIterator *= 2 ) { for ( BlockIterator = 0 ; BlockIterator < l - BlockSizeIterator ; BlockIterator += 2 * BlockSizeIterator ) { //Vi fusionerer med sortering af et par blokke startende fra BlockIterator-elementet //den venstre med størrelsen BlockSizeIterator, den højre med størrelsen 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 ]; //Mens begge arrays har elementer, vælg den mindste og læg den i den sorterede blok, mens ( LeftBorder + LeftBlockIterator < MidBorder && MidBorder + RightBlockIterator < RightBorder ) { if ( a [ LeftBorder + LeftBlockIterator ] < a [ MidBorder + RightBlockIterator ]) { SortedBlock [ LeftBlockIterator + RightBlockIterator ] = en [ LeftBorder + LeftBlockIterator ]; LeftBlockIterator += 1 ; } andet { SortedBlock [ LeftBlockIterator + RightBlockIterator ] = en [ MidBorder + RightBlockIterator ]; RightBlockIterator += 1 ; } } //Derefter henter vi de resterende elementer fra venstre eller højre blok, mens ( LeftBorder + LeftBlockIterator < MidBorder ) { SortedBlock [ LeftBlockIterator + RightBlockIterator ] = en [ LeftBorder + LeftBlockIterator ]; LeftBlockIterator += 1 ; } while ( MidBorder + RightBlockIterator < RightBorder ) { SortedBlock [ LeftBlockIterator + RightBlockIterator ] = en [ MidBorder + RightBlockIterator ]; RightBlockIterator += 1 ; } for ( MergeIterator = 0 ; MergeIterator < LeftBlockIterator + RightBlockIterator ; MergeIterator ++ ) { a [ LeftBorder + MergeIterator ] = SortedBlock [ MergeIterator ]; } slet SortedBlock ; } } }


Implementering i Python :

def merge_sort ( A ): hvis len ( A ) == 1 eller len ( A ) == 0 : retur 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 )) mens n < len ( L ) og m < len ( R ): hvis L [ n ] <= R [ m ]: C [ k ] = L [ n ] n += 1 andet : C [ k ] = R [ m ] m += 1 k += 1 mens n < len ( L ): C [ k ] = L [ n ] n += 1 k += 1 mens m < len ( R ): C [ k ] = R [ m ] m += 1 k += 1 for i inden for rækkevidde ( len ( A )): A [ i ] = C [ i ] retur A


Pseudokode for flettealgoritmen uden "vedhæftning" af resten i et C++- lignende sprog:

L = *Inl; R = *In2; if( L == R ) { *Ud++ = L; In1++; *Ud++ = R; In2++; } andet if(L < R) { *Ud++ = L; In1++; } andet { *Ud++ = R; In2++; }

Algoritmen blev opfundet af John von Neumann i 1945 [1] .

Ovenstående algoritme i et C++-lignende sprog bruger en kontrol for lighed af to sammenlignede elementer af subarrays med en separat behandlingsblok i tilfælde af lighed. En separat lighedskontrol fordobler antallet af sammenligninger, hvilket komplicerer programkoden. I stedet for en separat lighedskontrol og en separat lighedsbehandlingsblok, kan du bruge to kontroller if(L <= R) og if(L >= R) , hvilket næsten halverer programmets kode.

Pseudo-kode for en forbedret flettealgoritme uden at "vedhæfte" resten i et C++- lignende sprog:

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

Antallet af checks kan halveres ved at fjerne if(L >= R) markeringen . I dette tilfælde, hvis L og R er ens, vil L blive skrevet til Ud i den første iteration, og R - i den anden. Denne mulighed vil fungere effektivt, hvis det originale array ikke har duplikerede elementer, der dominerer over resten af ​​elementerne.

Pseudokode for en forkortet flettealgoritme uden at "vedhæfte" resten i et C++- lignende sprog:

L = *Inl; R = *In2; if( L <= R ) { *Ud++ = L; In1++; } andet { *Ud++ = R; In2++; }

De to overførselsoperationer til variablerne L og R forenkler nogle af programindtastningerne, hvilket kan være nyttigt til undervisningsformål, men i rigtige programmer kan de fjernes, hvilket vil reducere programkoden. Du kan også bruge den ternære operator , som vil reducere programkoden yderligere.
Pseudokode for en endnu mere avanceret flettealgoritme uden at "vedhæfte" resten i et C++- lignende sprog:

*Ud++ = *Ind1 <= *Ind2 ? In1++: In2++;

Algoritmens køretid er O(n * log n) i fravær af nedbrydning på dårlige tilfælde, hvilket er et ømt punkt for quicksort (også en algoritme af orden O(n * log n), men kun for det gennemsnitlige tilfælde ). Hukommelsesforbruget er højere end for hurtig sortering, med et meget mere gunstigt hukommelsestildelingsmønster - det er muligt at allokere én region af hukommelsen helt fra begyndelsen og ikke at allokere senere.

En populær implementering kræver en engangsallokeret midlertidig hukommelsesbuffer svarende til det array, der sorteres, og har ingen rekursioner. Implementeringstrin:

  1. InputArray = sorterbar array, OutputArray = midlertidig buffer;
  2. over hvert segment af input-arrayet InputArray[N * MIN_CHUNK_SIZE..(N + 1) * MIN_CHUNK_SIZE] udføres en eller anden hjælpesorteringsalgoritme, for eksempel Shell-sortering eller hurtig sortering;
  3. sæt ChunkSize = MIN_CHUNK_SIZE;
  4. flet to segmenter InputArray[N * ChunkSize..(N + 1) * ChunkSize] og InputArray[(N + 1) * ChunkSize..(N + 2) * ChunkSize] ved skiftevis at træde til venstre og højre (se ovenfor), resultat er placeret i OutputArray[N * ChunkSize..(N + 2) * ChunkSize], og så videre for alle N indtil slutningen af ​​arrayet er nået;
  5. ChunkSize er fordoblet;
  6. hvis ChunkSize er blevet >= array-størrelse, så end, er resultatet i OutputArray, som (på grund af de permutationer, der er beskrevet nedenfor) enten er et array, der skal sorteres eller en midlertidig buffer, i det andet tilfælde kopieres det helt til arrayet skal sorteres;
  7. ellers byttes InputArray og OutputArray af permuterende pointere, og alt gentages fra punkt 4.

Denne implementering understøtter også placering af arrayet, der skal sorteres, og den midlertidige buffer i diskfiler, hvilket gør den velegnet til at sortere enorme mængder data. Implementeringen af ​​ORDER BY i MySQL i mangel af et passende indeks fungerer præcis sådan (kilde: filesort.cc i MySQL-kildekoden).

Et eksempel på implementering af en simpel to-vejs flettealgoritme i pseudokode:

funktion mergesort(m) var liste venstre, højre, resultat hvis længde(m) ≤ 1 returner m andet midt = længde(m) / 2 for hvert x i m op til midten tilføje x til venstre for hvert x i m efter midten tilføje x til højre venstre = mergesort(venstre) højre = mergesort(højre) resultat = flet (venstre, højre) returnere resultat ende hvis

Der er flere varianter af merge()-funktionen, den enkleste kan se sådan ud:

funktion flet (venstre, højre) var listeresultat , mens længde (venstre) > 0 og længde (højre) > 0, hvis først (venstre) ≤ første (højre) føje først (venstre) til resultatet venstre = hvile (venstre) andet føje først (højre) til resultatet højre = hvile (højre) ende hvis mens længde (venstre) > 0 føje først (venstre) til resultatet venstre = hvile (venstre) mens længde (højre) > 0 føje først (højre) til resultatet højre = hvile (højre) returnere resultat

Fordele og ulemper

Fordele:

  • Fungerer selv på datastrukturer med sekventiel adgang.
  • Kombinerer godt med personsøgning og hukommelsescache .
  • Fungerer godt parallelt : det er nemt at dele opgaver ligeligt mellem processorer, men det er svært at få andre processorer til at tage over, hvis en processor er forsinket.
  • Har ingen "svære" input.
  • Stabil - bevarer rækkefølgen af ​​lige elementer (tilhører den samme ækvivalensklasse ved sammenligning).

Fejl:

  • På "næsten sorterede" arrays tager det lige så lang tid som på kaotiske. Der er en variant af flettesortering, der er hurtigere på delvist sorterede data, men det kræver ekstra hukommelse ud over den midlertidige buffer, der bruges direkte til sortering.
  • Kræver yderligere hukommelse til størrelsen af ​​det originale array.

Noter

  1. ↑ Knuth, D.E. The Art of Computer Programming. Bind 3 : Sortering og søgning  . — 2. - Addison-Wesley , 1998. - S. 159. - ISBN 0-201-89685-0 .

Litteratur

  • Levitin A. V. Kapitel 4. Dekomponeringsmetode: Merge sort // Algoritmer. Introduktion til udvikling og analyse - M . : Williams , 2006. - S. 169-172. — 576 s. — ISBN 978-5-8459-0987-9
  • Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmer: konstruktion og analyse = Introduktion til algoritmer / Ed. I. V. Krasikova. - 2. udg. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .

Links

 Sorteringsalgoritmer
Teori Kompleksitet O notation Ordreforhold Sorter typer bæredygtige Indre Ekstern
Udveksling
Valg
indsætter
fusion
Ingen sammenligninger
hybrid
Andet
upraktisk