Sortare îmbinare

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 6 octombrie 2018; controalele necesită 47 de modificări .
Sortare îmbinare

Exemplu de sortare fuzionare. Mai întâi, împărțim lista în bucăți (1 element fiecare), apoi comparăm fiecare element cu vecinul său, sortăm și îmbinam. Ca rezultat, toate elementele sunt sortate și combinate împreună.
Autor John von Neumann
scop Algoritm de sortare
Structură de date listă , matrice
cel mai rău moment
Cel mai bun timp
Timp mediu
Costul memoriei pentru listă, pentru matrice
 Fișiere media la Wikimedia Commons

Merge sort este un  algoritm de sortare care aranjează liste (sau alte structuri de date ale căror elemente pot fi accesate numai secvenţial , de exemplu, fluxuri ) într-o anumită ordine. Această sortare este un bun exemplu de utilizare a principiului împărțiți și cuceriți . În primul rând, sarcina este împărțită în mai multe subsarcini mai mici. Aceste sarcini sunt apoi rezolvate cu un apel recursiv sau direct dacă dimensiunea lor este suficient de mică. În cele din urmă, soluțiile lor sunt combinate și se obține o soluție la problema inițială.

Algoritm de sortare detaliat

Pentru a rezolva problema de sortare, acești trei pași arată astfel:

  1. Matricea de sortat este împărțită în două părți de aproximativ aceeași dimensiune;
  2. Fiecare dintre părțile rezultate este sortată separat, de exemplu, după același algoritm;
  3. Două matrice ordonate de jumătate de dimensiune sunt îmbinate într-una singură.

1.1. — 2.1. Partiționarea recursive a sarcinii în altele mai mici are loc până când dimensiunea matricei ajunge la unu (orice matrice cu lungimea 1 poate fi considerată ordonată).

3.1. Combinând două matrice ordonate într-una singură.
Ideea de bază a îmbinării a două matrice sortate poate fi explicată cu următorul exemplu. Să presupunem că avem două sub-tare deja sortate în ordine crescătoare. Apoi:
3.2. Fuzionarea a două sub-matrice într-o a treia matrice rezultată.
La fiecare pas, luăm cel mai mic dintre primele două elemente ale sub-tarilor și îl scriem în tabloul rezultat. Numătoarele numerelor de elemente ale tabloului rezultat și ale subgrupului din care a fost luat elementul sunt mărite cu 1.
3.3. „Atașarea” restului.
Când unul dintre subgrupuri se termină, adăugăm toate elementele rămase ale celui de-al doilea subbary la matricea rezultată.

Exemplu de sortare în C

