Sortowanie przez wstawianie. Procedura INSERTION-SORT.
Sortowanie przez wstawianie to algorytm, który rozwiązuje problem
INSERTION-SORT(A)
sortowania:
1. begin
Dane wejściowe: Ciąg n liczb (a1, . . . , an).
2. for i := 2 to n do
Wynik: Permutacja (ai1, . . . , ain) ciągu wejściowego, taka że
3. begin
ai1 d" ai2 d" · · · d" ain.
4. k := A[i];
// wstaw A[i] w posortowany ciÄ…g A[1..i - 1]. //
Algorytm ten zapiszemy w pseudokodzie jako procedurÄ™
5. j := i - 1;
INSERTION-SORT, której parametrem jest tablica A[1..n]
6. while j > 0 i A[j] > k do
zawierająca ciąg, który mamy posortować.
7. begin
Elementy wejściowej tablicy są sortowane w miejscu, tzn.
8. A[j + 1] := A[j];
wszystkie są przechowywane cały czas w tej samej tablicy, z
9. j := j - 1;
wyjątkiem stałej liczby elementów. (Oznacza to, że potrzeba
10. end;
jedynie stałej ilości dodatkowej pamięci.)
11. A[j + 1] := k;
12. end;
Kiedy procedura jest zakończona, tablica A zawiera posortowany
ciąg wyjściowy.
Przykład. Niezmiennik pętli.
i j k j > 0 i A[j] > k? A
2 1 2 tak [5, 2, 4, 6, 1, 3]
Żeby pokazać, że nasz algorytm poprawnie sortuje ciąg w tablicy
2 0 2 nie [5, 5, 4, 6, 1, 3]
A, udowodnimy następujący niezmiennik pętli:
3 2 4 tak [2, 5, 4, 6, 1, 3]
3 1 4 nie [2, 5, 5, 6, 1, 3]
Podczas każdego sprawdzania warunku pętli for fragment tablicy
4 3 6 nie [2, 4, 5, 6, 1, 3]
A[1..i - 1] składa się z elementów znajdujących się pierwotnie w
5 4 1 tak [2, 4, 5, 6, 1, 3]
A[1..i - 1], ale w porzÄ…dku niemalejÄ…cym.
5 3 1 tak [2, 4, 5, 6, 6, 3]
5 2 1 tak [2, 4, 5, 5, 6, 3] W przypadku pętli for i := 2 to n do warunkiem pętli jest i d" n.
5 1 1 tak [2, 4, 4, 5, 6, 3]
Pierwsze sprawdzenie tego warunku następuje bezpośrednio po
5 0 1 nie [2, 2, 4, 5, 6, 3]
nadaniu zmiennej sterującej i początkowej wartości 2.
6 5 3 tak [1, 2, 4, 5, 6, 3]
Po zakończeniu iteracji pętli, zmienna i jest zwiększana o 1, a
6 4 3 tak [1, 2, 4, 5, 6, 6]
następnie ponownie sprawdzany jest warunek pętli.
6 3 3 tak [1, 2, 4, 5, 5, 6]
6 2 3 nie [1, 2, 4, 4, 5, 6]
7 [1, 2, 3, 4, 5, 6]
Dowód niezmiennika.
Musimy udowodnić dwie własności niezmiennika pętli:
Inicjowanie: Podczas pierwszego sprawdzania warunku mamy
Inicjowanie: Jest on prawdziwy podczas pierwszego sprawdzania
i = 2. Fragment tablicy A[1..i - 1] zawiera tylko jeden element
warunku pętli.
A[1], zatem jest posortowany.
Utrzymanie: Jeśli jest on prawdziwy podczas sprawdzania
Utrzymanie: Załóżmy, że fragment tablicy A[1..i - 1] został
warunku pętli i warunek ten jest spełniony, to niezmiennik
posortowany. W kolejnej iteracji pętli for elementy A[i - 1],
pozostaje prawdziwy podczas następnego sprawdzania warunku
A[i - 2], A[i - 3] itd. sÄ… przesuwane o jednÄ… pozycjÄ™ w prawo
pętli.
dopóty, dopóki nie zostanie znaleziona właściwa pozycja dla A[i].
Jeśli spełnione są powyższe dwie własności, to niezmiennik jest Po zakończaniu iteracji, fragment A[1..i] jest posortowany.
prawdziwy podczas każdego sprawdzania warunku pętli, na mocy
Dowód niezmiennika jest zakończony, teraz łatwo wykazać
zasady indukcji.
poprawność algorytmu:
Zakończenie: Z prawdziwości niezmiennika podczas ostatniego
Zakończenie: Pętla for kończy się, kiedy wartość i przekracza n.
sprawdzania warunku pętli powinna wynikać poprawność
Z niezmiennika pętli dla i = n + 1 wynika, że cała tablica A[1..n]
algorytmu.
została posortowana.
Czas działania.
INSERTION-SORT(A) koszt krotność
1. begin
2. for i := 2 to n do c2 n
Oznaczmy czas wykonania wiersza nr i procedury
3. begin
INSERTION-SORT przez ci.
4. k := A[i]; c4 n - 1
Wartości ci zależą od konkretnej maszyny, ale nie zależą ani od n
5. j := i - 1; c5 n - 1
n
ani od elementów tablicy, traktujemy je więc jak stałe.

