Złożoność czasowa
Zasób interaktywny dostępny pod adresem https://zpe.gov.pl/a/DAN4TJELK
Symulacja przedstawia pasek przewijania podpisany jako Liczba elementów.
Pasek ustawiono na n=5.
Obok paska znajdują się przyciski Reset oraz Kolejny krok.
W prawym górnym rogu znajdują się przyciski: Załaduj przypadek optymistyczny oraz Załaduj przypadek pesymistyczny.
Poniżej znajduje się pięć słupków.
Przykład 1:
Po kliknięciu przycisku Załaduj przypadek optymistyczny, poniżej pojawiło się pięć słupków o wartościach: 1, 2, 3, 4, 5.
Słupek 2 zaznaczony jest czerwonym kolorem.
Po kliknięciu przycisku kolejny krok, słupek 3 zaznaczono kolorem czerwonym.
Po kliknięciu przycisku kolejny krok, słupek 4 zaznaczono kolorem czerwonym.
Po kliknięciu przycisku kolejny krok, słupek 5 zaznaczono kolorem czerwonym.
Po kliknięciu przycisku kolejny krok, czerwone oznaczenie zniknęło.
Żaden ze słupków nie zmienił pozycji.
Liczba porównań: 4.
Liczba przesunięć: 0.
Przykład 1:
Po kliknięciu przycisku Załaduj przypadek pesymistyczny, poniżej pojawiło się pięć słupków o wartościach: 100, 99, 98, 97, 96.
Słupek 99 zaznaczony jest czerwonym kolorem.
Po kliknięciu przycisku kolejny krok, słupek 98 zaznaczono kolorem czerwonym.
Kolejność słupków: 99, 100, 98, 97, 96.
Po kliknięciu przycisku kolejny krok, słupek 97 zaznaczono kolorem czerwonym.
Kolejność słupków: 98, 99, 100, 97, 96.
Po kliknięciu przycisku kolejny krok, słupek 96 zaznaczono kolorem czerwonym.
Kolejność słupków: 97, 98, 99, 100, 96.
Po kliknięciu przycisku kolejny krok, czerwone oznaczenie zniknęło.
Kolejność słupków: 96, 97, 98, 99, 100.
Liczba porównań: 14.
Liczba przesunięć: 10.
Złożoność czasowa
Algorytm sortowania przez wstawianie ma następujące złożoności:
Przypadek pesymistycznyPrzypadek pesymistyczny – jest to przypadek, gdy dane wejściowe są posortowane w odwrotnej kolejności niż mamy je posortować.
Wynika to stąd, że w trakcie sortowania tablicy warunek tab[j]>pom jest sprawdzany razy w każdym obiegu pętli, ponieważ liczby są ułożone w odwrotnej kolejności niż mamy zamiar je posortować. Złożoność obliczeniowa w takim wypadku jest kwadratowa.
Przypadek typowy – przypadek, w którym dane występują w losowym porządku.
Wynika to stąd, iż jeśli założymy, że wszystkie wartości tablicy występują z takim samym prawdopodobieństwem, to oczekiwana liczba elementów, które są mniejsze od danego klucza, wynosi .
Przypadek optymistyczny – przypadek, gdy dane są już posortowane.
Wynika to stąd, że pętla wewnętrzna nie jest wykonywana ani razu, gdyż warunek tab[j]>pom nigdy nie jest spełniony, ponieważ każda kolejna liczba jest większa od poprzedniej. Zatem dla każdej liczby warunki są sprawdzane jednokrotnie. Złożoność obliczeniowa w takim przypadku jest liniowa.