Sloučit třídění

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 6. října 2018; kontroly vyžadují 47 úprav .
Sloučit třídění

Příklad řazení sloučení. Nejprve rozdělíme seznam na části (každý 1 prvek), poté každý prvek porovnáme s jeho sousedem, seřadíme a sloučíme. Výsledkem je, že všechny prvky jsou seřazeny a kombinovány dohromady.
Autor John von Neumann
účel Algoritmus řazení
Datová struktura seznam , pole
nejhorší čas
Nejlepší čas
Průměrný čas
Náklady na paměť pro seznam, pro pole
 Mediální soubory na Wikimedia Commons

Merge sort je třídicí algoritmus ,  který uspořádává seznamy (nebo jiné datové struktury , k jejichž prvkům lze přistupovat pouze sekvenčně , například streamy ) v určitém pořadí. Toto třídění je dobrým příkladem použití principu rozděl a panuj . Nejprve je úkol rozdělen do několika menších dílčích úkolů. Tyto úlohy se pak řeší rekurzivním voláním nebo přímo, pokud je jejich velikost dostatečně malá. Nakonec se jejich řešení spojí a získá se řešení původního problému.

Podrobný algoritmus třídění

Chcete-li vyřešit problém řazení, tyto tři kroky vypadají takto:

  1. Pole , které se má třídit , je rozděleno na dvě části přibližně stejné velikosti;
  2. Každá z výsledných částí je tříděna samostatně, například stejným algoritmem;
  3. Dvě uspořádaná pole poloviční velikosti se sloučí do jednoho.

1.1. — 2.1. K rekurzivnímu dělení úlohy na menší dochází, dokud velikost pole nedosáhne jedničky (libovolné pole délky 1 lze považovat za uspořádané).

3.1. Kombinace dvou uspořádaných polí do jednoho.
Základní myšlenku sloučení dvou seřazených polí lze vysvětlit na následujícím příkladu. Předpokládejme, že již máme dvě podpole seřazené vzestupně. Poté:
3.2. Sloučení dvou podpolí do třetího výsledného pole.
V každém kroku vezmeme menší z prvních dvou prvků podpolí a zapíšeme jej do výsledného pole. Čítače počtu prvků výsledného pole a podpole, ze kterého byl prvek odebrán, se zvýší o 1.
3.3. "Příloha" zbytku.
Když jedno z podpolí skončí, přidáme do výsledného pole všechny zbývající prvky druhého podpole.

Příklad řazení v C

