Na czym polega metoda sortowania przez wstawianie?

Metodę sortowania przez wstawianie często porównuje się z układaniem kart w ręku gracza. Podnosi on kolejno karty ze stołu na rękę, każdą kolejną kartę wstawiając w odpowiednie miejsce. W każdym momencie karty na ręce są posortowane, a karty na stole – nie. My prześledzimy działanie algorytmu na przykładzie sortowania liczb.

Sortowany ciąg dzielony jest na część posortowaną i nieposortowaną. Na początku w części posortowanej znajduje się tylko jeden element (pierwszy). W każdym kolejnym kroku bierzemy pierwszy element z części nieposortowanej i wstawiamy we właściwe miejsce części posortowanej. Aby to zrobić, wstawiany element porównujemy kolejno z ostatnim elementem posortowanej części ciągu, z przedostatnim itd. Algorytm kończy się, gdy wszystkie elementy znajdują się w części posortowanej.

Zapis za pomocą pseudokodu

dla i = 2,3,4....n wykonuj
	pom = tab[i]
	j = i-1
	dopóki j >= 1 oraz tab[j] > pom wykonuj
		tab[j + 1] = tab[j]
		j = j - 1
	tab[j + 1] = pom

Wyjaśnijmy krok po kroku, jak działa algorytm.

Krok 1

Stwórzmy pętlę, która wykona się o jeden raz mniej, niż liczba elementów do posortowania. O jeden mniej, ponieważ tablica jednoelementowa jest tablicą posortowaną. Zatem początkowa wartość zmiennej i = 2. Pętla wykonuje się, dopóki nie zostaną wstawione wszystkie elementy tablicy.

Krok 2

Wewnątrz pętli stworzonej w kroku 1 ustawmy wartość zmiennej pomocniczej pom na wartość elementu tablicy o indeksie i. W tej zmiennej przechowujemy aktualnie wstawiany element. Miejsce w tablicy pod indeksem i możemy traktować jako puste.

Krok 3

Ustawmy wartość zmiennej j na wartość równą i - 1. W zmiennej j będziemy przechowywać indeks elementu, który obecnie porównujemy z elementem zawartym w zmiennej pom, który mamy wstawić we właściwe miejsce.

Krok 4

Stwórzmy pętlę wewnętrzną, która będzie się wykonywała, dopóki spełnione będą dwa warunki:

• zmienna j będzie miała wartość większą bądź równą 1 (jeśli wartość zmiennej j będzie równa zeru, oznacza to, że każda liczba w posortowanej części tablicy została porównana z wartością zmiennej pom i była od niej mniejsza, czyli dotarliśmy na początek tablicy);

• wartość w tablicy zapisana pod indeksem j jest większa od zmiennej pomocniczej pom.

Krok 5

Jeżeli powyższe warunki zostały spełnione, wchodzimy do pętli. Wykonujemy podstawienie w miejsce elementu zapisanego pod indeksem j + 1, który możemy traktować jako puste miejsce. W jego miejsce podstawiamy element zapisany pod indeksem j. Robimy to, by mieć możliwość zapisania wartości wstawianego elementu do części posortowanej, nie tracąc danych. Pętla jest wykonywana do momentu odnalezienia odpowiedniego miejsca w tablicy dla wstawianego elementu lub jeśli natrafimy na początek listy (kończymy gdy j = 0).

Zmniejszamy wartość zmiennej j o jeden i przechodzimy do sprawdzenia warunku pętli w kroku 4.

Krok 6

Ostatnią operacją wykonywaną w zewnętrznej pętli jest podstawienie w miejsce zmiennej zapisanej pod indeksem j + 1 wartości zmiennej pomocniczej pom. Poprzez wykonanie tego kroku wstawiamy obecnie sprawdzaną liczbę na swoje miejsce.

Przykład

Skoro już wiemy, jak działa algorytm sortowania przez wstawianie, prześledźmy przykładowe sortowanie. Posortujmy rosnąco tablicę złożoną z 5 elementów.

