Řazení
Řazení dělením
 Vytisknout studijní materiál

Řazení dělením

Algoritmus řazení dělením je pravděpodobně nejpoužívanější algoritmus řazení. Byl objeven C.A.R. Hoarem v roce 1960 a má mnoho verzí.

Algoritmus je založen na rekurzivním řazení pole prvků děleného na dvě části, přičemž základní případ je jednoprvková nebo prázdná část, které jsou vlastně „seřazeny“. Rekurzivní metoda razeniDelenimR( ) je na obr.. Její parametry jsou indexy krajního levého a pravého prvku řazené části.

Základem uvedeného algoritmu je metoda deleni( ), která přeuspořádá řazené pole tak, aby byly splněny následující podmínky:

1. Prvek a[i] je na své správné konečné pozici.

2. Prvky a[l], ..., a[i-1] jsou menší nebo rovny a[i].

3. Prvky a[i+1], ..., a[p] jsou větší nebo rovny a[i].

Napřed musíme zvolit dělící prvek, také nazývaný pivotem, který bude při dělení umístněn na konečnou pozici. Je zřejmé, že uvedený rekurzivní algoritmus seřadí prvky pole, ať zvolíme jako dělící prvek kterýkoliv prvek řazeného pole. Zvolme tedy a[p].

Obecně, na splnění uvedených podmínek projdeme pole zleva dokud nenalezneme větší prvek než dělící prvek v a dále ho projdeme zprava dokud nenalezneme menší prvek než dělící prvek. Tyto dva prvky pak vyměníme.

Na obr. index i prochází prvky pole zleva a index j zprava. Procházení zleva zastavíme, když a[i] > v a procházení sprava zastavíme, když a[j] <v. Potom prvky a[i] a a[j] vyměníme.

Specielně, pří nalezení prvku stejného jako dělící prvek, pole tedy obsahuje duplicitní klíče, můžeme zastavit procházení a tento použít na výměnu, protože tím neporušíme invariant naznačený na obr.. Navíc tato strategie vede k vyváženému dělení pole.

Když se indexy procházení zleva a zprava zkříží, vyměníme a[p] s prvkem, jenž je v části s většími prvky nejvíce vlevo, tj. a[i]. Tím jsme dosáhli toho, že na a[i] je dělící prvek, vlevo od něj prvky menší nebo rovné a vpravo od něj prvky větší nebo rovné. Dělící prvek je tedy na konečné správné pozici. Metoda deleni( ) je na obr.. Je-li dělící prvek největším prvkem, potom se na něm, pokud nemá duplikáty, zastaví procházení zleva. Na druhé straně, je-li dělící prvek nejmenším prvkem, procházení zprava je na levém konci zastaveno explicitně. Příklad dělení posloupnosti prvků je na obr. a její řazení je na obr.. Program pro řazení pole dělením je na obr..

Analýza řazení dělením

Efektivnost řazení dělením závisí na tom jak vyvážené je rozdělení řazené posloupnosti. Nejhorší případ nastane, když při každém dělení vznikne jedna část prázdná a druhá se zbývajícími prvky, kromě dělícího prvku, čímž vznikne nejvíc nevyvážené dělení. Časová náročnost dělení posloupnosti s n prvky, je úměrná n. Konstantu úměrnosti považujme za jednotkovou, jakož i seřazení jednoprvkové nebo prázdné posloupnosti. Potom pro n > 1 čas řazení dělením je

T(n) = T(n-1) + n

řešením je

T(n) = n(n + 1)/2 = O(n2)

Tato situace nastane například když algoritmus řazení dělením aplikujeme na již seřazenou posloupnost. Navíc hloubka zásobníku bude také odpovídat n rekurzivním voláním.

Nejlepší případ nastane, vzniknou-li každým dělení dvě poloviční posloupnosti, kdy čas řazení dělením je

T(n) =2 T(n /2) + n

a

T(n) ≈ n log2 n

Důležitý je průměrný případ. Za předpokladu, že všechny permutace jsou stejně pravděpodobné a posloupnost byla rozdělena na části o velikosti k - 1 a n - k, vyjádření času výpočtu počtem porovnání, s uvážením zkřížení indexů při procházení pole je

přičemž T(0) = T(1) = 0

Řešením uvedené rekurentní rovnice, podobně jako u hlubky BVS v průměrném případě, dostaneme

T(n) ≈ 2 ln n ≈ 1.39n log2 n

tedy

T(n) = O(n log2 n)

I pro řazení dělením můžeme použít explicitní zásobník (obr.). V nejhorším případě dosáhne velikosti úměrné n, například je-li posloupnost již seřazena. V iterační verzi se můžeme podle velikosti úseků vzniklých dělením rozhodnout, kterou vložíme do zásobníku jako první. Vložením většího z nich jako prvního, pokračujeme menším z nich. Tímto způsobem zajistíme, že žádný úsek v zásobníku není větší než polovina úseku pod ním (vkládáme shora) a tedy největší možná velikost bude úměrná log2 n. Tuto velikost zásobník dosáhne, když posloupnost bude vždycky rozdělena uprostřed. Pro téměř uspořádaný soubor bude malá. Příklad nerekurzivního řazení dělením je na obr..