Sortowanie przez wstawianie

Z Wikipedii

Przykład działania sortowania przez wstawianie.

Sortowanie przez wstawianie (ang. Insert Sort, Insertion Sort) - prosty algorytm sortowania, o złożoności O(n²). Mimo że jest znacznie mniej wydajny od algorytmów takich jak quicksort czy heapsort posiada pewne zalety:

wydajny dla danych wstępnie posortowanych
wydajny dla zbiorów o niewielkiej liczebności
stabilny

Algorytm polega na usuwaniu pewnego elementu z danych wejściowych i wstawianiu go na odpowiednie miejsce w wynikach. Wybór następnego elementu z danych jest dowolny.

Spis treści

1 Schemat działania algorytmu
2 Analiza algorytmu
- 2.1 Złożoność
- 2.2 Poprawność
3 Przykłady implementacji
4 Zobacz też

[edytuj] Schemat działania algorytmu

Utwórz zbiór elementów posortowanych i przenieś do niego dowolny element ze zbioru nieposortowanego.
Weź dowolny element ze zbioru nieposortowanego.
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.
Wyciągnięty element wstaw w miejsce gdzie skończyłeś porównywać.
Jeśli zbiór elementów nieuporządkowanych jest niepusty wróć do punkt 2.

[edytuj] Analiza algorytmu

[edytuj] Złożoność

A - tablica danych
n - długość tablicy

Zgodnie z pseudokodem, umieszczonym we "Wprowadzeniu do algorytmów":

                                  
0. Insert_sort(A,n)                     
1.    for i=2 to n :                                     
2.       klucz = A[i]                                    
3.       j = i - 1                                       
4.       while j>0 and A[j]>klucz:                       
5.          A[j + 1] = A[j]              
6.          j = j - 1                    
7.       A[j+1] = klucz

Niech δ(i) oznacza ilość 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
instrukcja 4. jest wykonana $\sum_{i = 1}^{n} \delta (i)$ razy
instrukcja 5. jest wykonana $\sum_{i = 1}^{n} \delta (i) - 1$ razy
instrukcja 6. jest wykonana $\sum_{i = 1}^{n} \delta (i) - 1$ razy
instrukcja 7. jest wykonana n-1 razy

Jeżeli przez c₁, c₂, ..., c₇ oznaczymy czas pojedynczego wywołania instrukcji 1,2, ... 7, to całkowity czas wykonania algorytmu sortowania przez wstawianie będzie równy:

T(n) = c₁n + (c₂+c₃+c₇)(n-1) + $\sum_{i = 1}^{n} \delta (i)$ c₄ + ( $\sum_{i = 1}^{n} \delta (i) - 1$ )c₅ + ( $\sum_{i = 1}^{n} \delta (i) - 1$ )c₆

[edytuj] Przypadek optymistyczny

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 (4.) zachodzi A[j]<klucz - pętla (4.) nie zostaje wykonana ani razu, a więc ilość sprawdzeń warunku pętli (4.) δ(i) wynosi 1 dla wszystkich j od 0 do n. Całkowity czas T(n) = (c₁ + c₂ + c₄ + c₅ + c₈)n - (c₂ + c₄ + c₅ + c₈) 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).

[edytuj] Przypadek pesymistyczny

Gdy tablica danych wejściowych jest uporządkowana malejąco, w każdym przebiegu pętli (1.) przy sprawdzaniu warunków pętli (4.) zachodzi A[j]>klucz - pętla (4.) 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(n²).

[edytuj] Przypadek średni

Przy założeniu, że wszystkie możliwe wartości tablicy A występują z jednakowym prawdopodobieństwem, można dowieść, że oczekiwana ilość elementów A[0..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(n²).

[edytuj] Poprawność

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

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

Dowód:

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

W l-tej iteracji, jeżeli elementy A[0..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[0..l-1] będzie posortowany.

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

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

[edytuj] Przykłady implementacji

[edytuj] Przykład w języku imperatywnym - Python

def Insert_sort(A):
    for i in range(1,len(A)):
        klucz = A[i]
        j = i - 1
        while j>0 and A[j]>klucz:
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = klucz

[edytuj] Przykład w języku funkcyjnym

Implementacja algorytmu w języku funkcyjnym - SML-u:

(* funkcja bierze listę dowolnego typu i relacje zgodnie z którą sortuje elementy listy*)
fun isort [] f = []
  | isort (x::xs) f =
          let fun insert x [] = [x]
                | insert x (l as hd::tl) = if f (x,hd) then x::l
                                             else hd::insert x tl
          in insert x (isort xs f) end;

(* przykładowe użycie sortuj niemalejąco listę liczb całkowitych: *)
isort [108, 15, 15, 3, 14, 15, 108] op<;

[edytuj] Przykład w Prologu


wstaw(X,[Y|T],[Y|NT]) :- X>Y, wstaw(X,T,NT).
wstaw(X,[Y|T],[X,Y|T]) :- X=<Y.
wstaw(X,[],[X]).

sortuj([], []).

sortuj(X, Y) :-
        X = [H|T],
        sortuj(T, Y2),
        wstaw(H, Y2, Y),
        !.

[edytuj] Zobacz też

Kategoria: Algorytmy sortowania

We provide Linux to the World