Tablica do posortowania wygląda następująco: {5, 8, 9, 7, 3}.

Krok 1

Podzielmy tablicę na część posortowaną oraz nieposortowaną. Tablica jednoelementowa jest tablicą posortowaną, zatem początkowo dzielimy tablicę na części:  5 | 8 9 7 3.

Krok 2

Zaczynamy pętlę z wartością początkową zmiennej pomocniczej i = 2. Ustawiamy wartość zmiennej pomocniczej pom na wartość tab[i]. Zatem pom = tab[2] = 8.

Krok 3

Ustawiamy wartość zmiennej pomocniczej j na wartość i - 1. Zatem j = 2 - 1 = 1.

Krok 4

Zaczynamy pętlę wewnętrzną. Sprawdzamy, czy warunki pętli są spełnione. W tym przypadku jest spełniony tylko jeden: j = 1, zatem spełniony jest warunek j >= 1. Jednak warunek tab[j] > pom jest niespełniony, ponieważ 5 nie jest większe od 8.

Krok 5

Przechodzimy do pierwszej instrukcji za pętlą, ponieważ instrukcje wewnętrzne pętli mogą zostać wykonane tylko wtedy, gdy oba warunki są spełnione. Ustawiamy wartość tab[j + 1] na wartość zmiennej pomocniczej pom. Zatem tab[2] = pom. Tablica wygląda teraz tak:  5 8 | 9 7 3.

Krok 6

Zwiększamy wartość zmiennej i o 1.

Krok 7

Zaczynamy pętlę z wartością zmiennej i = 3 Ustawiamy wartość zmiennej pomocniczej pom na wartość tab[i]. Zatem pom = tab[3] = 9.

Krok 8

Ustawiamy wartość zmiennej pomocniczej j na wartość i - 1. Zatem j = 3 - 1 = 2.

Krok 9

Zaczynamy pętlę. Sprawdzamy, czy warunki pętli są spełnione. W tym przypadku jest spełniony tylko jeden: j = 2, zatem spełniony jest warunek j >= 1. Jednak warunek tab[j] > pom jest niespełniony, ponieważ 8 nie jest większe od 9.

Krok 10

Pomijamy instrukcje wewnętrzne pętli, ponieważ instrukcje wewnętrzne pętli mogą zostać wykonane tylko wtedy, gdy oba warunki są spełnione. Ustawiamy wartość tab[j + 1] na wartość zmiennej pomocniczej pom. Zatem tab[3] = pom. Tablica wygląda teraz tak: 5 8 9 | 7 3.

Krok 11

Zwiększamy wartość zmiennej i o 1.

Krok 12

Zaczynamy pętlę z wartością zmiennej i = 4. Ustawiamy wartość zmiennej pomocniczej pom na wartość tab[i]. Zatem pom = tab[4] = 7.

Krok 13

Ustawiamy wartość zmiennej pomocniczej j na wartość i - 1. Zatem j = 4 - 1 = 3.

Krok 14

Zaczynamy pętlę. Sprawdzamy, czy warunki pętli są spełnione. W tym przypadku spełnione są oba warunki, ponieważ j = 3, więc warunek j >= 1 jest spełniony. Oraz tab[j] = tab[3] = 9, zatem tab[3] > 7.

Krok 15

Rozpoczynamy pętlę wewnętrzną. W miejsce zmiennej zapisanej pod indeksem j + 1 zapisujemy zmienną zapisaną pod indeksem j. Zatem tablica wygląda następująco: 5 8 9 | 9 3.

Krok 16

Zmniejszamy wartość zmiennej j o 1.

Krok 17

Sprawdzamy warunki pętli, czy mamy wykonać jeszcze jeden obieg. W tym przypadku tak jest, ponieważ j = 2, zatem j >= 1 oraz tab[j] = 8, a 8 > 7.

Krok 18

Rozpoczynamy pętlę. W miejsce zmiennej zapisanej pod indeksem j + 1 zapisujemy zmienną zapisaną pod indeksem j. Zatem tablica wygląda następująco: 5 8 8 | 9 3.

