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.
Před: 7, 1, 2, 8, 2, 4, 5, 3, 1, 9
01.krok: 1, 2, 7, 2, 4, 5, 3, 1, 8, 9
02.krok: 1, 2, 2, 4, 5, 3, 1, 7, 8, 9 03.krok: 1, 2, 2, 4, 3, 1, 5, 7, 8, 9 04.krok: 1, 2, 2, 3, 1, 4, 5, 7, 8, 9 //tučně setříděná oblast 05.krok: 1, 2, 2, 1, 3, 4, 5, 7, 8, 9
06.krok: 1, 2, 1, 2, 3, 4, 5, 7, 8, 9
07.krok: 1, 1, 2, 2, 3, 4, 5, 7, 8, 9
//setříděno
08.krok: 1, 2, 1, 2, 3, 4, 5, 7, 8, 9
09.krok: 1, 2, 1, 2, 3, 4, 5, 7, 8, 9
10.krok: 1, 1, 2, 2, 3, 4, 5, 7, 8, 9
//8. A další kroky jsou zbytečné - to řeší modifikace, která zjišťuje, zda došlo během průchodu k výměně - pokud
ne -
> konec třídění (Stejsky)
2. Jaké základní operace s prvky pole jsou
využívány při třídění přímou výměnou (Bubble
Sort).
Která ze základních operací určuje výs blednou
míru složitosti a jaká je výsledná míra složitosti.
(++)
• Algoritmus je založen na operacích
SROVNÁVÁNÍ a VÝMĚNY DVOU PRVKŮ
• Obě operace mají KVADRATICKOU
složitost -> výsledná složitost je tedy
KVADRATICKÁ --> O(n^2)
3. Je dána např. posloupnost čísel: 2, 3, 4, 5, 7, 8,
9, 1. Popište konkrétně jednotlivé kroky třídění
modifikovanou metodou přímou výměnou
(Shaker Sort) a uveďte po každém kroku
částečně setříděnou posloupnost. (Uvažujme
vzestupné třídění.) (+++)
(Stejskal)
4. 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 výběrem (Select Sort) a uveďte po každém kroku částečně setříděnou posloupnost. (Uvažujme
vzestupné třídění.) (+++)
Selection sort vychádza z myšlienky, že keď radíme pole vzostupne, prvý prvok bude najmenší, za ním bude