Algorytmy i struktury danych/Sortowanie - BubbleSort, SelectionSort, InsertionSort

Ten wykład poświęcimy prostym algorytmom sortowania. Zanalizujemy ich wady i zalety, co przygotuje nas do poszukiwania algorytmów lepszych. Zacznijmy od zdefiniowania problemu.

Definicja problemu

Niech $(U,\leq )$ będzie zbiorem liniowo uporządkowanym z relacją porządkującą $\leq$ i niech $c_{1},c_{2},\ldots ,c_{n}$ będzie ciągiem $n$ elementów z $U$, dla pewnego całkowitego $n>0$. Należy znaleźć permutację $c_{i_{1}},c_{i_{2}},\ldots ,c_{i_{n}}$ taką, że $c_{i_{1}}\leq c_{i_{2}}\leq \ldots \leq c_{i_{n}}$.

Uwaga: dla pary elementów $x,y\in U$ będziemy pisali $x<y$ ($x>y$), gdy $x\leq y$ ($y\leq x$) oraz $x\neq y$.

W tym wykładzie przyjmujemy, że elementy ciągu $c$ znajdują się w tablicy $a[1..n]$, tzn. $a[1]=c_{1},a[2]=c_{2},\ldots ,a[n]=c_{n}$. Będziemy także chcieli, żeby posortowany ciąg $c$ znajdował się nadal w tablicy $a$, tzn. wynikiem sortowania ma być $a[1]=c_{i_{1}}\leq a[2]=c_{i_{2}}\leq \ldots \leq a[n]=c_{i_{n}}$. Dla wygody dalszych rozważań przyjmijmy, że tablica $a$ jest indeksowana od $0$ i że $a[0]$ zawiera element, który nie jest większy od żadnego elementu z $a[1..n]$, tzn. dla każdego $i=1,2,\ldots ,n$, $a[0]\leq a[i]$.

Zauważmy, że w tak sformułowanym problemie sortowania nic nie wiemy o naturze elementów z $U$. Na $U$ mogą składać się zarówno liczby całkowite lub rzeczywiste, jak i $U$ może być zbiorem rekordów, które należy posortować według ich kluczy. Jedynym sposobem ustalenie porządku w tablicy $a$ jest porównywanie jej elementów parami. Operacja porównania będzie operacją dominującą w naszych algorytmach. Ponieważ będziemy chcieli ustalić wynik także w tablicy $a$, to potrzebna nam jest jeszcze operacja zamiany dwóch elementów w tablicy. Tą operacją będzie operacja $Exchange(i,j)$ polegająca na zamianie elementów w tablicy $a$ z pozycji $i$ oraz $j$, $1\leq i,j\leq n$.

Sortowanie bąbelkowe (BubbleSort)

Jest to jeden z najprostszych algorytmów sortowania. Sortowanie bąbelkowe jest wykonywane w $n-1$ fazach. W fazie $i$-tej wyznaczany jest $i$-ty najmniejszy element. Załóżmy, że po $i-1$ pierwszych fazach mamy wyznaczone i uporządkowane $i-1$ najmniejsze elementy, tzn. $a[1]\leq a[2]\leq \ldots a[i-1]$ i dla każdego $k=i,i+1,\ldots ,n$, mamy $a[i-1]\leq a[k]$. W fazie $i$-tej porównywane są kolejno elementy w parach $(a[n],a[n-1])$, $(a[n-1],a[n-2])$, ..., $(a[i+1],a[i])$. Jeżeli elementy w parze nie są uporządkowane, to dokonujemy ich zamiany. Oto algorytm sortowania bąbelkowego.

Algorytm Sortowanie bąbelkowe

---

 BubbleSort
 1  for $i:=1$ to $n-1$ do
 2    for $j:=n$  downto $i+1$ do
 3    if $a[j-1]>a[j]$ then
 4      $Exchange(j-1,j)$;

