Czego się nauczysz
Nauczysz się sortowania, które dzieli listę wokół jednego elementu, i zobaczysz, dlaczego zwykle jest szybkie, a dla danych już posortowanych potrafi być tak wolne jak bąbelkowe.
Po co ci to na maturze
Sortowanie szybkie też jest w podstawie programowej, a zadania pytają o podział listy wokół wybranego elementu i o to, kiedy algorytm zwalnia. Pomysł podziału pozwala też znaleźć k-tą najmniejszą liczbę bez sortowania.
Etapy lekcji
Spis lekcji
Teoria
4 rozdziałyNie zaczęte- 1.1Jeden element na swoim miejscuMniejsze na lewo, większe na prawo, a element rozdzielający stoi już tam, gdzie trzeba.
- 1.2Kiedy szybkie, kiedy wolneRówny podział daje n · log n. Pivot zawsze na skraju daje n · (n - 1) / 2.
- 1.3Podział w tej samej liścieGranica i oddziela mniejsze od reszty. Bez nowych list, tylko zamiany.
- 1.4PodsumowanieNajważniejsze rzeczy z każdego rozdziału na jednej stronie, do szybkiej powtórki.