Sortowanie przez wstawianie i przez scalanie

Ten materiał uzupełnia algorytmy sortowania o dwie metody, które podstawa programowa informatyki wymienia wprost: porządkowanie ciągu przez wstawianie (zakres podstawowy) i sortowanie przez scalanie (zakres rozszerzony, jako przykład metody „dziel i zwyciężaj”). Na maturze takie algorytmy pojawiają się zwykle w zadaniach z analizą gotowego kodu: trzeba przewidzieć stan tablicy po kilku krokach, policzyć operacje albo ocenić złożoność.

W sortowaniu przez wstawianie śledzisz, jak rośnie posortowany początek tablicy: kolejny element jest przesuwany w lewo, dopóki stoi przed nim element większy. Ćwiczysz to na konkretnych tablicach — także w krokach, w których nic się nie przesuwa — i na krótkim programie w Pythonie, który wypisuje tablicę po każdym obrocie pętli. Liczysz przesunięcia dla tablicy odwrotnie posortowanej, porównujesz przypadek optymistyczny (tablica już posortowana, $n-1$ porównań, czas liniowy) z pesymistycznym ($\frac{n(n-1)}{2}$ porównań, czas kwadratowy) i sprawdzasz, co daje wyszukiwanie miejsca wstawienia metodą połowienia: mniej porównań, ale wciąż tyle samo przesunięć.

W sortowaniu przez scalanie poznajesz trzy etapy: podział na połowy, rekurencyjne posortowanie każdej połowy i scalenie dwóch posortowanych ciągów. Scalasz ciągi ręcznie, licząc porównania, wyznaczasz liczbę poziomów podziału dla $n=16$ i wyjaśniasz, skąd bierze się złożoność $O(n\log n)$ w każdym przypadku oraz dodatkowa pamięć $O(n)$. Sprawdzasz też, dlaczego oba algorytmy mogą być stabilne i od czego to zależy przy scalaniu.

Na koniec porównujesz oba algorytmy: kiedy prosty algorytm kwadratowy wygrywa (małe lub prawie posortowane dane), a kiedy potrzebna jest gwarancja $O(n\log n)$.

Materiał oferuje cztery formy pracy. Quiz zawiera zadania ze śledzenia algorytmów i pytania o złożoność, z wyjaśnieniem kolejnych kroków. Fiszki utrwalają zasady działania, złożoności i pojęcie stabilności. Egzamin ustny w formie rozmowy z egzaminatorem sprawdza, czy umiesz opisać algorytm i uzasadnić jego własności. Praca pisemna do wydruku zawiera zadania otwarte: ręczne śledzenie, liczenie operacji i zapis algorytmu w pseudokodzie lub w wybranym języku programowania.

Wszystkie zadania są oryginalnymi ćwiczeniami do samodzielnej nauki, a wyniki programów zostały sprawdzone przez ich uruchomienie.

• Śledzisz kolejne kroki sortowania przez wstawianie i przewidujesz wydruk programu.
• Liczysz porównania i przesunięcia w przypadkach optymistycznym i pesymistycznym.
• Scalasz dwa posortowane ciągi i liczysz potrzebne porównania.
• Wyjaśniasz zasadę „dziel i zwyciężaj” i złożoność O(n log n) sortowania przez scalanie.
• Dobierasz algorytm sortowania do rodzaju danych i oceniasz jego stabilność.

Materiał ćwiczeniowy przygotowany przez Zestly.