Poniżej zilustrowano działanie sortowania bąbelkowego.

<applet code="SortItem" archive="images/e/ef/Sort.jar" width="300" height="300"> alg=BubbleSort delay=1000 </applet>

---

Zaletą sortowania bąbelkowego jest jego prostota i bardzo krótki kod. Niestety jego główną wadą jest to, że zawsze, niezależnie od danych, wykonuje tyle samo porównań: $n-1$ w pierwszej fazie, $n-2$ w drugiej, ..., $1$ w fazie ostatniej, co daje łącznie $\sum _{i=1}^{n-1}(n-i)={\frac {n(n-1)}{2}}$ porównań. Liczba zamian może się zmieniać od $0$ do ${\frac {n(n-1)}{2}}.$ Zauważmy, że tak zapisany algorytm sortowania bąbelkowego zawsze wykonuje $n-1$ faz, nawet wtedy, gdy ciąg wejściowy jest już uporządkowany. Celem ćwiczenia 1 jest taka modyfikacja algorytmu, aby zakończyć jego działanie, kiedy tylko zostanie stwierdzone, że tablica $a$ jest już uporządkowana.

---

Ćwiczenie 1

Zmodyfikuj algorytm sortowania bąbelkowego w taki sposób, żeby jego wykonywanie kończyło się z chwilą stwierdzenia, że tablica $a$ jest już posortowana.

Odpowiedź do ćwiczenia 1

Algorytm BubbleSortBis

---

 1  for $i:=1$ to $n-1$ do
 2  begin
 3    $posortowana:=$ TRUE;
 4    for $j:=n$  downto $i+1$ do
 5    if $a[j-1]>a[j]$ then
 6      begin $exchange(j-1,j)$; $posortowana:=$ FALSE end;
 7    if $posortowana$ then
 8    //nie wykonano żadnych zamian;
 9    //koniec wykonywania zewnętrznej pętli for 
 10      EXIT
 11  end

Sortowanie przez wybór (SelectionSort)

Na sortowanie bąbelkowe można spojrzeć jeszcze inaczej. W każdej fazie przepychamy na pierwsze miejsce w nieuporządkowanej części tablicy element najmniejszy. Symetrycznie moglibyśmy sortować poczynając od elementów nawiększych. W sortowaniu przez wybór nie przepychamy elementu największego (najmniejszego) na jego miejsce w ciągu uporządkowanym, tylko znajdujemy jego pozycję, a następnie znaleziony element - największy w części nieuporządkowanej - zamieniamy z elementem, który znajduje się na docelowej pozycji elementu największego. Niech $Max(i)$ będzie funkcją, której wartością jest pozycja największego elementu w podtablicy $a[1..i]$. Oto schemat algorytmu sortowania przez wybór:

Algorytm Schemat algorytmu sortowania przez wybór

---

 schemat SelectionSort 
 1  for $i:=n$ downto $2$ do
 2  begin
 3    $j:=Max(i)$;
 4    $Exchange(i,j)$
 5  end;

Dlaczego użyliśmy słowa schemat? Zauważmy, że do pełnego zdefinowania algorytmu, a także dla jego analizy, niezbędne jest zdefiniowanie funkcji $Max$. W klasycznym sortowaniu przez wybór pozycję elementu największego w podtablicy $a[1..i]$ wyznaczamy przeszukując podtablicę od lewej do prawej, pamiętając w zmiennej pomocniczej pozycję dotychczas największego elementu i modyfikując wartość tej zmiennej każdorazowo po napotkaniu elementu większego od dotychczas największego. Oto pełny zapis algorytmu sortowania przez wybór - algorytmu SelectionSort.

Algorytm Sortowanie przez wybór

---

 SelectionSort
 1  for $i:=n$ downto $2$ do
 2  begin
 3    $j:=1$;
 4    for $k:=2$ to $i$ do
 5      if $a[k]>a[j]$ then $j:=k$;
 6    $Exchange(i,j)$
 7  end;

