Informatyka MIMUW

Czy można sortować szybciej niż w czasie \( O(n\log n) \)? 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\ge 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 (BucketSort)

for i := 0 to m-1 do
  zainicjuj B[i]  jako listę pustą; 
for  i := n downto 1 do 
  wstaw a[i] na początek listy B[a[i]]; 
scal listy B w jedną listę, dołączając listę B[i+1] po liście B[i]; 
wpisz kolejne 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

 //zliczanie wystąpień poszczególnych wartości w tablicy a 
for i := 0 to m-1 do  t[i] := 0; 
for j := 1 to n do t[a[j]] := t[a[j]] + 1; 
//obliczenie dla każdego i liczby elementów nie większych od i 
for i := 1 to m-1 do t[i] := t[i] + t[i-1]; 
//w tablicy posortowanej elementy o wartości i znajdują się 
//na pozycjach od t[i-1]+1 do  t[i], jeśli tylko przyjmiemy, że t[0] =  0 
//w sortowaniu wykorzystujemy pomocniczą tablicę b
//sortowane elementy umieszczamy w tablicy b na ich docelowych pozycjach 
for j := n downto 1 do 
begin 
  b[t[a[j]]] := a[j]; 
  t[a[j]] := t[a[j]] - 1; // t[a[j]] jest ostatnią wolną pozycją dla 
  //kolejnego (od końca) elementu o wartości a[j]  
end; 
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\le l \le 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

for j := 1 to n do 
  a[j] := j; 
for faza := k downto  1 do 
//sortowanie stabilnie słów  w[a[1]], w[a[2]],..., w[a[n]] 
//względem elementów z pozycji o numerze faza  
begin 
//sortowanie przez zliczanie 
  for i := 0 to m-1 do  t[i] := 0  
  for j := 1 to n do
    t[w[a[j]][faza]] := t[w[a[j]][faza]] + 1; 
  for i := 1 to m-1 do t[i] := t[i] + t[i-1]; 
  for j := n downto 1 do 
  begin 
    b[t[w[a[j]][faza]]] := a[j]; 
    t[w[a[j]][faza]] := t[w[a[j]][faza]] - 1 
  end; 
  a := b 
end

Po zakończeniu wykonywania powyższego algorytmu mamy \( w[a[1]]\le w[a[2]]\le \ldots \le w[a[n]] \). Analiza tego algorytmu jest niezmiernie prosta. Wykonujemy \( k \) faz. Czas działania każdej fazy wynosi \( O(n+m) \). Cały algorytm działa więc 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 \). Dostaliśmy więc 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 (ang. RadixSort).

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\ge 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 od rozmiaru 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

zainicjuj a jako pustą listę; 
for faza := l(max) downto 1 do 
begin 
  dla każdego symbolu s z listy S_i uczyń pustą listę B[i]; 
  na początku listy a umieść listę L_i; 
  przeglądaj listę a od początku do końca i każde napotkane słowo wstaw 
  na koniec listy B o numerze równej wartości symbolu z pozycji faza w tym słowie; 
  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; 
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.

Wszystkie rozważane dotychczas algorytmy sortowały porównując ze sobą elementy porządkowanego zbioru. 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 dla problemu sortowania - drzewa decyzyjne

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 \le i < j \le 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\} \), 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.

Niech \( S(n) \) oznacza minimalną liczbę porównań zawsze wystarczającą do posortowania \( n \) elementów. Liczbę \( S(n) \) można z dołu oszacować za pomocą drzewa decyzyjnego.

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 \( C(n)\ =\ \lceil \log n! \rceil \) porównań. Można pokazać, że \( \lceil \log n! \rceil \ge n\log n -1.45n \).

Zatem zachodzi

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.

Dokładne liczenie pesymistycznej liczby porównań dla problemu sortowania

Problem dokładnego wyznaczenia liczby \( S(n) \) jest jednym z fundamentalnych problemów w kombinatoryczno-algorytmicznej teorii sortowania. Hugo Steinhaus postawił ten problem w Kalejdoskopie matematycznym, nazywając go problemem turniejowym. Stąd bywa też nazywany problemem Steinhausa.

Knuth poświęcił duży fragment swojej klasycznej już książki The Art of Computer Programming (tom 3) problemowi optymalnego sortowania.

Ford Jr i Johnson odkryli algorytm (oznaczany dalej FJA), który wymaga liczby porównań bliskiej, a czasem dokładnie równej teoretycznej dolnej granicy \( C(n) \). Dla \( n\le11 \) niezależnie odkryli tę metodę również Trybuła i Czen. Oznaczmy przez \( F(n) \) liczbę porównań wymaganą przez FJA do posortowania \( n \) elementów.

Początkowe wartości \( C(n) \) i \( F(n) \) przedstawia tabela.

