Kartičky na Rýchle triedenie (quicksort)
Rýchle triedenie (Quicksort): Podrobný rozbor pre študentov
Ťukni na otočenie · Potiahni na navigáciu
Algoritmus rýchleho triedenia (Quicksort)
18 kartičiek
Kartička 1
Otázka: Kto vyvinul algoritmus rýchleho triedenia Quicksort a kedy?
Odpoveď: Britský informatik T. A. R. Hoare v roku 1959, publikovaný v roku 1961.
Kartička 2
Otázka: Akú stratégiu využíva Quicksort?
Odpoveď: Stratégiu „rozdeľ a panuj“ (divide and conquer).
Kartička 3
Otázka: Čo znamená, že Quicksort patrí medzi porovnávacie triediace algoritmy?
Odpoveď: Znamená to, že triedi prvky porovnávaním ich hodnôt.
Kartička 4
Otázka: Aké sú hlavné výhody Quicksortu?
Odpoveď: Vysoká rýchlosť v priemernom prípade a relatívne jednoduchá implementácia, ktorá nevyžaduje dodatočnú pamäť (in-place).
Kartička 5
Otázka: Aké sú tri základné kroky princípu „Rozdeľ a panuj“ v Quicksorte?
Odpoveď: Rozdeľ (Divide), Panuj (Conquer), Spoj (Combine).
Kartička 6
Otázka: Popíš krok „Rozdeľ“ v Quicksorte.
Odpoveď: Vyberie sa pivot, pole sa rozdelí na dve podpolia (menšie ako pivot, väčšie ako pivot). Pivot sa umiestni na konečnú pozíciu.
Kartička 7
Otázka: Popíš krok „Panuj“ v Quicksorte.
Odpoveď: Rekurzívne sa aplikuje rýchle triedenie na podpolia.
Kartička 8
Otázka: Popíš krok „Spoj“ v Quicksorte.
Odpoveď: Tento krok je triviálny, pretože podpolia sú už utriedené a pivot je na správnej pozícii, čo vedie k utriedeniu celého poľa.
Kartička 9
Otázka: Čo má zásadný vplyv na výkon algoritmu Quicksort?
Odpoveď: Výber pivota.
Kartička 10
Otázka: Vymenuj aspoň tri bežné stratégie výberu pivota v Quicksorte.
Odpoveď: Prvý alebo posledný prvok, stredný prvok, náhodný prvok, medián z troch.