Nietrudno zauważyć, że algorytm SelectionSort wykonuje saką zamą liczbę porównań, co algorytm bąbelkowy. Jednak w tym przypadku maksymalna liczba zamian wynosi tylko $n-1$. Poniższa animacja ilustruje działanie algorytmu SelectionSort.

<applet code="SortItem" archive="images/e/ef/Sort.jar" width="300" height="300"> alg=SelectionSort delay=1000 </applet>

---

Należy podkreślić, że w implementacji schematu sortowania przez wybór mamy swobodę w realizacji funkcji $Max$. Wykorzystamy to w algorytmie sortowania z użyciem struktury danych zwanej kopcem.

Sortowanie przez wstawianie

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
 1  for $i:=2$ to $n$ do
 2  begin
 3    //$a[1..i-1]$ jest już posortowana
 4    $x:=a[i]$; //odkładamy element z pozycji $i$
 5    $j:=i$;
 6    while $x<a[j-1]$ do
 7    begin
 8      $a[j]:=a[j-1]$; //przesuwamy element większy od $x$ o jedną pozycję w prawo    
 9      $j:=j-1$
 10   end;
 11    $a[j]:=x$
 12 end;

Poniższa animacja ilustruje działanie sortowania przez wstawianie.

<applet code="SortItem" archive="images/e/ef/Sort.jar" width="300" height="300"> alg=InsertionSort delay=1000 </applet>

---

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]\leq 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\leq i<j\leq$ 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 Parser nie mógł rozpoznać (nieznana funkcja „\frav”): {\displaystyle \frav{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 Parser nie mógł rozpoznać (nieznana funkcja „\ldts”): {\displaystyle 1, 2,\ldts, 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. Tak więc, żeby policzyć oczekiwaną liczbę porównań wykonywaną przez algorytm InsertionSort, wystarczy 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\leq 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 Parser nie mógł rozpoznać (nieznana funkcja „\p”): {\displaystyle \p_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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi', \pi"} będą różnymi $n$-elementowymi permutacjami i niech Parser nie mógł rozpoznać (błąd składni): {\displaystyle w', w"} będą odpwiednio wektorami inwersji dla tych permutacji. Niech $i$ będzie największym takim indeksem, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi'_i \ne \pi"_i} . Bez straty ogólności możemy przyjąć, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pi'_i < \pi"_i} . Wówczas Parser nie mógł rozpoznać (błąd składni): {\displaystyle w'_i > w"_i} . Dlaczego?

Zauważmy, że elementy każdego wektora inwersji $w$ muszą spełniać nierówności $0\leq w_{i}<i$, dla $i=1,2,\ldots ,n$. Oznaczmy zbiór wszystkich $n$-elementowych wektorów o takich własnościach przez Parser nie mógł rozpoznać (nieznana funkcja „\calc”): {\displaystyle \calc{W}_n} . Liczba elementów zbioru Parser nie mógł rozpoznać (nieznana funkcja „\calc”): {\displaystyle \calc{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 Parser nie mógł rozpoznać (nieznana funkcja „\calc”): {\displaystyle \calc{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, wyznaczją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

---

 1  $Wolne:=\{1,2,\ldots ,n\}$ 
 2  for $i:=n$ downto $1$ do
 3  begin
 4    $k:=w[i]+1;$
 5    //W zbiorze $Wolne$, $i$-ty element permutacji jest $k$-tym co do wartości, 
 6    //licząc od największego 
 7    $x:=k{\mbox{-ty co do wartości element w }}Wolne$;
 8    $Wolne:=Wolne-\{x\};$ //usuń $x$ z $Wolne$
 9    $p[i]:=x$  
 10 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 Parser nie mógł rozpoznać (nieznana funkcja „\ldost”): {\displaystyle 0+\frac{1}{2}+\ldost + \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.