Ilustracja przedstawia dłoń osoby składającej puzzle.
I_P_W14_M12_C++ Sortowanie przez wstawianie w języku C++
Ź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).
Polecenie 1
Zaobserwuj, jak działa sortowanie przez wstawianie na podstawie animacji
Przykład działania sortowania przez wstawianie
Źródło: Nuno Nogueira, licencja: CC BY-SA 2.5.
Ćwiczenie na rozgrzewkę
Ćwiczenie 1
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.
Wyznaczysz złożoność obliczeniową algorytmu sortowania przez wstawianie.