I_P_R_W14_M13_Java Sortowanie przez wstawianie
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).
Ćwiczenie na rozgrzewkę:
Uzupełnij algorytm sortowania przez wstawianie, tak aby poprawnie sortował ciąg liczb całkowitych podanych w tablicy zawartej w programie w kolejności nierosnącej. Wypisz posortowaną tablicę, oddzielając jej elementy znakiem spacji.
Swoje rozwiązanie przetestuj na tablicy tab = {27, 26, 4, 5, 24, 23, 15, 12, 1, 0, 9, 84}.
Specyfikacja problemu:
Dane:
n– liczba naturalnatab– tablicanliczb całkowitych
Wynik:
tab– posortowana nierosnąco tablicanliczb całkowitych
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.
Zapoznasz się z implementacją algorytmu sortowania przez wstawianie.
Przeanalizujesz, ile porównań wykonywanych jest w przypadku pesymistycznym, a ile w optymistycznym.
Napiszesz program, który do porządkowania danych wykorzysta algorytm sortowania przez wstawianie.