/** * Seřadí pole pomocí rekurzivního sloučení řazení * nahoru - ukazatel na pole, které se má seřadit * dolů - ukazatel na pole s alespoň stejnou velikostí jako 'nahoru', použito jako vyrovnávací paměť * levý levý okraj pole, předat 0 seřadit pole od začátku * vpravo - pravý okraj pole, předat délku pole - 1 pro seřazení pole do posledního prvku * vrátí: ukazatel na seřazené pole. Vzhledem k tomu, jak tato implementace funguje * setříděná verze pole může skončit buď v 'nahoru' nebo 'dolů' **/ int * merge_sort ( int * nahoru , int * dolů , unsigned int vlevo , unsigned int vpravo ) { if ( vlevo == vpravo ) { dolů [ vlevo ] = nahoru [ vlevo ]; vrátit se dolů ; } unsigned int middle = left + ( right - left ) / 2 ; // rozdělení a řazení int * l_buff = merge_sort ( nahoru , dolů , vlevo , uprostřed ); int * r_buff = merge_sort ( nahoru , dolů , uprostřed + 1 , vpravo ); // sloučení dvou seřazených polovin int * target = l_buff == up ? dolů : nahoru ; unsigned int l_cur = vlevo , r_cur = prostřední + 1 ; for ( unsigned int i = left ; i <= right ; i ++ ) { if ( l_cur <= střední && r_cur <= vpravo ) { if ( l_buff [ l_cur ] < r_buff [ r_cur ]) { cíl [ i ] = l_buff [ l_cur ]; l_cur ++ ; } jiný { cíl [ i ] = r_buff [ r_cur ]; r_cur ++ ; } } else if ( l_cur <= middle ) { cíl [ i ] = l_buff [ l_cur ]; l_cur ++ ; } jiný { cíl [ i ] = r_buff [ r_cur ]; r_cur ++ ; } } návratový cíl ; }

Implementace v C++11 :

#include <algoritmus> #include <cstddef> #include <iterátor> #include <paměť> šablona < typenameT > _ void merge_sort ( T pole [], std :: size_t size ) noexcept { if ( velikost > 1 ) { std :: size_t const left_size = velikost / 2 ; std :: size_t const right_size = size - left_size ; merge_sort ( & pole [ 0 ], left_size ); merge_sort ( & pole [ left_size ], right_size ); std :: size_t lidx = 0 , ridx = left_size , idx = 0 ; std :: unique_ptr < T [] > tmp_array ( new T [ size ]); while ( lidx < left_size || ridx < size ) { if ( pole [ lidx ] < pole [ ridx ]) { tmp_array [ idx ++ ] = std :: move ( array [ lidx ]); lidx ++ ; } jiný { tmp_array [ idx ++ ] = std :: move ( pole [ ridx ]); ridx ++ ; } if ( lidx == left_size ) { std :: copy ( std :: make_move_iterator ( & pole [ ridx ]), std :: make_move_iterator ( & pole [ velikost ]), & tmp_array [ idx ]); zlomit ; } if ( ridx == velikost ) { std :: copy ( std :: make_move_iterator ( & pole [ lidx ]), std :: make_move_iterator ( & pole [ left_size ]), & tmp_array [ idx ]); zlomit ; } } std :: copy ( std :: make_move_iterator ( tmp_array ), std :: make_move_iterator ( & tmp_array [ velikost ]), pole ); } }

Implementace v C++14 s paralelizací OpenMP

#include <algoritmus> #include <iterátor> #include <omp.h> #include <paměť> šablona < typenameIterator > _ void mergesort ( iterátor z , iterátor do ) { #pragma omp paralela { #pragma omp single nowait static_assert ( ! std :: is_same < typename std :: iterator_traits < Iterator >:: value_type , void >:: value ); auto n = std :: vzdálenost ( od , do ); if ( 1 < n ) { #pragma omp task firstprivate (od, do, n) { Iterátor l_from = from ; Iterátor l_to = l_from ; std :: záloha ( l_to , n / 2 ); mergesort ( l_od , l_do ); } #pragma omp task firstprivate (od, do, n) { Iterátor r_from = from ; std :: záloha ( r_od , n / 2 ); Iterátor r_to = r_from ; std :: záloha ( r_to , n - ( n / 2 )); mergesort ( r_from , r_to ); } #pragma omp taskwait auto tmp_array = std :: make_unique < název_typu Iterátor :: typ_hodnoty [] > ( n ); Iterátor l_iter = od ; Iterátor l_end = l_iter ; std :: záloha ( l_konec , n / 2 ); Iterátor r_iter = l_konec ; Iterátor & r_end = to ; auto tmp_iter = tmp_array . získat (); while ( l_iter != l_end || r_iter != r_end ) { if ( * l_iter < * r_iter ) { * tmp_iter = std :: move ( * l_iter ); ++ l_iter ; ++ tmp_iter ; } jiný { * tmp_iter = std :: move ( * r_iter ); ++ r_iter ; ++ tmp_iter ; } if ( l_iter == l_end ) { std :: kopie ( std :: make_move_iterator ( r_iter ), std :: make_move_iterator ( r_end ), tmp_iter ); zlomit ; } if ( r_iter == r_end ) { std :: kopie ( std :: make_move_iterator ( l_iter ), std :: make_move_iterator ( l_end ), tmp_iter ); zlomit ; } } std :: kopie ( std :: make_move_iterator ( tmp_array.get ( ) ), std :: make_move_iterator ( & tmp_array [ n ]), z ); } } }

Iterativní implementace v C++ :

šablona < 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 ) { //Sloučíme se řazením dvojice bloků počínaje prvkem BlockIterator //levý s velikostí BlockSizeIterator, pravý s velikostí BlockSizeIterator nebo méně LeftBlockIterator = 0 ; RightBlockIterator = 0 ; LeftBorder = BlockIterator ; MidBorder = BlockIterator + BlockSizeIterator ; RightBorder = BlockIterator + 2 * BlockSizeIterator ; RightBorder = ( RightBorder < l ) ? RightBorder : l ; int * SortedBlock = new int [ RightBorder - LeftBorder ]; //Zatímco obě pole mají prvky, vyberte ten menší a vložte jej do seřazeného bloku , zatímco ( LeftBorder + LeftBlockIterator < MidBorder && MidBorder + RightBlockIterator < RightBorder ) { if ( a [ LeftBorder + LeftBlockIterator ] < a [ MidBorder + RightBlockIterator ]) { SortedBlock [ LeftBlockIterator + RightBlockIterator ] = a [ LeftBorder + LeftBlockIterator ]; LeftBlockIterator += 1 ; } jiný { SortedBlock [ LeftBlockIterator + RightBlockIterator ] = a [ MidBorder + RightBlockIterator ]; RightBlockIterator += 1 ; } } //Poté přivedeme zbývající prvky z levého nebo pravého bloku while ( 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 ] = SortedBlock [ MergeIterator ]; } odstranit SortedBlock ; } } }


Implementace v Pythonu :

def merge_sort ( A ): pokud len ( A ) == 1 nebo len ( A ) == 0 : vrátit A L = merge_sort ( A [: len ( A ) // 2 ]) R = merge_sort ( A [ délka ( A ) // 2 :]) n = m = k = 0 C = [ 0 ] * ( len ( L ) + len ( R )) zatímco n < len ( L ) a m < len ( R ): jestliže L [ n ] <= R [ m ]: C [ k ] = L [ n ] n + = 1 jinak : C [ k ] = R [ m ] m += 1 k += 1 zatímco n < len ( L ): C [ k ] = L [ n ] n + = 1 k += 1 zatímco m < len ( R ): C [ k ] = R [ m ] m += 1 k += 1 pro i v dosahu ( len ( A )): A [ i ] = C [ i ] vrátit A


Pseudokód slučovacího algoritmu bez "připojení" zbytku v jazyce podobném C++ :

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

Algoritmus vynalezl John von Neumann v roce 1945 [1] .

Výše uvedený algoritmus v jazyce podobném C++ používá v případě rovnosti kontrolu rovnosti dvou porovnávaných prvků podpolí se samostatným blokem zpracování. Samostatná kontrola rovnosti zdvojnásobuje počet srovnání, což komplikuje programový kód. Namísto samostatné kontroly rovnosti a samostatného bloku zpracování rovnosti můžete použít dvě kontroly if(L <= R) a if(L >= R) , čímž se kód programu zmenší téměř na polovinu.

Pseudokód vylepšeného slučovacího algoritmu bez „připojení“ zbytku v jazyce podobném C++ :

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

Počet kontrol lze snížit na polovinu odstraněním kontroly if(L >= R) . V tomto případě, pokud jsou L a R stejné, L bude zapsáno do Out v první iteraci a R - ve druhé. Tato možnost bude efektivně fungovat, pokud původní pole nemá duplicitní prvky převažující nad zbytkem prvků.

Pseudokód pro zkrácený slučovací algoritmus bez "připojení" zbytku v jazyce podobném C++ :

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

Dvě operace přenosu do proměnných L a R zjednodušují některé položky programu, což může být užitečné pro účely výuky, ale ve skutečných programech je lze odstranit, což sníží kód programu. Můžete také použít ternární operátor , který dále zmenší kód programu.
Pseudokód pro ještě pokročilejší slučovací algoritmus bez „připojování“ zbytku v jazyce podobném C++ :

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

Doba běhu algoritmu je O(n * log n) při absenci degradace na špatných případech, což je bolestné místo rychlého třídění (také algoritmus řádu O(n * log n), ale pouze pro průměrný případ ). Spotřeba paměti je vyšší než u rychlého řazení, s mnohem příznivějším vzorem přidělování paměti - je možné alokovat jednu oblast paměti od samého začátku a později již nepřidělovat.

Populární implementace vyžaduje jednorázově přidělenou dočasnou vyrovnávací paměť rovnající se tříděnému poli a nemá žádné rekurze. Kroky implementace:

  1. InputArray = tříditelné pole, OutputArray = dočasný buffer;
  2. nad každým segmentem vstupního pole InputArray[N * MIN_CHUNK_SIZE..(N + 1) * MIN_CHUNK_SIZE] se provede nějaký pomocný třídící algoritmus, například Shell sort nebo quick sort;
  3. set ChunkSize = MIN_CHUNK_SIZE;
  4. sloučit dva segmenty InputArray[N * ChunkSize..(N + 1) * ChunkSize] a InputArray[(N + 1) * ChunkSize..(N + 2) * ChunkSize] střídavým krokováním doleva a doprava (viz výše), výsledek je umístěn do OutputArray[N * ChunkSize..(N + 2) * ChunkSize] a tak dále pro všechna N, dokud není dosaženo konce pole;
  5. ChunkSize je zdvojnásobena;
  6. pokud se ChunkSize stala >= velikost pole, pak end, výsledek je v OutputArray, což je (kvůli permutacím popsaným níže) buď pole, které se má třídit, nebo dočasný buffer, ve druhém případě se celý zkopíruje do pole být tříděn;
  7. jinak jsou InputArray a OutputArray prohozeny permutačními ukazateli a vše se opakuje od bodu 4.

Tato implementace také podporuje umístění pole k třídění a dočasné vyrovnávací paměti do souborů na disku, takže je vhodná pro třídění velkého množství dat. Implementace ORDER BY v MySQL při absenci vhodného indexu funguje přesně takto (zdroj: filesort.cc ve zdrojovém kódu MySQL).

Příklad implementace jednoduchého dvoucestného slučovacího algoritmu v pseudokódu:

funkce mergesort(m) var list left, right, result if length(m) ≤ 1 return m else střed = délka (m) / 2 pro každé x v m až do středu přidejte x doleva pro každé x v m po středu přidejte x doprava vlevo = mergesort(left) vpravo = mergesort (vpravo) výsledek = sloučit (vlevo, vpravo) vrátit výsledek end if

Existuje několik variant funkce merge(), ta nejjednodušší může vypadat takto:

funkce merge(left,right) var list result while length(left) > 0 and length(right) > 0 if first(left) ≤ first(right) připojit první (vlevo) k výsledku vlevo = odpočinek (vlevo) jiný připojit první (vpravo) k výsledku vpravo = odpočinek (vpravo) end if while length(left) > 0 připojit první (vlevo) k výsledku vlevo = odpočinek (vlevo) zatímco délka (vpravo) > 0 připojit první (vpravo) k výsledku vpravo = odpočinek (vpravo) vrátit výsledek

Výhody a nevýhody

výhody:

  • Funguje i na sekvenční přístupové datové struktury.
  • Dobře se kombinuje se stránkováním a ukládáním do mezipaměti .
  • Funguje dobře paralelně : je snadné rozdělit úlohy mezi procesory rovnoměrně, ale je těžké přimět jiné procesory, aby převzaly řízení, pokud je jeden procesor zpožděn.
  • Nemá žádné "obtížné" vstupy.
  • Stabilní - zachovává pořadí stejných prvků (patřících ve srovnání do stejné třídy ekvivalence).

nedostatky:

  • Na „téměř seřazených“ polích to trvá stejně dlouho jako na chaotických. Existuje varianta slučovacího řazení, která je rychlejší na částečně setříděná data, ale kromě dočasné vyrovnávací paměti, která se používá přímo pro řazení, vyžaduje další paměť.
  • Vyžaduje další paměť pro velikost původního pole.

Poznámky

  1. ↑ Knuth, D.E. The Art of Computer Programming. Svazek 3 : Třídění a vyhledávání  . — 2. - Addison-Wesley , 1998. - S. 159. - ISBN 0-201-89685-0 .

Literatura

  • Levitin A. V. Kapitola 4. Metoda rozkladu: Merge sort // Algorithms. Úvod do vývoje a analýzy - M .: Williams , 2006. - S. 169-172. — 576 s. — ISBN 978-5-8459-0987-9
  • Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmy: konstrukce a analýza = Introduction to Algorithms / Ed. I. V. Krasíková. - 2. vyd. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .

Odkazy

 Algoritmy řazení
Teorie Složitost O zápis Objednávkový vztah Seřadit typy udržitelného Vnitřní Externí
Výměna
Výběr
vložky
fúze
Žádné srovnání
hybridní
jiný
nepraktický