6. while j > 0 i A[j] > k do c6 ti
Zakładamy, że begin, end oraz komentarze, nie są wykonywalnymi
i=2
instrukcjami, więc kosztują zero czasu. 7. begin
n

Dla każdego i = 2, . . . , n, niech ti oznacza ilość sprawdzeń
8. A[j + 1] := A[j]; c8 (ti - 1)
warunku w wierszu 6 dla danej wartości i. Zauważmy, że i=2
n

sprawdzanie warunku pętli while lub for jest wykonywane o jeden
9. j := j - 1; c9 (ti - 1)
raz więcej niż treść pętli.
i=2
10. end;
Zauważmy, że 1 d" ti d" i, przy czym wartość ta zależy od
11. A[j + 1] := k; c11 n - 1
elementów A[1..i].
12. end;
Przypadek optymistyczny. Przypadek pesymistyczny.
Przypadek pesymistyczny występuje wówczas, gdy tablica jest
A
ączny czas działania procedury INSERTION-SORT dla tablicy
posortowana w porzÄ…dku odwrotnym, czyli malejÄ…cym. Musimy
A[1..n]:
wtedy porównać każdy element A[i] z każdym elementem
posortowanej tablicy A[1..i - 1], a więc ti = i dla i = 2, . . . , n.
n n

Mamy
T (n) = c1n + (c4 + c5 + c11)(n - 1) +c6 ti +(c8 + c9) (ti - 1).
i=2 i=2
n n

n(n + 1) n(n - 1)
ti = - 1, (ti - 1) = ,
W procedurze INSERTION-SORT przypadek optymistyczny
2 2
i=2 i=2
występuje wtedy, gdy tablica wejściowa jest już posortowana.
a pesymistyczny czas działania procedury INSERTION-SORT
Wówczas dla każdego i = 2, . . . , n stwierdzamy, że A[j] d" k w
wynosi
wierszu 6, gdy j ma wartość początkową i - 1.
T (n) = c1n + (c4 + c5 + c11)(n - 1)+
Zatem ti = 1 dla i = 2, . . . , n, a minimalny czas działania wynosi

n(n + 1) n(n - 1)
+c6 - 1 + (c8 + c9) .
T (n) = c1n + (c4 + c5 + c11 + c6)(n - 1) = Åš(n). 2 2
T (n) = Åš(n2).
Uwagi końcowe.
Optymistyczny czas działania procedury INSERTION-SORT dla
tablicy rozmiaru n wynosi Ś(n), a pesymistyczny czas działania
wynosi Åš(n2).
Zazwyczaj będziemy się ograniczać do analizy przypadku
pesymistycznego, ponieważ daje on ograniczenie górne na czas
działania algorytmu dla dowolnych danych.
Sortowanie przez wstawianie jest algorytmem stosujÄ…cym metodÄ™
przyrostowÄ…: majÄ…c posortowanÄ… podtablicÄ™ A[1..i - 1]
wstawiamy pojedynczy element A[i] we właściwe miejsce,
otrzymując większą posortowaną podtablicę A[1..i].