xxx

Sortowanie przez wstawianie

to 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. Jest efektywny
dla niewielkiej liczby elementów.

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;



jest wydajny dla zbiorów o niewielkiej

liczebności;



jest stabilny;



prosty w implementacji;

Zasada działania

Pierwszy element pozostaje na swoim

miejscu. Następnie bierzemy drugi i
sprawdzamy, w jakiej relacji jest on z
pierwszym. Jeśli jest niemniejszy, to zostaje
na drugim miejscu, w przeciwnym wypadku
wędruje na pierwsze miejsce. Dalej
sprawdzamy trzeci element (porównujemy
go do dwóch pierwszych i wstawiamy w
odpowiednie miejsce), czwarty
(porównujemy z trzema pierwszymi), piąty
itd.

Dla przykładowego ciągu wygląda to

następująco:

2 

5

 3 0 7 1 - liczba 5 pozostaje na swoim miejscu

(dwa pierwsze elementy są posortowane)

2 

3

 5 0 7 1 - liczba  3 zostaje wstawiona między

liczby  2 i  5 (trzy pierwsze elementy są
posortowane)

0 

2 3 5 7 1 - liczba  0 zostaje wstawiona na

początek (cztery pierwsze elementy są
posortowane)

0 2 3 5 

7

 1 - liczba  7 pozostaje na swoim miejscu

(pięć pierwszych elementów jest posortowanych)

0 

1

 2 3 5 7 - liczba  1 zostaje wstawiona między

liczby 0 i 2. (otrzymujemy zbiór uporządkowany)

Źródła:



https://pl.wikipedia.org/wiki/Sortowani
e_przez_wstawianie



http://www.algorytm.edu.pl/algorytmy
-maturalne/sortowanie-przez-
wstawianie.html

xxx