Kartičky na Bublinkové řazení (bubble sort)
Bublinkové řazení (Bubble Sort): Průvodce pro studenty
Klepni pro otočení · Swipni pro navigaci
Bublinkové řazení
21 kartiček
Kartička 1
Otázka: Jaká je funkce optimalizace pro předčasné ukončení u bublinkového řazení?
Odpověď: Pokud v průchodu nedojde k žádné výměně, znamená to, že seznam je již seřazen, a algoritmus se může ukončit, čímž se zlepší výkon v nejlepším případě.
Kartička 2
Otázka: Co je to časová složitost algoritmu?
Odpověď: Popisuje, jak se doba běhu algoritmu mění s velikostí vstupu `n`.
Kartička 3
Otázka: Jaká je časová složitost bublinkového řazení v nejhorším případě a kdy k němu dochází?
Odpověď: O(n²). Nastává, když je seznam seřazen v opačném pořadí.
Kartička 4
Otázka: Proč je časová složitost bublinkového řazení v nejhorším případě O(n²)?
Odpověď: Algoritmus provede přibližně n(n-1)/2 porovnání, což je zhruba n²/2, tedy O(n²).
Kartička 5
Otázka: Jaká je časová složitost bublinkového řazení v průměrném případě?
Odpověď: O(n²).
Kartička 6
Otázka: Jaká je časová složitost bublinkového řazení v nejlepším případě a kdy k němu dochází?
Odpověď: O(n). Nastává, když je seznam již seřazen a je použita optimalizace pro předčasné ukončení.
Kartička 7
Otázka: Proč je časová složitost bublinkového řazení v nejlepším případě O(n)?
Odpověď: S optimalizací algoritmus provede pouze jeden průchod s n-1 porovnáními a ukončí se, což je lineární složitost.
Kartička 8
Otázka: Jaká je prostorová složitost bublinkového řazení a co to znamená?
Odpověď: O(1). Je to tzv. řazení na místě (in-place sorting), nepotřebuje dodatečnou paměť s rostoucí velikostí vstupu.
Kartička 9
Otázka: Jaká je první optimalizace v pseudokódu bublinkového řazení?
Odpověď: Pokud nedojde k žádné výměně (`vymeneno = NEPRAVDA`), algoritmus se ukončí (`dokud vymeneno je PRAVDA`).
Kartička 10
Otázka: Jaká je druhá optimalizace v pseudokódu bublinkového řazení?
Odpověď: Zkracování rozsahu vnitřního cyklu (`n = n - 1`), protože poslední prvek je již na svém místě.