Algorytmy i struktury danych/Dolne granice i sortowanie pozycyjne

Wszystkie rozważane dotychczas algorytmy sortowały porównując ze sobą elementy porządkowanego ciągu. W żadnym z nich pesymistyczna liczba wykonywanych porównań nie była mniejszego rzędu niż $n\log n$.

Czy za pomocą porównań można sortować istotnie szybciej?

Odpowiedź brzmi NIE.

Dolna granica

Załóżmy, że chcemy posortować $n$ różnych elementów $x_{1},\ldots ,x_{n}$ i jedynym sposobem ustalenia porządku pomiędzy nimi jest porównywanie ich w parach. Wynikiem sortowania jest permutacja $x_{i_{1}}<x_{i_{2}}<\ldots <x_{i_{n}}$. Możliwych wyników sortowania jest oczywiście tyle, ile wszystkich permutacji zbioru $n$-elementowego, czyli $n!$. Każdy algorytm sortowania przez porównania można zapisać za pomocą drzewa decyzyjnego. ‘’’Drzewo decyzyjne’’’ jest drzewem binarnym, w którym wszystkie węzły różne od liści mają po dwóch synów. W tych węzłach zapisujemy pary indeksów $i:j$, $1\leq i<j\leq n$. Każda taka para $i:j$ oznacza, że interesuje nas wynik porównania $x_{i}$ z $x_{j}$. Jeśli wynikiem porównania jest TAK, co oznacza, że $x_{i}$ jest mniejsze od $x_{j}$, kierujemy się do lewego poddrzewa, zadając jako kolejne to pytanie, które odpowiada parze elementów zapisanych w korzeniu lewego poddrzewa (o ile to nie jest liść). Jeśli wynikiem porównania jest NIE, co w tym przypadku oznacza, że $x_{i}$ nie jest mniejsze od $x_{j}$, przechodzimy do prawego poddrzewa. Bez straty ogólności możemy założyć, że w naszym drzewie nie wykonujemy redundantnych porównań, tzn. nie pytamy o wynik porównania, jeśli tylko ten wynik można wywnioskować z odpowiedzi na wcześniej zadane pytania. Sortowanie polega na przejściu w drzewie od korzenia do pewnego liścia (węzła bez synów). Jeśli odpowiedzi na zadane pytania pozwalają na wskazanie porządku w zbiorze $\{x_{1},x_{2},\ldots ,x_{n}\}$, to stosowna permutacja wyznaczająca ten porządek znajduje się właśnie w liściu na końcu ścieżki. Na rysunku poniżej przedstawiono sortujące drzewo decyzyjne dla 3 elementów.

Pesymistyczna złożoność algorytmu opisanego za pomocą drzewa decyzyjnego to oczywiście wysokość tego drzewa, czyli długość najdłuższej ścieżki od korzenia do liścia w tym drzewie mierzona liczbą krawędzi. Drzewo decyzyjne sortujące $n$-elementów jest drzewem binarnym o $n!$ liściach. Najmniejsza wysokość drzewa binarnego o $k$ liściach wynosi $\lceil \log k\rceil$. Wynika stąd, że każdy algorytm sortujący przez porównania wykonuje w pesymistycznym przypadku $\lceil \log n!\rceil$ porónań. Można pokazać, że $\lceil \log n!\rceil \geq n\log n-1.45n$. Podobne dolne ograniczenie zachodzi, gdy pytamy o średnią liczbę porównań w modelu losowych permutacji, tzn. gdy każdy z $n!$ wyników sortowania jest możliwy z jednakowym prawdopodobieństwem ${\frac {1}{n!}}$. W tym wykładzie pominiemy dowód tego faktu.

Sortowanie w czasie liniowym

Czy można sortować szybciej niż w czasie $O(n\log n)$. Odpowiedzią jest tak, jeśli wiemy coś więcej o sortowanym ciągu. Na przykład gdy liczba inwersji w ciągu jest liniowa ze względu na jego długość, algorytm InsertionSort posortuje taki ciąg w czasie liniowym. Zastanówmy się teraz, w jaki sposób można posortować tablicę $a[1..n]$, jeśli wiemy, że jej elementami są liczby całkowite z przedziału $0..m-1$, dla pewnego $m\geq 1$. Jest wiele rozwiązań tego zadania. Jednym z nich jest tzw. sortowanie kubełkowe. Bierzemy $m$ kubełków $B[0..m-1]$. Do kubełka $B[i]$ wrzucamy wszystkie elementy z tablicy $a$ o wartości równej $i$. Następnie wypisujemy zawartości kubełków, poczynając od kubełka $B[0]$. Kubełki reprezentujemy jako listy jednokierunkowe. Oto dokładniejszy zapis algorytmu sortowania kubełkowego.

