Czego się nauczysz
Nauczysz się sortować listę tak, jak układasz karty w ręce: każdą kolejną liczbę wsuwasz między już ułożone. Policzysz przesunięcia, zobaczysz, dlaczego dla danych prawie posortowanych to najszybsza z prostych metod, i znajdziesz miejsce dla liczby wyszukiwaniem binarnym.
Po co ci to na maturze
Sortowanie przez wstawianie, także w wersji z wyszukiwaniem binarnym, jest w podstawie programowej i pojawia się w zadaniach na analizę algorytmu. Warto wiedzieć, dla jakich danych działa najszybciej.
Etapy lekcji
Spis lekcji
Teoria
5 rozdziałówNie zaczęte- 1.1Jak układanie kart w ręceLewa część listy jest zawsze posortowana, a kolejny element wsuwa się w nią na swoje miejsce.
- 1.2Przesuwanie zamiast zamianKlucz czeka z boku, a większe elementy kolejno przesuwają się o jedno miejsce w prawo.
- 1.3Kiedy szybko, a kiedy wolnoPrzesunięć jest tyle, ile par w złej kolejności: zero dla listy posortowanej, n · (n - 1) / 2 dla odwrotnej.
- 1.4Miejsce znalezione binarnieLewa część jest posortowana, więc miejsce dla klucza można znaleźć połowieniem.
- 1.5PodsumowanieNajważniejsze rzeczy z każdego rozdziału na jednej stronie, do szybkiej powtórki.