Sortowanie przez wstawianie

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
Sortowanie przez wstawianie
Insertion sort animation.gif
Przykład działania sortowania przez wstawianie.
Rodzaj Sortowanie
Struktura danych Tablica, lista
Złożoność
Czasowa O(n2)

Sortowanie przez wstawianie (ang. Insert Sort, Insertion Sort) - jeden z najprostszych algorytmów sortowania, którego zasada działania odzwierciedla sposób w jaki ludzie ustawiają karty - kolejne elementy wejściowe są ustawiane na odpowiednie miejsca docelowe[1]. Jest efektywny dla niewielkiej liczby elementów, jego złożoność wynosi O(n2)[1]. Pomimo tego, że jest znacznie mniej wydajny od algorytmów takich jak quicksort czy heapsort, posiada pewne zalety:

  • jest wydajny dla danych wstępnie posortowanych[potrzebne źródło]
  • jest wydajny dla zbiorów o niewielkiej liczebności[1]
  • jest stabilny[1]

Schemat działania algorytmu [1][edytuj | edytuj kod]

Przykład działania
  1. Utwórz zbiór elementów posortowanych i przenieś do niego dowolny element ze zbioru nieposortowanego.
  2. Weź dowolny element ze zbioru nieposortowanego.
  3. Wyciągnięty element porównuj z kolejnymi elementami zbioru posortowanego póki nie napotkasz elementu równego lub elementu większego (jeśli chcemy otrzymać ciąg niemalejący) lub nie znajdziemy się na początku/końcu zbioru uporządkowanego.
  4. Wyciągnięty element wstaw w miejsce gdzie skończyłeś porównywać.
  5. Jeśli zbiór elementów nieuporządkowanych jest niepusty wróć do punkt 2.

Algorytm - pseudokod[edytuj | edytuj kod]

Poniższy kod przedstawia algorytm zapisany w pseudokodzie, gdzie[2]:

  • A - tablica danych, przeznaczonych do posortowania (indeksowana od 1 do n)
  • n - liczba elementów w tablicy A
 
0. Insert_sort(A, n)                     
1.    for i=2 to n :                                     
2.       klucz = A[i]
3        > Wstaw A[i] w posortowany ciąg A[1 ... i-1]                
4.       j = i - 1                                       
5.       while j>0 and A[j]>klucz:                       
6.          A[j + 1] = A[j]              
7.          j = j - 1                    
8.       A[j+1] = klucz

Analiza algorytmu [potrzebne źródło][edytuj | edytuj kod]

Złożoność[edytuj | edytuj kod]

Niech δ(i) oznacza liczba sprawdzeń warunku pętli (4.) w i-tym przebiegu pętli (1.). Wtedy:

  • instrukcja 1. jest wykonana n razy
  • instrukcja 2. jest wykonana n-1 razy
  • instrukcja 3. jest wykonana n-1 razy (komentarz oznaczony przez >)
  • instrukcja 4. jest wykonana n-1 razy
  • instrukcja 5. jest wykonana \sum_{i = 2}^{n}  \delta (i) razy
  • instrukcja 6. jest wykonana \sum_{i = 2}^{n}  \delta (i) - 1 razy
  • instrukcja 7. jest wykonana \sum_{i = 2}^{n}  \delta (i) - 1 razy
  • instrukcja 8. jest wykonana n-1 razy

Jeżeli przez c1, c2, ..., c8 oznaczymy czas pojedynczego wywołania instrukcji 1,2, ... 8, to całkowity czas wykonania algorytmu sortowania przez wstawianie będzie równy:

T(n) = c1n + (c2+c3+c4+c8)(n-1) + \sum_{i = 2}^{n}  \delta (i) c5 + (\sum_{i = 2}^{n}  \delta (i) - 1)c6 + (\sum_{i = 2}^{n}  \delta (i) - 1)c7

Przypadek optymistyczny[edytuj | edytuj kod]

Gdy tablica danych wejściowych jest uporządkowana rosnąco, to w każdym przebiegu pętli (1.) przy pierwszym sprawdzeniu warunków pętli (5.) zachodzi A[j]<klucz - pętla (5.) nie zostaje wykonana ani razu, a więc liczba sprawdzeń warunku pętli (5.) δ(i) wynosi 1 dla wszystkich j od 1 do n. Całkowity czas T(n) = (c1 + c2 + c4 + c5 + c8)n - (c2 + c4 + c5 + c8) wykonania algorytmu jest więc wyrażony funkcją liniową, z czego wynika, że dla posortowanych tablic o długości n algorytm insert sort działa w czasie O(n).

Przypadek pesymistyczny[edytuj | edytuj kod]

Gdy tablica danych wejściowych jest uporządkowana malejąco, w każdym przebiegu pętli (1.) przy sprawdzaniu warunków pętli (5.) zachodzi A[j]>klucz - pętla (5.) w każdym i-tym przebiegu pętli (1.) jest wywoływana i-1 razy. Po podstawieniu do wzoru na T(n): δ(i) = i, otrzymuje się kwadratową złożoność czasową T(n) \in O(n2).

Przypadek średni[edytuj | edytuj kod]

Przy założeniu, że wszystkie możliwe wartości tablicy A występują z jednakowym prawdopodobieństwem, można dowieść, że oczekiwana liczba elementów A[1..i] większych od wstawianego klucza wynosi i/2. W tym wypadku podstawienie δ(i) = i/2 daje podobnie jak w przypadku pesymistycznym złożoność T(n) \in O(n2).

Poprawność[edytuj | edytuj kod]

Prawidłowość algorytmu sortowania przez wstawianie można dowieść, udowodniając poniższe twierdzenie:

w i-tym wykonaniu pętli for tablica A[1..i-1] składa się z posortowanych elementów znajdujących się w pierwotnej tablicy na pozycjach [1..i-1].

Dowód:

W pierwszej iteracji, dla i=1 zdanie jest prawdziwe (rozważamy posortowany ciąg A[1..1]).

W l-tej iteracji, jeżeli elementy A[1..l-2] są posortowane, to nowy klucz zostanie wstawiony na pozycję, w której nie będzie tworzył inwersji z żadnym z elementów w zbiorze do którego zostanie dołączony, a więc zbiór A[1..l-1] będzie posortowany.

W ostatniej iteracji pętli ostatni wolny klucz zostaje wstawiony w posortowany ciąg A[1..n-2] w wyniku czego powstaje posortowana tablica A[1..n-1]

Bezpośredni wniosek z powyższego twierdzenia: algorytm sortowania przez wstawianie dla każdej tablicy A dokona jej prawidłowego posortowania.

Przykłady implementacji[edytuj | edytuj kod]

Zobacz też[edytuj | edytuj kod]

Przypisy

Bibliografia[edytuj | edytuj kod]

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. WNT, 2007.


Linki zewnętrzne[edytuj | edytuj kod]