Sortowanie przez wstawianie

Sortowanie przez wstawianie jest jedną z najprostszych metod sortowania. Dlatego też zwykle
naukę algorytmów sortowania rozpoczyna się od tego zagadnienia (ale nie u nas :). Jednak sortowanie
tym sposobem jest mało efektywne kiedy mamy do czynienia z dużą ilością danych, co jest
spowodowane przez dużą złożoność - O(n^2). (patrz - wstęp do sortowania i złożoność
obliczeniowa)

Te fakty powodują, że sortowanie to jest używane tam, gdzie elementów nie ma zbyt wiele. To
określenie jest jednak określeniem elastycznym - to Ty decydujesz, jaka prędkość jest w danym
przypadku konieczna, ponieważ wszystko zależy od sytuacji. Moc komputerów również wciąż się
zmienia, dlatego podawanie konkretnych liczb jako granicy, do której sprawdza się ten algorytm
mijało by się tu z celem.

Zacznijmy jednak przedstawianie tegoż algorytmu. Zapewne zaskoczę Cię, mówiąc iż używałeś już
tej metody nieraz, nawet jako małe dziecko. Sortowanie przez wstawianie jest bowiem najbardziej
intuicyjnym sposobem porządkowania pewnego zbioru elementów. Najczęściej porównuje się je z
układaniem kart do gry, dlatego również posłużę się tym przykładem:

Wyobraź sobie, że masz w prawej ręce 10 różnych kart jednego koloru (jeżeli masz talię kart
gdzieś pod ręką to mogą się przydać :). Układasz je teraz w kolejności zgodnej z ich wartością. W
jaki sposób to robisz ? Zwykle postępujemy w taki sposób iż bierzemy po kolei karty z prawej ręki i
wstawiamy je w odpowiednie miejsce w lewej dłoni. I tak mając już np. w lewej ręce 3,6,7 bierzemy
kartę z numerem 4. Wstawiamy ją w swoje miejsce tzn. pomiędzy 3 i 6. Potem bierzemy następną, i
jeszcze, i jeszcze... Powoli wszystkie karty będą przechodziły ze strony prawej na lewą aż w końcu w
prawej ręce kart zabraknie, a w lewej wszystkie będą w wymaganym porządku.

To jest właśnie sortowanie przez wstawianie - każdy element po kolei wstawiamy w ciąg
posortowanych już elementów aż do momentu, kiedy wstawimy ostatnią kartę.

Przeanalizujemy teraz sposób na konkretnym przykładzie z liczbami do posortowania:

4
2
1
5
9
0
7
3
6
8


Bierzemy pierwszy element, czyli czwórkę i wstawiamy go do ciągu liczb posortowanych. Jako że
nic jeszcze tam nie ma, to po prostu go przepisujemy:

4

2
1
5
9
0
7
3
6
8


Dalej: bierzemy dwójeczkę i szukamy do niej pozycji... Analizujemy posortowany ciąg od końca -
czwórka jest większa od dwójki, czyli nasza liczba powinna być wcześniej. Wcześniej nie ma już nic,
czyli kończymy szukanie odpowiedniego miejsca i wstawiamy liczbę 2 na początek ciągu:

2
4

1
5
9
0
7
3
6
8


Tak samo zrobimy z jedynką porównujemy z kolejnymi elementami, ale zawsze wychodzi nam, że
to jeszcze nie tu, że musimy schodzić jeszcze niżej, aż dochodzimy do początku ciągu:

1
2
4

5
9
7
0
3
6
8


A teraz piątka. Porównujemy z ostatnim elementem i wychodzi nam, że piątka jest większa niż
ostatni element, czyli wpisujemy ją na końcu:

1
2
4
5

9
7
0
3
6
8


Dziewiątka:

1
2
4
5
9

7
0
3
6
8


Dochodzimy do siódemki. Porównując ją z elementem ostanim stwierdzamy, że jest większy od
liczby wstawianej. Musimy zatem wstawić siódemkę wcześniej. Jednak od piątki jest już większy.
Wstawiamy zatem pomiędzy 5 a 9:

1
2
4
5
7
9

0
3
6
8


Kolejne etapy:

0
1
2
4
5
7
9

3
6
8


0
1
2
3
4
5
7
9

6
8


0
1
2
3
4
5
6
7
9

8


0
1
2
3
4
5
6
7
8
9



I tablica posortowana ! Pomyśleć możesz - no tak, ładnie to wygląda, ale jak to zaprogramować
??? Powoli wszystko można zrobić... :)

Przyjmijmy iż w tablicy t przechowujemy sortowane liczby a w zmiennej n mamy ilość tych
elementów (bo przecież tablica nie musi być pełna)

Zabieramy się do tego problemu krok po kroku. Co wiemy o naszym algorytmie ? Czynność
wstawiania musi się wykonać tyle razy ile jest elementów, czyli n razy.

Robimy szielet pętelki:

for li:=2 to n do
begin
{bierz element i wstawiaj go w odpowiednie miejsce}
end;

