Algorytmy i struktury danych/Dolne granice i sortowanie pozycyjne

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

Załóżmy, że chcemy posortować $n$ różnych elementów $x_{1}, \dots, 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}} < \dots < 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}, \dots, 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.

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 $⌈ \log k ⌉$ . Wynika stąd, że każdy algorytm sortujący przez porównania wykonuje w pesymistycznym przypadku $⌈ \log n! ⌉$ porównań. Można pokazać, że $⌈ \log n! ⌉ \geq n \log n - 1.45 n$ . 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)$ ? 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 (BucketSort)

 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 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, \dots, 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 $Σ = {0 < 1 < . . . < m - 1}$ jest uporządkowanym alfabetem $m$ -elementowym i danych jest $n$ słów $w [1], w [2], \dots, w [n]$ nad alfabetem $Σ$ , 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 $Σ$ . 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, \dots, 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, \dots, 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 [j] : = j$ ;
 3  for  $f a z a : = k$  downto 1 do 
 4  //sortowanie stabilnie słów  $w [a [1]], w [a [2]], \dots, w [a [n]]$  
 5  //względem elementów z pozycji o numerze  $f a z a$ 
 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]] [f a z a]] : = t [w [a [j]] [f a z a]] + 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]] [f a z a]]] : = a [j]$ ; 
 15      $t [w [a [j]] [f a z a]] : = t [w [a [j]] [f a z a]] - 1$ 
 16   end;
 17    $a : = b$ 
 18  end

Po zakończeniu wykonywania powyższego algorytmu mamy $w [a [1]] \leq w [a [2]] \leq \dots \leq 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 $k n + k m$ . Dla $m$ rzędu co najwyżej $n$ mamy algorytm o złożoności $O (k n)$ . Zauważmy, że wielkość $k n$ 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 $Σ = {0, \dots, 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}, \dots, w_{n}$ nad alfabetem $Σ = {0, 1, \dots, 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_{m a x}$ 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_{m a x}$ symbolem, który będzie traktowany jako mniejszy od każdego symbolu z $Σ$ . W naszym przypadku tym symbolem może być po prostu -1. Niestety takie podejście daje algorytm, którego czas działania wynosi $O (n l_{m a x})$ , 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_{m a x})$ 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 $(p o z y c j a, s y m b o l)$ , 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_{m a x}$ . 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 $Σ$ , 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  $f a z a : = l_{m a x}$  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 napotkane słowo 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.

Algorytmy i struktury danych/Dolne granice i sortowanie pozycyjne

Dolna granica

Sortowanie w czasie liniowym

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia