BPC-ALD - Skripta_rev2019_2
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
n
vk
= .
A odtud použitím logaritmu
)
(
log n
k
v
=
.
Počet průchodů logaritmicky závisí na počtu tříděných prvků. Když to vynásobíme lineární
složitostí jednoho průchodu, dostáváme, že složitost popsané metody vnějšího třídění je
Θ(n*log(n)). Už jsme se zmínili, že tato složitost je pro třídění nejmenší možná, tedy optimální.
3.4.2 Vnější třídění s využitím vnitřního třídění
V předchozím popisu vnějšího třídění se ve fázi rozdělování vytvářely běhy obsahující jen jeden
prvek. Zde se nabízí myšlenka využít některé metody vnitřního třídění a ve fázi rozdělování
vytvářet běhy delší než 1. Pak by zřejmě bylo zapotřebí méně průchodů zatřiďování a celkový
čas pro třídění by se tím zkrátil. Tento postup budeme aplikovat tak, že stanovíme nějaký počet
prvků m, který se ještě vejde do paměti. Při rozdělování vždy do paměti načteme m prvků, ty
v ní setřídíme, přirozeně některou z efektivních metod (Quicksort, třídění haldou), a po setřídění
je zapíšeme do příslušného výstupního souboru jako jeden běh. Nyní pro počty běhů při
následných průchodech zatřiďování bude platit
Průchod
Délka vstupních běhů
Délka výstupních běhů
1
m
m
∗ v
2
m
∗ v
m
∗ v2
3
m
∗ v2
m
∗ v3
…
…
…
k
m
∗ v(k-1)
m
∗ vk
Odtud pro poslední k-tý běh dostáváme vztah
n
v
m
k
=
∗
.
A použitím logaritmu
)
(
log
)
(
log
m
n
k
v
v
−
=
.
Z toho je zřejmé, že čím bude délka běhů m vytvářených vnitřním tříděním ve fázi rozdělování
větší, tím více ušetříme průchodů zatřiďování. To se dalo i očekávat.