Sortowanie przez wstawianie | Informatyka MIMUW

Sortowanie przez wstawianie jest algorytmem szczególnie polecanym do sortowania krótkich ciągów. Jego złożoność pesymistyczna jest asymptotycznie taka sama jak dwóch poprzednich algorytmów, ale zachowuje się on znacznie lepiej dla ciągów "prawie" posortowanych. Co znaczy "prawie" wyjaśnimy w dalszej części wykładu.

Idea sortowania przez wstawianie jest następująca. Sortujemy w \( n-1 \) fazach, ponumerowanych dla wygody opisu od 2 do \( n \). Przed rozpoczęciem \( i \)-tej fazy wiemy, że podtablica \( a[1..i-1] \) jest już posortowana. Naszym celem jest uporządkowanie podtablicy \( a[1..i] \), co w rzeczywistości oznacza wstawienie na właściwe miejsce elementu \( a[i] \) w uporządkowany ciąg \( a[1..i-1] \). W tym celu odkładamy element z pozycji \( a[i] \) na bok (zapamiętujemy w pomocniczej zmiennej), a następnie przeglądamy elementy podtablicy \( a[1..i-1] \) od prawej do lewej, przesuwając każdy element większy od odłożonego o jedną pozycję w prawo. Po napotkaniu w tablicy \( a \) elementu nie większego od elementu odłożonego (nazwijmy go elementem blokującym), element odłożony wstawiany tuż przed element blokujący. Oto zapis sortowania przez wstawianie - algorytm InsertionSort.

Algorytm Sortowanie przez wstawianie

InsertionSort 
  for i := 2 to n do 
  begin 
    //a[1..i-1] jest już posortowana 
    x := a[i] ; //odkładamy element z pozycji  i  
    j := i ; 
    while x  <  a[j-1] do 
    begin 
      a[j] := a[j-1] ; //przesuwamy element większy od  x  o jedną pozycję w prawo 
      j&nbsp;:= j-1  
    end; 
     a[j] := x  
 end;

Dokonamy teraz wspólnie analizy przedstawionego algorytmu. W tym celu postaraj się drogi czytelniku samodzielnie wykonać następujące ćwiczenia.

Ćwiczenie 2
Jakie znaczenie dla poprawności algorytmu InsertionSort ma założenie z początku wykładu o tym, że \( a[0] \le a[i] \), dla każdego \( i = 1, 2, ..., n \)?

Odpowiedź do ćwiczenia 2

Pętla "while" kończy się poprawnie w przypadku, gdy \( x \) jest mniejsze od wszystkich elementów z \( a[1..i-1] \).

Ćwiczenie 3
Załóżmy, że sortujemy permutację liczb \( 1, 2, \ldots, n \). Podaj permutacje, dla których algorytm InsertionSort wykona odpowiednio najwięcej i najmniej porównań, a następnie wyznacz dokładne liczby porównań w najgorszym i najlepszym przypadku. Uwaga: pamiętaj o porównaniach z \( a[0] \).

Odpowiedź do ćwiczenia 3

Najwięcej porównań zostanie wykonanych dla ciągu \( n, n-1, \ldots, 1 \). Liczba porównań w tym przypadku wynosi
\( 2 + 3 + \ldots + n = \frac{(n+2)(n-1)}{2} \). Najmniej porównań zostanie wykonanych dla permutacji \( 1,2, \ldots, n \) - dokładnie \( n-1 \).

Zastanówmy się, od czego zależy liczba porównań wykonywanych przez algorytm InsertionSort dla ustalonej permutacji \( \pi = < p_1, p_2, \ldots, p_n> \). W tym celu zdefiniujmy pojęcie inwersji w permutacji. Inwersją w permutacji \( \pi \) nazywamy każdą parę indeksów \( 1\le i < j \le \) takich, że \( p_i > p_j \).

Ćwiczenie 4
Zastanów się, jaka jest zależność pomiędzy liczbą porównań wykonywanych przez algorytm InsertionSort dla permutacji \( \pi \) a liczbą inwersji w tej permutacji.

Odpowiedź do ćwiczenia 4

Niech \( Inv(\pi) \) będzie liczbą inwersji w \( \pi \). Liczba porównań wykonywana przez InsertionSort dla \( \pi \) wynosi \( Inv(\pi) + n-1 \).

Jedną z miar uporządkowania ciągu elementów jest liczba inwersji w nim występujących. Permutacja rosnąca nie zawiera wcale inwersji, natomiast permutacja malejąca zawiera \( {n(n-1)}/{2} \) inwersji. Na podstawie ćwiczenia 4 wnioskujemy, że jeżeli ciąg wejściowy zawiera liniową ze względu na \( n \) liczbę inwersji, to dla takiego ciągu algorytm InsertionSort działa w czasie liniowym. Jeżeli jednak w ciągu wejściowym jest kwadratowa liczba inwersji, to algorytm InsertionSort działa w czasie kwadratowym. Może jednak takie dane są niesłychanie rzadkie, a dla "przeciętnych" danych algorytm InsertionSort zachowuje się zdecydowanie lepiej? Niestety, to nie jest prawda. Żeby to wykazać, obliczymy oczekiwaną liczbę porównań wykonywanych przez nasz algorytm dla "losowych" danych. Pisząc "losowych", musimy precyzyjnie określić, co mamy na myśli. Dla naszych rozważań przyjmiemy model losowej permutacji, w którym to zakłada się, że początkową zawartością sortowanej tablicy \( a \) jest permutacja liczb \( 1, 2,, n \) i każda z \( n! \) permutacji może pojawić się z tym samym prawdopodobieństwem \( \frac{1}{n!} \). Jeśli już ustaliliśmy model probabilistyczny, to możemy określić średnią liczbę porównań wykonywanych przez algorytm InsertionSort. Nietrudno zauważyć, że wynosi ona

