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.
Vybereme nejmenší prvek 5 a zapíšeme ho na výstup.
x1 = 7 v 1. běhu zbývá: 15
x2 = 8 v 2. běhu zbývá: 11 12
Vybereme nejmenší prvek 7 a zapíšeme ho na výstup.
Atd.
Složitost metody Vezměme nejprve, kolik operací zahrnuje operace zatřiďování pro jeden prvek:
jednu operaci čtení, kdy je prvek načten do příslušné proměnné,
v-1 operací srovnání, kdy je tento prvek vybrán jako nejmenší (případně těchto operací může
být méně, když už některé vstupní běhy jsou vyčerpány a příslušné proměnné těchto běhů už
žádný prvek neobsahují),
jednu operaci zápisu, kdy je prvek zapsán do souboru, do něhož je právě výstupní běh ukládán.
Uvážíme-li, že máme n tříděných prvků, pak pro jeden průchod zatřiďování dostáváme
n operaci čtení + přibližně n
∗(v-1) operací srovnání + n operací zápisu.
Protože v je zvolená konstanta, jejíž hodnota je velmi malá vzhledem k počtu tříděných prvků n,
je složitost jednoho průchodu zatřiďování lineární.
Zbývá stanovit, kolik průchodů zatřiďování proběhne. V prvním průchodu zatřiďování, kdy
délka vstupních běhů je 1, vzniknou výstupní běhy délky v. V druhém průchodu zatřiďování,
kdy délka vstupních běhů je v, vzniknou výstupní běhy délky v
∗v. Atd.
Pro zatřiďování
je zapotřebí jen
několik
proměnných.
− 53 −
Průchod
Délka vstupních běhů
Délka výstupních běhů
1
1
v
2
v
v2
3
v2
v3
…
…
…
k
v(k-1)
vk
Třídění končí, když výstupní běh obsahuje všech n tříděných prvků. Tedy pro pořadí
k posledního průchodu dostáváme vztah