BPC-ALD_Zpracované_otazky_ke_zkousce

zoradená časť obsahuje 1. prvok a nezoradená zvyšné prvky 

2.  Z nezoradenej časti vytiahneme prvý prvok zľava, a 

porovnávame ho so zoradenou časťou kým nenájdeme správnu 
pozíciu prvku, vložíme ju na správnu pozíciu a prvky zoradenej 
časti napravo od vloženého prvku posunieme o index doprava 

3.  Zoradenú časť zväčšíme o jeden prvok, nezoradenú časť 

zmenšíme o jeden prvok zprava 

4.  Opakujeme body 2-3 do úplneho zoradenia //fučela +1 

3.  Jaké základní operace s prvky pole jsou využívány při 

třídění přímým vkládáním (Insert 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 dvou základních operacích - 

SROVNÁVÁNÍ a PŘESUNU 

•  Operace SROVNÁVÁNÍ i operace PŘESUNU mají 

KVADRATICKOU míru složitosti -> výsledná složitost je 
tedy KVADRATICKÁ --> O(n^2) 

Přednáška 9: Třídění přímou výměnou, modifikace algoritmu, třídění přímým výběrem 
(Select Sort), odvození složitosti obou algoritmu (Ing. Tomáš Macho, Ph.D.) 

1.  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římou výměnou (Bubble Sort) a uveďte po každém kroku částečně setříděnou posloupnost. (Uvažujme 
vzestupné třídění.) (+++) 

//Strašně zdlouhavé a neustálé přepisování... Prostě je to podobné jako Shaker sort s tím rozdílem, že jednotlivé 
kroky probíhají pouze zleva doprava, a tím se dostávají největší hodnoty vpravo. Naopak malé hodnoty se 
každým krokem posunou pouze o jednu pozici vlevo. Setřízená oblast tedy bude růst zprava doleva, dokud 
neobsáhne všechny prvky. (Stejskal) 
//Jak psal Stejsky, je to strašně zdlouhavé (přes 57 kroků), mám to rozepsané, takže kdyby to někdo chtěl tak ať napíše a 
pošlu (Štípek) 
//Oprava: V každém kroku setřídíš alespoň jeden prvek, tudíž nemůžeš mít tolik kroků - to jsou jen rozkreslené mezikroky, co ty 
myslíš. K setřídění je tu potřeba 10 kroků (resp. 7, další jsou zbytečné). (Stejsky)   //pravda pravdouci