\( n-1 + \frac{1}{n!}\sum_{\{\pi: \mbox{ permutacja liczb } 1,2, \ldots, n\}}Inv(\pi). \)
W powyższym wzorze wartość wyrażenia \( \frac{1}{n!}\sum_{\{\pi: \mbox{ permutacja liczb } 1,2, \ldots, n\}}Inv(\pi) \) jest równa oczekiwanej liczbie inwersji w losowej permutacji. Żeby policzyć oczekiwaną liczbę porównań wykonywaną przez algorytm InsertionSort, wystarczy więc wyznaczyć oczekiwaną liczbę inwersji w losowej permutacji.

Wektorem inwersji dla permutacji \( \pi \) nazywamy ciąg liczb \( w = [w_1, w_2, \ldots, w_n] \) taki, że \( w_i = |\{j: 1 \le j < i \mbox{ oraz } p_j > p_i \}| \), dla każdego \( i = 1,2, \ldots, n \). Innymi słowy, \( w_i \) jest liczbą tych elementów permutacji \( \pi \), która znajdują się na lewo od elementu \(_{i}\) i są od niego większe.

Ćwiczenie 5

Podaj wektor inwersji dla permutacji \( \pi=[7,8,2,4,6,1,5,3] \).

Odpowiedź do ćwiczenia 5

\( w = [0,0,2,2,2,5,3,5] \).

Nietrudno jest pokazać, że dwóm różnym permutacjom odpowiadają różne wektory inwersji.

Niech \( \pi', \pi" \) będą różnymi \( n \)-elementowymi permutacjami i niech \( w', w" \) będą odpwiednio wektorami inwersji dla tych permutacji. Niech \( i \) będzie największym takim indeksem, że \( \pi'_i \ne \pi"_i \). Bez straty ogólności możemy przyjąć, że \( \pi'_i < \pi"_i \). Wówczas \( w'_i > w"_i \). Dlaczego?

Zauważmy, że elementy każdego wektora inwersji \( w \) muszą spełniać nierówności \( 0 \le w_i < i \), dla \( i=1, 2, \ldots, n \). Oznaczmy zbiór wszystkich \( n \)-elementowych wektorów o takich własnościach przez \({W}_n \). Liczba elementów zbioru \({W}_n \) wynosi \( n! \). Z naszych dotychczasowych rozważań wynika, że istnieje wzajemnie jednoznaczna odpowiedniość pomiędzy permutacjami liczb \( 1,2,\ldots, n \), a wektorami z \({W}_n \). Dlatego elementy tego zbioru będziemy nazywali po prostu wektorami inwersji.

Ćwiczenie 6
Podaj permutację o wektorze inwersji \( w=[0,0,1,1,2,1,4,5] \).

Odpowiedź do ćwiczenia 6

\( \pi=[1,8,2,6,5,7,4,3] \).

Ćwiczenie 7

Zaproponuj algorytm, który dla danego wektora inwersji \( w=[w_1,w_2,\ldots, w_n] \) znajdzie odpowiadającą mu permutację.

Wskazówka do ćwiczenia 7

Należy budować permutację od końca, wyznaczając najpierw jej ostatni element, potem przedostatni, a na końcu element pierwszy.

Odpowiedź do ćwiczenia 7

Załóżmy, że wektor inwersji jest dany w tablicy \( w[1..n] \). Permutację budujemy w tablicy \( p[1..n] \). Zbiór \( Wolne \subset \{1,2,\ldots, n\} \) zawiera te elementy permutacji, których pozycja jest jeszcze nieokreślona. Oto schemat algorytmu:

Algorytm Wektor inwersji --> permutacja

Wolne := {1,2,..., n} 
for i := n downto 1 do 
begin 
  k := w[i] + 1; 
  //W zbiorze Wolne, i-ty element permutacji jest k-tym co do wartości, 
  //licząc od największego 
  x := k-ty co do wartości element w Wolne; 
  Wolne := Wolne - {x};  //usuń  x  z  Wolne  
  p[i] := x 
end;

Sumą wektora inwersji nazwiemy sumę jego elementów. Z dotychczasowych rozważań wynika, że suma wektora inwersji jest równa liczbie inwersji w odpowiadającej temu wektorowi permutacji. Losowy wektor inwersji można otrzymać losując każdy jego element niezależnie w ten sposób, że na pozycji \( i \)-tej może pojawić się każda z wartości \( 0, 1, \ldots, i-1 \) z jednakowym prawdopodobieństwem \( \frac{1}{i} \). Tak więc oczekiwana wartość \( i \)-tego elementu w losowym wektorze inwersji wynosi \( \frac{0+1+\ldots+i-1}{i} = \frac{i-1}{2} \). Z liniowości wartości oczekiwanej otrzymujemy, że oczekiwana suma losowego wektora inwersji wynosi \( 0+\frac{1}{2}+\ldots+ \frac{n-1}{2} = \frac{n(n-1)}{4} \). Zatem taka jest też oczekiwana liczba inwersji w losowej permutacji. Wynika stąd, że algorytm sortowania przez wstawianie zachowuje się dla "przeciętnych" danych podobnie, jak dla danych "najgorszych" i działa w czasie kwadratowym.