Algorytm Sortowanie kubełkowe

---

 1  for $i:=0$ to $m-1$ do
 2    zainicjuj $B[i]$ jako listę pustą; 
 3  for $i:=n$ downto 1 do
 4    wstaw $a[i]$ na początek listy $B[a[i]]$;
 5  scal listy $B$ w jedną listę, dołączając listę $B[i+1]$
    po liście $B[i]$;
 6  wpisz po kolei elementy z posortowanej listy na kolejne pozycje w tablicy $a$;

Zauważmy, że przeglądanie tablicy $a$ od końca i wrzucanie jej elementów na początki list $B$ gwarantuje, że tablica $a$ zostanie posortowana stabilnie. Oznacza to, że względny porządek pomiędzy elementami o tej samej wartości nie ulega zmianie. Analiza złożoności czasowej tego algorytmu jest bardzo prosta. Kroki 1-2 wykonują się w czasie $O(m)$, kroki 3-4 w czasie $O(n)$, krok 5 można wykonać w czasie O(m), jeśli pamiętamy wskaźniki na końce list, lub w czasie $O(n+m)$, gdy musimy przejrzeć każdą listę w poszukiwaniu jej końca. Krok 6 zabiera czas $O(n)$. Otrzymujemy zatem algorytm sortujący, który działa w czasie $O(n+m)$. Gdy $m$ jest rzędu co najwyżej $n$ nasz algorytmy wykonuje tylko liniową liczbę operacji!

Ten sam wynik można osiągnąć za pomocą sortowania przez zliczanie. W tym algorytmie dla każdej wartości $i=0,1,\ldots ,m-1$ zliczamy ile razy pojawia się ona w tablicy $a[1..n]$. Taka informacja pozwala już łatwo określić pozycje elementów o wartości $i$ w posortowanej tablicy. W tym celu wystarczy wiedzieć ile jest elementów o wartościach mniejszych. Elementy o tej samej wartości $i$ umieszczamy następnie na pozycjach docelowych, w kolejności ich początkowego występowania w tablicy $a$. Oto formalny zapis algorytmu:

Algorytm Sortowanie przez zliczanie

---

 1  //zliczanie wystąpień poszczególnych wartości w tablicy $a$
 2  for $i:=0$ to $m-1$ do $t[i]:=0$;
 3  for $j:=1$ to $n$ do $t[a[j]]:=t[a[j]]+1$;
 4  //obliczenie dla każdego $i$ liczby elementów nie większych od $i$
 5  for $i:=1$ to $m-1$ do $t[i]:=t[i]+t[i-1]$;
 6  //w tablicy posortowanej elementy o wartości $i$ znajdują się
 7  //na pozycjach od $t[i-1]+1$ do $t[i]$, jeśli tylko przyjmiemy, że $t[0]=0$
 8  //w sortowaniu wykorzystujemy pomocniczą tablicę $b$
 9  //sortowane elementy umieszczamy w tablicy $b$ na ich docelowych pozycjach
 10 for $j:=n$ downto 1 do
 11 begin 
 12   $b[t[a[j]]]:=a[j]$; 
 13   $t[a[j]]:=t[a[j]]-1$; //$t[a[j]]$ jest ostatnią wolną pozycją dla
 14   //kolejnego (od końca) elementu o wartości $a[j]$ 
 15 end;
 16 $a:=b$; //przepisanie posortowanej tablicy $b$ do $a$

Podobnie jak w sortowaniu kubełkowym nasz algorytm działa w czasie $O(n+m)$ i jest algorytmem liniowym dla każdego $m$, które jest rzędu co najwyżej $n$.

Ten algorytm, tak jak sortowanie kubełkowe, jest algorytmem stabilnym. Stabilność wykorzystamy do zaadaptowania sortowania przez zliczanie do sortowania leksykograficznego w czasie liniowym słów o tych samych długościach. Załóżmy, że $\Sigma =\{0<1<...<m-1\}$ jest uporządkowanym alfabetem $m$-elementowym i danych jest $n$ słów $w[1],w[2],\ldots ,w[n]$ nad alfabetem $\Sigma$, każde o długości $k$. Inaczej mówiąc, słowo $w[i]$ jest tablicą $w[i][1..k]$ o wartościach z $\Sigma$. W porządku leksykograficznym $w[i]$ jest mniejsze od $w[j]$ wtedy i tylko wtedy, gdy istnieje $1\leq l\leq k$ takie, że $w[i][s]=w[j][s]$ dla każdego $s=1,2,...,l-1$ oraz $w[i][l]<w[j][l]$. Algorytm sortowania leksykograficznego jest teraz bardzo prosty. W sortowaniu słowa są przetwarzane od końca. Algorytm jest wykonywany w $k$ fazach ponumerowanych malejąco $k,k-1,\ldots ,1$. Przed rozpoczęciem fazy o numerze $i$ słowa $w$ są już uporządkowane leksykograficzne względem swoich sufiksów o długościach równych $k-i$, czyli podsłów składających się ze znaków z pozycji $i+1,i+2,\ldots ,k$. W fazie $i$-tej sortujemy słowa $w$ stabilnie względem znaków z pozycji $i$. Stabilność gwarantuje, że porządek słów, które posiadają te same elementy na pozycji $i$-tej, będzie wyznaczony przez ich wcześniej już uporządkowane sufiksy. Poniżej przedstawiamy formalny opis algorytmu sortowania leksykograficznego. W tym algorytmie w tablicy $a$ będziemy przechowywali indeksy słów $w$ uporządkowanych względem swoich sufiksów.