Krok 19

Zmniejszamy wartość zmiennej j o 1.

Krok 20

Wykonujemy instrukcje zawarte w pętli dopóki jej warunki są spełnione. W tym przypadku tak nie jest, ponieważ j = 1, zatem j >= 1 oraz tab[1] = 5, a to nie prawda, że 5 > 7, zatem wychodzimy z pętli.

Krok 21

W miejsce zmiennej zapisanej pod indeksem j + 1 zapisujemy wartość zmiennej pomocniczej pom. Zatem tablica wygląda następująco: 5 7 8 9 | 3.

Krok 22

Zwiększamy wartość zmiennej i o 1.

Krok 23

Zaczynamy pętlę z wartością zmiennej i = 5 Ustawiamy wartość zmiennej pomocniczej pom na wartość tab[i]. Zatem pom = tab[5] = 3.

Krok 24

Ustawiamy wartość zmiennej pomocniczej j na wartość i - 1. Zatem j = 5 - 1 = 4.

Krok 25

Zaczynamy pętlę. Sprawdzamy, czy warunki pętli są spełnione. W tym przypadku spełnione są oba warunki, ponieważ j = 4, więc warunek j >= 1 jest spełniony. Oraz tab[j] = 9, a 9 > 3.

Krok 26

Rozpoczynamy pętlę. W miejsce zmiennej zapisanej pod indeksem j + 1 zapisujemy zmienną zapisaną pod indeksem j. Zatem tablica wygląda następująco:  5 7 8 9 | 9.

Krok 27

Zmniejszamy wartość zmiennej j o 1.

Krok 28

Sprawdzamy warunki pętli, czy mamy wykonać jeszcze jeden obieg. W tym przypadku tak jest, ponieważ j = 3, zatem j >= 1 oraz tab[j] = 8, a 8 > 3.

Krok 29

Rozpoczynamy pętlę. W miejsce zmiennej zapisanej pod indeksem j + 1 zapisujemy zmienną zapisaną pod indeksem j. Zatem tablica wygląda następująco: 5 7 8 8 | 9.

Krok 30

Zmniejszamy wartość zmiennej j o 1.

Krok 31

Sprawdzamy warunki pętli, czy mamy wykonać jeszcze jeden obieg. W tym przypadku tak jest, ponieważ j = 2, zatem j >= 1 oraz tab[j] = 7, a 7 > 3.

Krok 32

Rozpoczynamy pętlę. W miejsce zmiennej zapisanej pod indeksem j + 1 zapisujemy zmienną zapisaną pod indeksem j. Zatem tablica wygląda następująco: 5 7 7 8 | 9.

Krok 33

Zmniejszamy wartość zmiennej j o 1.

Krok 34

Sprawdzamy warunki pętli, czy mamy wykonać jeszcze jeden obieg. W tym przypadku tak jest, ponieważ j = 1, zatem j >= 1 oraz tab[j] = 5, a 5 > 3.

Krok 35

Rozpoczynamy pętlę. W miejsce zmiennej zapisanej pod indeksem j + 1 zapisujemy zmienną zapisaną pod indeksem j. Zatem tablica wygląda następująco: 5 5 7 8 | 9.

Krok 36

Zmniejszamy wartość zmiennej j o 1.

Krok 37

Sprawdzamy warunki pętli, czy mamy wykonać jeszcze jeden obieg. W tym przypadku tak nie jest, ponieważ j = 0, a to nie prawda, że j >= 1. Wychodzimy z pętli.

Krok 38

W miejsce zmiennej zapisanej pod indeksem j + 1 zapisujemy wartość zmiennej pomocniczej pom. Zatem tablica wygląda następująco: 3 5 7 8 9|.

Koniec algorytmu.

Złożoność czasowa

Algorytm sortowania przez wstawianie ma następujące złożoności:

1. Przypadek pesymistycznyprzypadek 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 $i - 1$ 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.

2. 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 $i/2$.

3. 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.

Słownik