Test na Bublinkové řazení (bubble sort)

Otázka 1: Jednou z běžných chyb při implementaci bublinkového řazení je předpoklad, že optimalizace pro předčasné ukončení mění asymptotickou časovou složitost algoritmu v nejhorším případě.

A. Ano

B. Ne

Vysvětlení: Studijní materiály uvádějí, že "optimalizace pro předčasné ukončení... Ačkoli to nemění asymptotickou časovou složitost v nejhorším případě, výrazně to zlepšuje výkon pro částečně nebo zcela seřazené vstupní datové sady." Z toho vyplývá, že mylná představa, že by optimalizace měnila asymptotickou časovou složitost v nejhorším případě, je chybou.

Otázka 2: Pseudokód pro bublinkové řazení zahrnuje optimalizaci, která zmenšuje rozsah vnitřního cyklu v každém průchodu snížením hodnoty 'n' o jedničku.

A. Ano

B. Ne

Vysvětlení: Pseudokód v sekci 'Pseudokód' obsahuje řádek 'n = n - 1 // Optimalizace: poslední prvek je již na svém místě'. To znamená, že rozsah vnitřního cyklu (pro i od 0 do n - 2) se v každém dalším průchodu zkracuje, protože 'n' se snižuje o jedna, což odpovídá optimalizaci, kde se již seřazené prvky na konci seznamu znovu nekontrolují.

Otázka 3: Který z následujících popisů nejlépe vystihuje funkci vnitřního cyklu `for j in range(n - 1 - i)` v poskytnuté Python implementaci bublinkového řazení?

A. Zajišťuje, že vnitřní cyklus porovnává prvky v celém seznamu v každém průchodu.

B. Umožňuje optimalizaci algoritmu tím, že zmenšuje rozsah porovnávání v každém dalším průchodu, neboť poslední `i` prvků je již seřazeno.

C. Slouží k inicializaci příznaku `vymeneno` na `True` na začátku každého vnitřního průchodu.

D. Je zodpovědný za kontrolu, zda je seznam již seřazen, a ukončuje algoritmus, pokud nedošlo k žádné výměně.

Vysvětlení: Vnitřní cyklus `for j in range(n - 1 - i)` v Python implementaci je klíčový pro optimalizaci. Text uvádí: 'Posledních i prvků je již na svém místě, takže je nemusíme kontrolovat'. To znamená, že v každém dalším průchodu (řízeném proměnnou `i` ve vnějším cyklu) se zmenšuje rozsah, ve kterém se provádí porovnávání a případné prohazování prvků. Tím se zabraňuje zbytečným operacím s již seřazenými prvky na konci seznamu.

Otázka 4: Mějme neseřazený seznam o délce 'n'. Které tvrzení správně popisuje mechanismus průchodů při bublinkovém řazení bez optimalizace, konkrétně po dokončení 'i'-tého průchodu (kde 'i' je index průchodu začínající od 0)?

A. Po každém 'i'-tém průchodu je prvních 'i' prvků seznamu seřazeno a na svých správných pozicích.

B. V každém 'i'-tém průchodu se porovnávají a případně prohazují prvky od začátku seznamu až po '(n-1-i)' -tý prvek, protože posledních 'i' prvků je již seřazeno.

C. Po dokončení 'i'-tého průchodu se vnitřní cyklus zkrátí o 'i' pozic, protože 'i' největších prvků je již umístěno na konec seznamu.

D. Bublinkové řazení vždy provede 'n-1' průchodů, bez ohledu na to, zda je seznam již seřazen.

Vysvětlení: Podle studijních materiálů bublinkové řazení provádí 'n-1' průchodů v nejhorším případě, a v každém 'i'-tém průchodu se porovnávají a případně prohazují prvky od začátku seznamu až po '(n-1-i)'-tý prvek. Je to z důvodu, že po 'i' průchodech je posledních 'i' prvků seznamu již seřazeno a na svých správných pozicích, a proto je není třeba znovu kontrolovat. Tvrzení o 'n-1' průchodech je pravdivé pro základní implementaci bez optimalizace, nebo v nejhorším případě. Optimalizace pro předčasné ukončení by umožnila dřívější ukončení, ale otázka se ptá na mechanismus průchodů obecně, a 'n-1' průchodů je horní hranice a běžné chování bez optimalizace. Možnost A je nesprávná, protože bublinkové řazení 'bublá' největší prvky na konec, ne nejmenší na začátek.

Otázka 5: Interaktivní simulace bublinkového řazení vizuálně demonstruje, jak se větší prvky posouvají doprava během každého průchodu.

A. Ano

B. Ne

Vysvětlení: Simulace bublinkového řazení názorně ukazuje, jak se prvky porovnávají a kdy dochází k jejich výměně, přičemž větší prvky se postupně posouvají doprava v každém průchodu, což pomáhá pochopit princip algoritmu.