Algorytm Sortowanie leksykograficzne słów o tych samych długościach

---

 1  for $j:=1$ to $n$ do 
 2    $a[i]:=i$;
 3  for $faza:=k$ downto 1 do 
 4  //sortowanie stabilnie słów $w[a[1]],w[a[2]],\ldots ,w[a[n]]$ 
 5  //względem elementów z pozycji o numerze $faza$
 6  begin
 7  //sortowanie przez zliczanie 
 8    for $i:=0$ to $m-1$ do $t[i]:=0$;
 9    for $j:=1$ to $n$ do 
 10     $t[w[a[j]][faza]]:=t[w[a[j]][faza]]+1$;
 11   for $i:=1$ to $m-1$ do $t[i]:=t[i]+t[i-1]$;
 12   for $j:=n$ downto 1 do
 13   begin 
 14     $b[t[w[a[j]][faza]]]:=a[j]$; 
 15     $t[w[a[j]][faza]]:=t[w[a[j]][faza]]-1$;
 16   end;
 17   $a:=b$
 18  end

Po zakończeniu wykonywania powyższego algorytmu mamy $w[a[1]]\leq w[a[2]]\leq \ldots \leq w[a[n]]$. Analiza tego algorytmu jest niezmiernie prosta. Wykonujemy $k$ faz. Czas działania każdej fazy wynosi $O(n+m)$. Tak więc cały algorytm działa w czasie proporcjonalnym do $kn+km$. Dla $m$ rzędu co najwyżej $n$ mamy algorytm o złożoności $O(kn)$. Zauważmy, że wielkość $kn$ to rozmiar danych - $n$ słów, każde o długości $k$. Tak więc dostaliśmy algorytm liniowy, sortujący leksykograficznie słowa o tej samej długości nad alfabetem o rozmiarze rzędu co najwyżej $n$. Zauważmy, że słowa nad alfabetem $\Sigma =\{0,\ldots ,m-1\}$ można interpretować jako liczby całkowite bez znaku zapisane w układzie pozycyjnym przy podstawie $m$. Dlatego uprawnione jest mówić w tym miejscu o ‘’’sortowaniu pozycyjnym’’’.

