Sortowanie przez wstawianie
Z Wikipedii
Sortowanie przez wstawianie (ang. Insert Sort, Insertion Sort) - prosty algorytm sortowania, o złożoności O(n2). 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 |
[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 razy
- instrukcja 5. jest wykonana razy
- instrukcja 6. jest wykonana razy
- instrukcja 7. jest wykonana n-1 razy
Jeżeli przez c1, c2, ..., c7 oznaczymy czas pojedynczego wywołania instrukcji 1,2, ... 7, to całkowity czas wykonania algorytmu sortowania przez wstawianie będzie równy:
- T(n) = c1n + (c2+c3+c7)(n-1) + c4 + ()c5 + ()c6
[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) = (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).
[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) O(n2).
[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) O(n2).
[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), !.