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ż

Rośnie liczba udzielanych kredytów mieszkaniowych

W I połowie 2008 r. banki udzieliły klientom indywidualnym i instytucjonalnym kredyty mieszkaniowe na sumę około 36 mld zł. To wzrost o 18 proc. w stosunku do analogicznego okresu ub. r. - podał Związek Banków Polskich.

KPP za jak najszybszym przyjęciem euro

Konfederacja Pracodawców Polskich (KPP) opowiada się za jak najszybszym przystąpieniem Polski do strefy euro. Ich zdaniem, ułatwi to prowadzenie działalności gospodarczej i wpłynie na rozwój przedsiębiorczości.

Invoptic ma zgodę UOKiK na przejęcie spółki JZO

Firma Invoptic ma zgodę Urzędu Ochrony Konkurencji i Konsumentów (UOKiK) na przejęcie kontroli nad spółką JZO. Firmy działają w branży optycznej.

Spadek indeksu zaufania inwestorów w Szwajcarii

Wskaźnik zaufania inwestorów w Szwajcarii spadł w sierpniu z powodu obaw, że spowolnienie wzrostu gospodarczego w Europie osłabi popyt na towary eksportowane ze Szwajcarii.

Bagsik powraca z nową aferą

To Bogusław Bagsik od początku stał za spółką Digit Serve, podejrzewaną o oszustwa i nielegalną działalność maklerską - pisze "Puls Biznesu". Gazeta odkryła w brytyjskim rejestrze handlowym dokumenty dowodzące, że założycielem firmy był bohater afery Art-B.

Linki: Strona g��wna

Encyklopedia