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.
//”poslední průchod je vždy klasické třídění přímým vkládáním”
//Osobně bych volil velikost gapu 2n–1 (Hibbardova posloupnost), tzn.: ..., 255, 127, 63, 31, 15, 7, 3, 1 (Stejsky) +1 //Takže první h = 3 a pak 1? //Ano.
//První (maximální) hodnota h je <= n/2 (n
je počet prvků)
2. Je dána např. posloupnost čísel: 1, 2, 8, 2, 4, 5, 3, 1. Popište konkrétně jednotlivé kroky rychlé třídění
výběrem (Quick Sort) a uveďte po každém kroku částečně setříděnou posloupnost. (Uvažujme vzestupné
třídění.) (+++)
1, 2, 8, 2, 4, 5, 3, 1 – urcime pivot a dame ho na konec (pivot je prostredni cislo, u sudeho poctu cisel konec první
pulky cisel) //není to vlastně úplně jedno jaké číslo se určí jako pivot jde tam jen určit všechny prvky vetší a menší
než je ten pivot
1, 2, 8, 1, 4, 5, 3, 2
1, 2, 8, 1, 4, 5, 3, 2 – najdeme cislo z leva které je rovno nebo vetsi nez pivot (2)
1, 2, 8, 1, 4, 5, 3, 2 - najdeme cislo z prava které je mensi nez pivot nebo dokud neprekrocime levou “zarazku”
1, 1, 8, 2, 4, 5, 3, 2 - prohodime je
1, 1, 8, 2, 4, 5, 3, 2 – najdeme cislo z leva které je rovno nebo vetsi nez pivot
1, 1, 8, 2, 4, 5, 3, 2 najdeme cislo z prava které je mensi nez pivot nebo dokud neprekrocime levou “zarazku”
Prekroceni nam říká ze vse doleva od zarazky je mensi nez pivot, tudiz je prohodime
1, 1, 2, 2, 4, 5, 3, 8 – vezmeme část před pivotem a urcime pro tutu část novy pote algoritmus provedeme znovu
1, 1, 2, 2, 4, 5, 3, 8 - vezmeme část za puvodnim pivotem a vse opakujeme
1, 1, 2, 2, 4, 8, 3, 5
1, 1, 2, 2, 4, 3, 8, 5 - zde zase prava zarazka dojde az do leva tudiz vime ze pivot je mensi nebo rovny zarazce