BPC-ALD_Zpracované_otazky_ke_zkousce

najmenší z nezoradenej časti atď. Stačí teda iba postupne vyberať najmenšie prvky z nezoradenej časti a 
umiestňovať ich na koniec zoradenej časti. V prvom kroku hľadáme najmenší prvok poľa, našli sme 1, vymeníme 
s prvým prvkom. (1,7,2,8,2’,4,5,3,1’,9). Prvok na indexe 0 je teda zoradený. Hľadáme najmenší prvok vo zvyšnej 
časti poľa, opäť 1’, vymeníme s prvým prvkom nezoradenej časti poľa teda 7. (1,1’,2,8,2’,4,5,3,7,9) a teda prvky 
na indexoch 0 a 1 sú zoradené. Postup opakujeme kým nie je zoradené celé pole. (1,1’,2,8,2’,4,5,3,7,9) 
(1,1’,2,2’,8,4,5,3,7,9) (1,1’,2,2’,3,4,5,8,7,9,) (1,1’,2,2’,3,4,5,8,7,9) (1,1’,2,2’,3,4,5,8,7,9) (1,1’,2,2’,3,4,5,7,8,9) 
(1,1’,2,2’,3,4,5,7,8,9) //fučela +1 

5.  Jaké základní operace s prvky pole jsou využívány při třídění přímým výběrem (Select Sort).  

Která ze základních operací určuje výslednou míru složitosti a jaká je výsledná míra složitosti. (++) 

Algoritmus je založen na operacích VÝBĚR a VÝMĚNA DVOU PRVKŮ 
Operace VÝBĚRU - KVADRATICKÁ složitost 
Operace VÝMĚNY - LINEÁRNÍ složitost  
VÝSLEDNÁ SLOŽITOST JE TEDY KVADRATICKÁ (O(n^2))! 

Přednáška 10: Účinnější metody vnitřního třídění - Shellovo třídění (Shell Sort), Quick Sort (Ing. 

Tomáš Macho, Ph.D.)

1.  Je dána např. posloupnost čísel: 7, 1, 2, 8, 2’, 4, 5, 3. Popište konkrétně jednotlivé kroky třídění pomocí 

metody (Shell Sort) a uveďte po každém kroku částečně setříděnou posloupnost. (Uvažujme vzestupné 
třídění.) (+++)  

Na začiatok zvolíme vhodný gap (h - velikost gapu), v tomto prípade vyhovuje 4.  To znamená prvok s indexom 0 

porovnávame s prvkom s indexom 4, index 1 s 5, 2 s 6 atď.. V prvom kroku porovnáme čísla 7 a 2’, swap -> (2’,1,2,8,7,4,5,3). 
Porovnáme 1 a 4, sú zoradené, nerobíme nič. Porovnáme 2 a 5, opäť v poriadku, porovnáme 8 a 3, swap -> po prvom 
prechode je postupnosť 2’,1,2,3,7,4,5,8. Prešli sme celé pole, zmenšíme gap na 1 a zoradíme insert sortom. Teda 2’ nič, 1 a 
2’ swap,(1,2’,2,3,7,4,5,8),  2 nič,  3 nič, 7 nič,  4 a 7 swap (1,2’,2,3,4,7,5,8), 5 a 7 swap (1,2’,2,3,4,5,7,8),  8 nič, došli sme 
nakoniec, pole je zotriedené. //Fučela