Czego się nauczysz
Nauczysz się scalać dwie posortowane listy i zbudujesz z tego sortowanie, które dla miliona liczb robi kilkadziesiąt tysięcy razy mniej porównań niż bąbelkowe.
Po co ci to na maturze
Sortowanie przez scalanie jest w podstawie programowej i pojawia się w zadaniach na analizę: jak wygląda lista po scaleniu, ile wykona porównań. Sam pomysł scalania przydaje się też przy łączeniu dwóch uporządkowanych plików.
Etapy lekcji
Spis lekcji
Teoria
4 rozdziałyNie zaczęte- 1.1Scalanie dwóch posortowanych listZawsze bierzesz mniejszy z dwóch pierwszych elementów. Każdy element ogląda się raz.
- 1.2Dziel na pół, scalaj w góręLista z jednym elementem jest posortowana. Z takich klocków scalanie buduje całość.
- 1.3Dlaczego n · log nNa każdym poziomie scalanie dotyka każdego elementu raz, a poziomów jest log₂ n.
- 1.4PodsumowanieNajważniejsze rzeczy z każdego rozdziału na jednej stronie, do szybkiej powtórki.