Jak widać, dla \( n\le11 \) i \( n=20,21 \) zachodzi \( F(n)=C(n) \), zatem FJA jest optymalny w tych przypadkach. Dla \( n=12,13,\ldots,19,22 \) mamy \( F(n)=C(n)+1 \). Prowadząc wyczerpujące obliczenia komputerowe, Wells odkrył, że \( S(12)=F(12)=30 \). Knuth postawił problem znalezienia następnej wartości \( S(13) \). Przypuszczał on, że \( S(13)=33 \) i \( S(14)=37 \). Udoskonalając metodę Wellsa i intensywnie wykorzystując obliczenia komputerowe, Marcin Peczarski (w swoich pracach magisterskiej i doktorskiej na Wydziale MIMUW) pokazał, że:

Aktualne wersje użytych programów można znaleźć na stronie Marcina Peczarskiego http://www.mimuw.edu.pl/~marpe.

Okazuje się zatem, że FJA jest optymalny dla \( n\le15 \) i \( n=20,21,22 \). Z drugiej strony najmniejszą liczbą elementów, dla której znamy algorytm lepszy od FJA jest 47. Schulte Mönting znalazł algorytm, który najpierw sortuje 5 elementów i 42 elementy za pomocą FJA, używając odpowiednio 7 i 171 porównań, a następnie scala posortowane ciągi za pomocą 22 dalszych porównań. Algorytm ten potrzebuje więc łącznie 200 porównań, podczas gdy FJA potrzebuje ich 201.

Wiadomo, że FJA nie jest optymalny dla nieskończenie wielu wartości \( n \), a wszystkie znane lepsze algorytmy są kombinacją sortowania i scalania. Za pomocą wyczerpującego przeszukiwania komputerowego Peczarski pokazał również, że 47 jest najmniejszą liczbą elementów, dla której istnieje algorytm typu: sortuj \( m \) i \( n-m \) elementów za pomocą FJA, a następnie scal posortowane ciągi, przy czym łączna liczba porównań jest mniejsza niż potrzebna do bezpośredniego posortowania \( n \) elementów za pomocą FJA.

Opiszemy teraz działanie FJA. Sortowanie \( n \) elementów \( u_1,u_2,\ldots,u_n \) za pomocą FJA można podzielić na 3 fazy.
Faza 1. Wykonujemy porównania dowolnie wybranych \( \lfloor n/2\rfloor \) rozłącznych par elementów. Powiedzmy, że są to porównania:

\( u_1\!:\!u_2,\ u_3\!:\!u_4,\ \ldots, \ u_{2\lfloor n/2\rfloor-1}\!:\!u_{2\lfloor n/2\rfloor}. \)

Gdy \( n \) jest liczbą nieparzystą, to element \( u_n \) nie jest w tej fazie porównywany.

Faza 2. Używając rekurencyjnie FJA, sortujemy \( \lfloor n/2\rfloor \) większych elementów znalezionych w fazie 1. Dostajemy posortowany ciąg elementów, który oznaczamy \( a_1,a_2,\ldots,a_{\lfloor n/2\rfloor} \). Przez \( b_i \) oznaczamy element, który był porównywany w fazie 1 z elementem \( a_i \) i okazał się od niego mniejszy. Gdy \( n \) jest liczbą nieparzystą, to element \( u_n \), który nie był porównywany w fazie 1 oznaczamy przez \( b_{\lceil n/2\rceil} \).

Faza 3. Elementy \( b_1,a_1,a_2,\ldots,a_{\lfloor n/2\rfloor} \) tworza ciąg posortowany, nazwijmy go łańcuchem głównym. Pozostałe elementy \( b_2,b_3,\ldots,b_{\lceil n/2\rceil} \) wstawiamy binarnie do łańcucha głównego w następującej kolejności:

\( b_3,b_2;\ b_5,b_4;\ b_{11},b_{10},\ldots,b_6;\ \ldots; \ b_{t_k},b_{t_k-1},\ldots,b_{t_{k-1}+1};\ \ldots, \)

gdzie \( t_k=(2^{k+1}+(-1)^k)/3 \). Kolejne wstawiane elementy wydłużają łańcuch główny. Przy czym element \( b_i \) dla \( i\le\lfloor n/2\rfloor \) jest wstawiany do tej części łańcucha głównego, gdzie są elementy mniejsze od \( a_i \).

Kolejność wstawianych elementów można zapamiętać za pomocą następującej reguły. Wypisujemy w wierszu kolejne potęgi liczby 2, poczynając od 4. Następnie w drugim wierszu wypisujemy liczby, poczynając od 1, tak by suma dwóch kolejnych liczb była równa liczbie znajdującej się nad lewą z nich w pierwszym wierszu. Wreszcie pod każdą liczbą z drugiego wiersza wypisujemy kolejne dodatnie liczby całkowite mniejsze od niej, ale większe od liczby znajdującej się w drugim wierszu w kolumnie bezpośrednio po lewej stronie.

Indeksy kolejnych wstawianych elementów odczytujemy w ten sposów, że pomijamy pierwszy wiersz i pierwszą kolumnę, a następnie odczytujemy liczby wypisane w kolejnych kolumnach od lewej do prawej, a w każdej kolumnie od góry do dołu.
Liczbę porównań wykonywanych przez FJA opisują ciekawe wzory, które można znależć np. we wspomnaienj wyżej książce Knutha.