/** * Sortează matricea utilizând sortarea de îmbinare recursivă * în sus - indicator la matrice de sortat * în jos - indicator la matrice cu cel puțin aceeași dimensiune ca „sus”, folosit ca buffer * marginea stângă - stânga a matricei, treceți 0 la sortați matricea de la început * dreapta - marginea dreaptă a matricei, treceți lungimea matricei - 1 pentru a sorta matricea la ultimul element * returnează: un pointer către matricea sortată. Datorită modului în care funcționează această implementare * versiunea sortată a matricei poate ajunge fie în „sus” fie în „jos” **/ int * merge_sort ( int * sus , int * jos , unsigned int stânga , unsigned int dreapta ) { daca ( stânga == dreapta ) { jos [ stânga ] = sus [ stânga ]; întoarcere în jos ; } unsigned int middle = stânga + ( dreapta - stânga ) / 2 ; // split and sort int * l_buff = merge_sort ( sus , jos , stânga , mijloc ); int * r_buff = merge_sort ( sus , jos , mijloc + 1 , dreapta ); // îmbina două jumătăți sortate int * target = l_buff == up ? jos : sus ; unsigned int l_cur = stânga , r_cur = mijloc + 1 ; pentru ( unsigned int i = stânga ; i <= dreapta ; i ++ ) { if ( l_cur <= mijloc && r_cur <= dreapta ) { if ( l_buff [ l_cur ] < r_buff [ r_cur ]) { target [ i ] = l_buff [ l_cur ]; l_cur ++ ; } altfel { target [ i ] = r_buff [ r_cur ]; r_cur ++ ; } } else if ( l_cur <= mijloc ) { target [ i ] = l_buff [ l_cur ]; l_cur ++ ; } altfel { target [ i ] = r_buff [ r_cur ]; r_cur ++ ; } } ținta de întoarcere ; }

Implementare în C++11 :

#include <algoritm> #include <cstddef> #include <iterator> #include <memorie> template < typenameT > _ void merge_sort ( T array [], std :: size_t size ) noexcept { dacă ( mărime > 1 ) { std :: size_t const left_size = dimensiune / 2 ; std :: size_t const right_size = size - left_size ; merge_sort ( & array [ 0 ], left_size ); merge_sort ( & array [ dimensiunea_stânga ], dimensiunea_dreapta ); std :: size_t lidx = 0 , ridx = left_size , idx = 0 ; std :: unique_ptr < T [] > tmp_array ( nou T [ dimensiune ]); while ( lidx < left_size || ridx < size ) { if ( matrice [ lidx ] < matrice [ ridx ]) { tmp_array [ idx ++ ] = std :: move ( array [ lidx ]); lidx ++ ; } altfel { tmp_array [ idx ++ ] = std :: mutare ( array [ ridx ]); ridx ++ ; } if ( lidx == left_size ) { std :: copy ( std :: make_move_iterator ( & array [ ridx ]), std :: make_move_iterator ( & matrice [ dimensiune ]), & tmp_array [ idx ]); rupe ; } dacă ( ridx == dimensiune ) { std :: copy ( std :: make_move_iterator ( & array [ lidx ]), std :: make_move_iterator ( & array [ left_size ]), & tmp_array [ idx ]); rupe ; } } std :: copiere ( std :: make_move_iterator ( tmp_array ), std :: make_move_iterator ( & tmp_array [ dimensiune ]), matrice ); } }

Implementare în C++14 cu paralelizare OpenMP

#include <algoritm> #include <iterator> #include <omp.h> #include <memorie> template < typenameIterator > _ void mergesort ( Iterator de la , Iterator la ) { #pragma omp paralel { #pragma omp single acum static_assert ( ! std :: is_same < typename std :: iterator_traits < Iterator >:: value_type , void >:: value ); auto n = std :: distanta ( de la , la ); dacă ( 1 < n ) { #pragma omp task firstprivate (de la, la, n) { Iterator l_from = din ; Iterator l_to = l_from ; std :: advance ( l_to , n / 2 ); mergesort ( l_from , l_to ); } #pragma omp task firstprivate (de la, la, n) { Iterator r_from = din ; std :: advance ( r_from , n / 2 ); Iterator r_to = r_from ; std :: advance ( r_to , n - ( n / 2 )); mergesort ( r_from , r_to ); } #pragma omp taskwait auto tmp_array = std :: make_unique < typename Iterator :: value_type [] > ( n ); Iterator l_iter = din ; Iterator l_end = l_iter ; std :: advance ( l_end , n / 2 ); Iterator r_iter = l_end ; Iterator & r_end = la ; auto tmp_iter = tmp_array . obține (); while ( l_iter != l_end || r_iter != r_end ) { if ( * l_iter < * r_iter ) { * tmp_iter = std :: move ( * l_iter ); ++ l_iter ; ++ tmp_iter ; } altfel { * tmp_iter = std :: move ( * r_iter ); ++ r_iter ; ++ tmp_iter ; } if ( l_iter == l_end ) { std :: copie ( std :: make_move_iterator ( r_iter ), std :: make_move_iterator ( r_end ), tmp_iter ); rupe ; } if ( r_iter == r_end ) { std :: copie ( std :: make_move_iterator ( l_iter ), std :: make_move_iterator ( l_end ), tmp_iter ); rupe ; } } std :: copie ( std :: make_move_iterator ( tmp_array.get ( ) ), std :: make_move_iterator ( & tmp_array [ n ]), din ); } } }

Implementare iterativă în C++ :

template < 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 ; pentru ( BlockSizeIterator = 1 ; BlockSizeIterator < l ; BlockSizeIterator *= 2 ) { pentru ( BlockIterator = 0 ; BlockIterator < l - BlockSizeIterator ; BlockIterator += 2 * BlockSizeIterator ) { //Contopim cu sortarea unei perechi de blocuri pornind de la elementul BlockIterator //cel din stânga cu dimensiunea BlockSizeIterator, cel din dreapta cu dimensiunea BlockSizeIterator sau mai puțin LeftBlockIterator = 0 ; RightBlockIterator = 0 ; LeftBorder = BlockIterator ; MidBorder = BlockIterator + BlockSizeIterator ; RightBorder = BlockIterator + 2 * BlockSizeIterator ; RightBorder = ( RightBorder < l ) ? Chenar drept : l ; int * SortedBlock = new int [ RightBorder - LeftBorder ]; //În timp ce ambele matrice au elemente, selectați-l pe cel mai mic și puneți-l în blocul sortat în timp ce ( LeftBorder + LeftBlockIterator < MidBorder && MidBorder + RightBlockIterator < RightBorder ) { if ( a [ LeftBorder + LeftBlockIterator ] < a [ MidBorder + RightBlockIterator ]) { SortedBlock [ LeftBlockIterator + RightBlockIterator ] = a [ LeftBorder + LeftBlockIterator ]; LeftBlockIterator += 1 ; } altfel { SortedBlock [ LeftBlockIterator + RightBlockIterator ] = a [ MidBorder + RightBlockIterator ]; RightBlockIterator += 1 ; } } //După aceea, aducem elementele rămase din blocul din stânga sau din dreapta în timp ce ( LeftBorder + LeftBlockIterator < MidBorder ) { SortedBlock [ LeftBlockIterator + RightBlockIterator ] = a [ LeftBorder + LeftBlockIterator ]; LeftBlockIterator += 1 ; } while ( Bord mijlociu + RightBlockIterator < RightBorder ) { SortedBlock [ LeftBlockIterator + RightBlockIterator ] = a [ MidBorder + RightBlockIterator ]; RightBlockIterator += 1 ; } pentru ( MergeIterator = 0 ; MergeIterator < LeftBlockIterator + RightBlockIterator ; MergeIterator ++ ) { a [ LeftBorder + MergeIterator ] = SortedBlock [ MergeIterator ]; } șterge SortedBlock ; } } }


Implementare în Python :

def merge_sort ( A ): dacă len ( A ) == 1 sau len ( A ) == 0 : întoarce 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 )) în timp ce n < len ( L ) și m < len ( R ): dacă L [ n ] <= R [ m ]: C [ k ] = L [ n ] n += 1 altceva : C [ k ] = R [ m ] m += 1 k += 1 în timp ce n < len ( L ): C [ k ] = L [ n ] n += 1 k += 1 în timp ce m < len ( R ): C [ k ] = R [ m ] m += 1 k += 1 pentru i în interval ( len ( A )): A [ i ] = C [ i ] întoarce A


Pseudocod al algoritmului de îmbinare fără „atașare” restului într-un limbaj asemănător C++ :

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

Algoritmul a fost inventat de John von Neumann în 1945 [1] .

Algoritmul de mai sus într-un limbaj asemănător C++ utilizează o verificare a egalității a două elemente comparate ale subbaryurilor cu un bloc de procesare separat în caz de egalitate. O verificare separată a egalității dublează numărul de comparații, ceea ce complică codul programului. În loc de o verificare separată a egalității și un bloc separat de procesare a egalității, puteți utiliza două verificări if(L <= R) și if(L >= R) , ceea ce aproape înjumătățit codul programului.

Pseudo-cod al unui algoritm de îmbinare îmbunătățit fără a „atașa” restul într-un limbaj asemănător C++ :

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

Numărul de verificări poate fi redus la jumătate prin eliminarea verificării if(L >= R) . În acest caz, dacă L și R sunt egali, L va fi scris în Out în prima iterație și R - în a doua. Această opțiune va funcționa eficient dacă matricea originală nu are elemente duplicate care predomină asupra restului elementelor.

Pseudocod pentru un algoritm de îmbinare scurtat fără a „atașa” restul într-un limbaj asemănător C++ :

L = *In1; R = *In2; dacă( L <= R ) { *Out++ = L; In1++; } altfel { *Out++ = R; In2++; }

Cele două operații de transfer la variabilele L și R simplifică unele dintre intrările de program, care pot fi utile în scopuri didactice, dar în programele reale pot fi eliminate, ceea ce va reduce codul programului. De asemenea, puteți utiliza operatorul ternar , care va reduce și mai mult codul programului.
Pseudocod pentru un algoritm de îmbinare și mai avansat fără a „atașa” restul într-un limbaj asemănător C++ :

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

Timpul de rulare al algoritmului este O(n * log n) în absența degradării în cazurile proaste, ceea ce este un punct dureros de sortare rapidă (de asemenea, un algoritm de ordinul O(n * log n), dar numai pentru cazul mediu ). Consumul de memorie este mai mare decât pentru sortarea rapidă, cu un model de alocare a memoriei mult mai favorabil - este posibil să se aloce o regiune de memorie de la bun început și să nu se aloce mai târziu.

O implementare populară necesită un buffer de memorie temporar alocat unic, egal cu matricea care este sortată și nu are recursiuni. Etape de implementare:

  1. InputArray = matrice sortabilă, OutputArray = buffer temporar;
  2. peste fiecare segment al matricei de intrare InputArray[N * MIN_CHUNK_SIZE..(N + 1) * MIN_CHUNK_SIZE] se efectuează un algoritm de sortare auxiliar, de exemplu, sortare Shell sau sortare rapidă;
  3. setați ChunkSize = MIN_CHUNK_SIZE;
  4. îmbina două segmente InputArray[N * ChunkSize..(N + 1) * ChunkSize] și InputArray[(N + 1) * ChunkSize..(N + 2) * ChunkSize] trecând alternativ la stânga și la dreapta (vezi mai sus), rezultat este plasat în OutputArray[N * ChunkSize..(N + 2) * ChunkSize] și așa mai departe pentru toate N până când se ajunge la sfârșitul matricei;
  5. ChunkSize este dublat;
  6. dacă ChunkSize a devenit >= dimensiunea matricei, atunci final, rezultatul este în OutputArray, care (datorită permutărilor descrise mai jos) este fie un tablou de sortat, fie un buffer temporar, în al doilea caz este copiat în întregime în matrice a fi sortat;
  7. în caz contrar, InputArray și OutputArray sunt schimbate prin permutarea pointerilor și totul se repetă de la punctul 4.

Această implementare acceptă, de asemenea, plasarea matricei de sortat și a tamponului temporar în fișiere de disc, făcându-l potrivit pentru sortarea unor cantități uriașe de date. Implementarea ORDER BY în MySQL în absența unui index adecvat funcționează exact așa (sursa: filesort.cc în codul sursă MySQL).

Un exemplu de implementare a unui algoritm simplu de îmbinare în două sensuri în pseudocod:

funcția mergesort(m) var listă stânga, dreapta, rezultat dacă lungimea(m) ≤ 1 returnează m altfel mijloc = lungime (m) / 2 pentru fiecare x în m până la mijloc adăugați x la stânga pentru fiecare x în m după mijloc adăugați x la dreapta stânga = mergesort(stânga) dreapta = mergesort(dreapta) rezultat = îmbinare (stânga, dreapta) returnează rezultatul final dacă

Există mai multe variante ale funcției merge(), cea mai simplă ar putea arăta astfel:

funcția merge(stânga, dreapta) var listă rezultat în timp ce lungime(stânga) > 0 și lungime(dreapta) > 0 dacă primul(stânga) ≤ primul(dreapta) adăugați primul (stânga) la rezultat stânga = odihnă (stânga) altfel adăugați primul (dreapta) la rezultat dreapta = odihnă (dreapta) termina dacă în timp ce lungimea (stânga) > 0 adăugați primul (stânga) la rezultat stânga = odihnă (stânga) în timp ce lungimea (dreapta) > 0 adăugați primul (dreapta) la rezultat dreapta = odihnă (dreapta) returnează rezultatul

Avantaje și dezavantaje

Avantaje:

  • Funcționează chiar și pe structuri de date cu acces secvenţial.
  • Se combină bine cu paginarea și memoria cache .
  • Funcționează bine în paralel : este ușor să împărțiți sarcinile între procesoare în mod egal, dar este greu să preluați alte procesoare dacă un procesor întârzie.
  • Nu are intrări „dificile”.
  • Stabil - păstrează ordinea elementelor egale (aparținând aceleiași clase de echivalență prin comparație).

Defecte:

  • Pe matrice „aproape sortate”, durează la fel de mult ca și pe cele haotice. Există o variantă de sortare de îmbinare care este mai rapidă pentru datele sortate parțial, dar necesită memorie suplimentară în plus față de tamponul temporar care este utilizat direct pentru sortare.
  • Necesită memorie suplimentară pentru dimensiunea matricei originale.

Note

  1. ↑ Knuth, D.E. The Art of Computer Programming. Volumul 3 : Sortare și căutare  . — al 2-lea. - Addison-Wesley , 1998. - P. 159. - ISBN 0-201-89685-0 .

Literatură

  • Levitin A. V. Capitolul 4. Metoda de descompunere: Merge sort // Algoritmi. Introducere în dezvoltare și analiză - M . : Williams , 2006. - S. 169-172. — 576 p. — ISBN 978-5-8459-0987-9
  • Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algorithms: construction and analysis = Introduction to Algorithms / Ed. I. V. Krasikova. - Ed. a II-a. - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .

Link -uri

 Algoritmi de sortare
Teorie Complexitate O notație Relația de comandă Sortați tipuri durabil Intern Extern
schimb valutar
Alegere
inserții
fuziune
Fara comparatii
hibrid
Alte
nepractic