Ilustracja przedstawia dłoń osoby składającej puzzle.
I_P_W14_M12 Sortowanie przez wstawianie
Źródło: Delaney Van, domena publiczna.
Sortowanie przez wstawianie jest jednym z najprostszych algorytmów sortujących. Zastosowanie tego algorytmu jest szczególnie przydatne w przypadku, gdy dane wejściowe są częściowo posortowane. Sortowanie przez wstawianie bywa wykorzystywane np. w czasie gry w brydża. Gracz bierze kolejno karty i każdą z nich wstawia w odpowiednie miejsce docelowe (w tym celu zestaw kart jest rozsuwany).
Przykład działania sortowania przez wstawianie
Źródło: Nuno Nogueira, licencja: CC BY-SA 2.5.
Ćwiczenie na rozgrzewkę:
Twoje cele
Przeanalizujesz, jak działa metoda sortowania przez wstawianie.
Prześledzisz krok po kroku, jak działa algorytm sortowania przez wstawianie dla konkretnego przykładu.
Zaimplementujesz algorytm sortowania przez wstawianie w języku Python.
Wyznaczysz złożoność obliczeniową algorytmu sortowania przez wstawianie.