BPC-ALD_Zpracované_otazky_ke_zkousce
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.
ho jako as // zpravidla se při sudém počtu bere z 2 prostřeních levý (podle skript), ale ani pravým chybu neuděláte
• Provedeme srovnání hledané hodnoty x a hodnoty as
• x < as => provedeme rekurzivně předchozí dva body na část A (je-li oblast A prázdná hledání neúspěšně
končí)
• Pokud neplatí provedeme porovnání
• x > as => provedeme rekurzivně předchozí dva body na část B (je-li oblast B prázdná hledání neúspěšně
končí)
• Pokud neplatí ani jedna podmínka srovnáme ještě jestli x = as (když neplatí => hledání neúspěšně končí)
Přednáška 8: Úvod do třídicích algoritmů, definice třídicí úlohy, vnitřní a vnější metody třídění,
třídění přímým vkládáním, odvození složitosti algoritmu Insert Sort (Ing. Tomáš Macho, Ph.D.)
1. Vysvětlete rozdíl mezi algoritmy vnějšího a vnitřního třídění (řazení). Za jakých podmínek použijeme vnější
třídění. (+) − Vnitřní třídění - během třídění jsou všechny tříděné prvky uloženy v operační (vnitřní) paměti počítače a
veškeré operace probíhají výlučně s těmito hodnotami
− Vnější třídění - tříděné prvky jsou uloženy v souborech ve vnější paměti (disk), po malých částech jsou
vkládány do vnitřní paměti, kde se nad nimi provedou operace a následně jsou uloženy zpět na vnější
paměť
-
Využívá se, pokud je objem dat tak velký, že pro něj nestačí vnitřní paměť - výrazně pomalejší
2. Je dána např. posloupnost čísel: 7, 1, 2, 8, 2, 4, 5, 3, 1, 9.
Popište konkrétně jednotlivé kroky třídění přímým
vkládáním (Insert Sort) a uveďte po každém kroku
částečně setříděnou posloupnost. (Uvažujme vzestupné
třídění.) (+++)
1. poslupnosť rozdelíme na zoradenú a nezoradenú časť tak, že