Powstaje naturalne pytanie, czy jesteśmy w stanie sortować w czasie liniowym słowa o różnych długościach. Odpowiedź jest pozytywna. Poniżej przedstawiamy szkic takiego algorytmu. Szczegóły implementacyjne pozostawiamy czytelnikom. Załóżmy, że chcemy posortować leksykograficznie $n$ słów $w_{1},w_{2},\ldots ,w_{n}$ nad alfabetem $\Sigma =\{0,1,\ldots ,m-1\}$. Dla dalszych rozważań przyjmijmy, że $m$ jest rzędu co najwyżej $n$. Niech $l_{i}\geq 1$ będzie długością $i$-tego słowa. Zauważmy, że rozmiar danych w tym zadaniu wynosi $\sum _{i=1}^{n}l_{i}$. Będziemy chcieli, żeby nasz algorytm sortował słowa $w$ w czasie liniowym ze względu na tę wielkość. Niech $l_{max}$ będzie długością najdłuższego słowa. Zauważmy, że bardzo łatwo zaadaptować do rozwiązania tego zadania algorytm sortowania słów o takich samych długościach. Wystarczy każde słowo uzupełnić do długości $l_{max}$ symbolem, który będzie traktowany jako mniejszy od każdego symbolu z $\Sigma$. W naszym przypadku tym symbolem może być po prostu -1. Niestety takie podejście daje algorytm, którego czas działania wynosi $O(nl_{max})$, co może być znacząco większe niż wynosi rozmiar danych. Na przykład dla danych składających się z jednego słowa o długości $n$ i pozostałych słów o stałych długościach, niezależnych od $n$, dostajemy algorytm działający w czasie O(n^2), podczas gdy dane mają rozmiar $O(n)$. Jak widać, bezpośrednie stosowanie algorytmu dla słów o takich samych długościach nie daje oczekiwanych wyników. Możemy go jednak wykorzystać troszeczkę sprytniej. Zauważmy, że po wykonaniu fazy o numerze $i$ wszystkie słowa, których długości są krótsze niż $i$, znajdują się na samym początku uporządkowanego ciągu słów. Żeby je tam umieścić nie musimy ich sortować ze słowami o długościach co najmniej $i$. Dlatego zamiast tablicy indeksów słów będziemy słowa sortowane w danej fazie trzymać na liście słów $a$. Druga obserwacja dotyczy organizacji procesu sortowania. Zauważmy, że w algorytmie sortowania słów o tych samych długościach na początku każdej fazy zerujemy liczniki wystąpień symboli. Ponieważ dopuszczamy alfabet o rozmiarze rzędu $n$, to zerowanie liczników w każdej fazie prowadziłoby nadal do algorytmu kwadratowego ze względu na $n$. Więcej, nie możemy też obliczać sum prefiksowych w tablicy $t$ (krok 11) tak jak dotychczas, ponieważ to też dawałoby algorytm kwadratowy. Żeby temu zapobiec skorzystamy z pomysłu z sortowania kubełkowego. Użyjemy kubełków $B$ do rozrzucania słów. Żeby jednak nie inicjować w każdej fazie wszystkich kubełków, będziemy inicjować tylko te, które w danej fazie zostaną wykorzystane. W tym celu wystarczy, żebyśmy mieli w ręku uporządkowaną listę symboli z alfabetu, aktywnych w danej fazie - tzn. tych, które występują w słowach $w$ na pozycjach o numerach równych numerowi fazy. Podsumujmy zatem, co jest nam potrzebne, żeby nie wykonywać niepotrzebnych operacji podczas wykonywania jednej fazy. Niewątpliwie dla każdej fazy potrzebna jest lista numerów słów o długościach równych numerowi fazy. Takie słowa byłyby dołączane na początku listy słów uporządkowanych wcześniej, w fazach o większych numerach. Niech $L_{i}$ będzie listą numerów słów o długościach równych $i$. Taką listę łatwo stworzyć w czasie $O(n+l_{max})$ sortując leksykograficznie pary $(l_{i},i)$ - długość słowa i jego numer. Do tego celu można wykorzystać algorytm sortowania słów o tych samych długościach. Żeby otrzymać listy aktywnych symboli w fazach wystarczy posortować leksykograficznie wszystkie pary $(pozycja,symbol)$, otrzymane w wyniku przejrzenia wszystkich słów $w$. Takich par jest $\sum _{i=1}^{n}l_{i}$, a więc tyle, ile wynosi rozmiar danych. Znowu mamy do czynienia z sortowaniem słów o takich samych długościach. Takie sortowanie składa się z dwóch faz. W fazie o numerze 2 alfabet ma rozmiar $m$, natomiast w fazie o numerze 1 rozmiar alfabetu wynosi $l_{max}$. Tak więc sortowanie wykonuje się w czasie $O(\sum _{i=1}^{n}l_{i})$. Niech $S_{i}$ będzie uporządkowaną listą tych symboli z $\Sigma$, które występują na pozycji o numerze $i$ w słowach $w$. Możemy teraz przystąpić do opisu algorytmu sortowania słów zmiennej długości. Zakładamy, że listy $L_{i}$ oraz $S_{i}$ są już zbudowane.

Algorytm Sortowanie leksykograficzne słów o różnych długościach

---

 1  zainicjuj $a$ jako pustą listę;
 2  for $faza:=l_{max}$ downto 1 do 
 3  begin
 4    dla każdego symbolu $s$ z listy $S_{i}$ uczyń pustą listę $B[i]$;
 5    na początku listy $a$ umieść listę $L_{i}$;
 6    przeglądaj listę $a$ od początku do końca i każde słowo  
      z listy $a$ wstaw na koniec listy $B$ o numerze równej wartości symbolu z pozycji faza 
      w tym słowie;
 9    przeglądaj listy $B$ w kolejności numerów znajdujących się na liście
      $S_{i}$ i połącz je w jedną listę $a$, dopisując każdą kolejną listę  
      na koniec listy złożonej z dotychczas scalonych list;
 12 end;

Zauważmy, że każda faza w tym algorytmie jest wykonywana w czasie proporcjonalnym do liczby słów o długościach równych co najmniej numerowi tej fazy, co gwarantuje, że cały algorytm działa w czasie proporcjonalnym do $\sum _{i=1}^{n}l_{i}$, czyli w czasie liniowym.