Dlaczego zaczynamy od dwójki ? Nasze elementy będziemy w całości sortować w tablicy t, po
prostu na początku będziemy mieli ciąg posortowany, a na końcu nieposortowany. Wszystkie
elementy będziemy odowiednio przesuwać. Jeżeli bierzemy pierwszy element z tablicy, to wiadomo, że
wstawimy go na pierwszą pozycję w posortowanym ciągu (bo więcej pozycji tam nie ma) czyli inaczej
wyląduje on i tak na pierwszej pozycji w tablicy. Dlatego ten element opuszczamy. On na razie nigdzie
się i tak nie przesunie.

Rozbudowujemy naszą pętelkę sortującą:

var klucz : Integer;
{...}
for li:=2 to n do
begin
klucz:=t[li];
end;

Czyli mamy coś takiego - bierz po kolei każdy element z tablicy i zapamiętuj go w zmiennej klucz.
Ta zmienna mówi nam o tym, jaką wartość obecnie będziemy wstawiać do posortowanego ciągu.

for li:=2 to n do
begin
klucz:=t[li];
p:=li-1;
while (p>0) and (t[p]>klucz) do
begin
t[p+1]:=t[p];
p:=p-1;
end;
t[p+1]:=klucz;
end;

Tak wygląda całe sortowanie. Teraz to wytłumaczę. Bierzemy po kolei każdy element z tablicy i
zapisujemy go do zmiennej klucz. Teraz musimy ustalić jego pozycję w tablicy. Będziemy go
porównywali z każdym elementem z dolnej części tablicy (od 1 do pozycji tego elementu).

Zaczynamy porównywanie od elementu mniejszego od obecnej pozycji o 1 (p:=li-1).

Przypomij sobie przykład który rozpatrywaliśmy - bierzemy element i zaczynamy go porównywać z
tymi wszystkimi poprzednimi, zaczynając od ostatniego posortowanego, czyli od elementu
poprzedzającego aktualny.

Teraz następuje część szukająca właściwej pozycji:

while (t[p]>klucz) and (p>0) do

Tak długo jak w tablicy mamy elementy większe od tego, który właśnie chcemy wstawić oraz
jesteśmy jeszcze w obrębie tablicy...

begin
t[p+1]:=t[p];
p:=p-1;
end;

Przesuwaj elementy w tablicy o jeden w górę i zmniejszaj indeks p, który mówi nam który element
porównujemy z kluczem.

Jaki cel ma przesuwanie elementów ? Otóż jeżeli widzimy, że w danym miejscu wartość w tablicy
jest większa od tej wstawianej to wiemy, że wstawimy naszą liczbę gdzieś wcześniej. Jeżeli tak ma się
stać, musimy wszystkie elementy które są powyżej niej przesunąć o jedno miejsce w prawą stronę aby
zrobić miejsce wstawianej liczbie. Czy czasem nie pozamazujemy sobie tutaj danych ? Przecież
kopiujemy tutaj wartość pewnej komórki do komórki o jeden większej. Co się stanie z tą wartością,
która tam była ? Ona już wcześniej została przekopiowana o jeden wyżej itd.

Pokażę jeden krok takiej pętli:

1
5
6
3
7


Do wstawienia mamy trójkę. Najpierw zapamiętujemy ją:

1
5
6
3
7


Teraz wszystkie elementy większe od trójki kopiujemy do komórek o jeden w prawo:

1
5
5
6
7


W ten sposób na drugiej pozycji zrobiło się miejsce do wstawienia naszej zapamiętanej liczby:

1
3
5
6
7


Przyjrzyjmy się wstawieniu:

while (p>0) and (t[p]>klucz) do
begin
t[p+1]:=t[p];
p:=p-1;
end;
t[p+1]:=klucz;

Ale dlaczego na pozycję p+1 ? Otóż skoro dochodzimy do wstawiania, to znaczy że jeden z
warunków pętli while nie został spełniony, czyli albo p=0, albo p wskazuje na element, który nie jest
większy od wstawianej liczby.

Skoro p=0 to znaczy, że doszliśmy za zakres tablicy i to oznacza, że musimy wstawić nasz element
na pierwszej pozycji (czyli 0+1). A jeżeli p wskazuje na element nie większy od klucza (czyli w naszym
przypadku wskazuje na jedynkę), to znaczy że tuż nad tą pierwszą liczbą mniejszą (lub równą) jest
zrobione miejsce na naszą wstawianą liczbę.

Przeanalizuj jeszcze raz całość:

for li:=2 to n do
begin
klucz:=t[li];
p:=li-1;
while (p>0) and (t[p]>klucz) do
begin
t[p+1]:=t[p];
p:=p-1;
end;
t[p+1]:=klucz;
end;

Czyli kolejno: bierz elementy jeden za drugim dla wszystkich poniżej sprawdzaj, czy są większe. Po
drodze przesuwaj wszystko o jeden w górę. Jeżeli znajdzie się element nie większy od wstawianego to
kończymy przesuwanie i wstawiamy tam nasz element.

Wypróbuj teraz tę procedurę w praktyce - utwórz sobie tablicę, do której powpisuj różne dane.
Do zmiennej n wpisz ile jest tych danych i spróbuj to posortować. Następnie wypisz wszystkie
elementy na ekan.

Wszystko w porządku ? Spróbuj teraz posortować większą liczbę losowych danych. Porównaj
czasy sortowania. Po prostu zapoznaj się z tym algorytmem w praktyce. Skorzystaj również z
programu przykładowego, szczególnie jeśli masz jakieś problemy z zaprogramowaniem...