Czego się nauczysz
Nauczysz się sortować listę, wybierając w każdym przebiegu najmniejszą z pozostałych liczb i stawiając ją jedną zamianą na swoim miejscu. Porównasz to z sortowaniem bąbelkowym i zobaczysz, kiedy wybieranie się opłaca.
Po co ci to na maturze
Zadania na analizę lubią porównywać sortowanie przez wybieranie z innymi: ile zamian, ile porównań, jak wygląda lista po trzech przebiegach. Ten sam pomysł znajduje kilka najmniejszych liczb bez sortowania całej listy.
Etapy lekcji
Spis lekcji
Teoria
5 rozdziałówNie zaczęte- 1.1Wybierz najmniejszyPrzebieg szuka najmniejszej z pozostałych liczb i jedną zamianą stawia ją na pierwszym wolnym miejscu.
- 1.2Część posortowana rośnie z lewejPrzebieg numer i szuka minimum tylko w części t[i:] i stawia je na pozycji i.
- 1.3Porównania zawsze, zamiany rzadkoPorównań jest zawsze n · (n - 1) / 2, a zamian najwyżej n - 1.
- 1.4Wybieranie nie jest stabilneDaleka zamiana potrafi przerzucić element za inny o tej samej wartości.
- 1.5PodsumowanieNajważniejsze rzeczy z każdego rozdziału na jednej stronie, do szybkiej powtórki.