BPC-ALD_Zpracované_otazky_ke_zkousce

 Vysvětlete princip metody vnějšího třídění využívající vnitřní třídění. (++) 

Snaha je prodloužit délku jednoho běhu metody se stejným počtem vstupních a výstupních souborů. Pokud by 

byly první běhy delší, pak by bylo potřeba méně průchodů zatřiďování a celkový čas třídění by se zkrátil. 
Stanovíme počet prvků 𝑚, které se vejdou do paměti. Ve fázi rozdělování načteme 𝑚 prvků do paměti, setřídíme 
je některou z efektivních metod vnitřního třídění (Quick Sort, Heap Sort) a setříděnou posloupnost 𝑚 prvků 
uložíme do příslušného výstupního souboru jako jeden běh. 

Přednáška 13: Vyhledávání v lineární datové struktuře, Binární vyhledávání v poli, složitost 

algoritmu. Binární vyhledávací stromy, určení složitost algoritmu. 

 1. Vysvětlete, jak funguje lineární vyhledávání v nesetříděném poli a modifikace lineárního vyhledávání s využitím 

zarážky. (++)  

Musíme postupně procházet prvky (např. směrem od začátku ke konci) a každý prvek srovnat s hledanou hodnotou 𝑥. 

Pokud na prvek 

narazíme, návratovou hodnotou je nejčastěji pozice nalezeného prvku v poli. 

Modifikace s využitím zarážky : 

•  Délku pole zvětšíme o jeden prvek (na 𝑛+1) - resp. při vytváření počítáme se zarážkou a vytvoříme pole o 

velikosti n+1 (pro pole o n prvcích).

•  Jako poslední prvek před každým vyhledáváním dáme hledanou hodnotu 𝑥 - cyklus tak vždy nalezne 

hledanou hodnotu a ukončí se. Tímto se můžeme v každém průběhu cyklu zbavit srovnání, zda i < n a tím 
vyhledávání urychlit.

•  Srovnání i < n použijeme až po ukončení cyklu - pokud bude i < n, byl prvek nalezen. Pokud i = n, prvek 

nalezen nebyl.

2. Je dáno pole obsahující např. vzestupně setříděné prvky: 1, 2, 4, 5, 7, 8, 15, 28, 31, 39. Popište konkrétně 

jednotlivé kroky binárního vyhledávání, pokud hledáme např. prvky: 15 a 38. (+++)