Algorytmy i struktury danych/Dolne granice i sortowanie pozycyjne

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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ż .

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

Odpowiedź brzmi NIE.

Dolna granica

Załóżmy, że chcemy posortować różnych elementów i jedynym sposobem ustalenia porządku pomiędzy nimi jest porównywanie ich w parach. Wynikiem sortowania jest permutacja . Możliwych wyników sortowania jest oczywiście tyle, ile wszystkich permutacji zbioru -elementowego, czyli . 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 , . Każda taka para oznacza, że interesuje nas wynik porównania z . Jeśli wynikiem porównania jest TAK, co oznacza, że jest mniejsze od , 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 nie jest mniejsze od , 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 , 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.


Sortowanie.1.png

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 elementów jest drzewem binarnym o liściach. Najmniejsza wysokość drzewa binarnego o liściach wynosi . Wynika stąd, że każdy algorytm sortujący przez porównania wykonuje w pesymistycznym przypadku porównań. Można pokazać, że . Podobne dolne ograniczenie zachodzi, gdy pytamy o średnią liczbę porównań w modelu losowych permutacji, tzn. gdy każdy z wyników sortowania jest możliwy z jednakowym prawdopodobieństwem . W tym wykładzie pominiemy dowód tego faktu.

Sortowanie w czasie liniowym

Czy można sortować szybciej niż w czasie ? 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ę , jeśli wiemy, że jej elementami są liczby całkowite z przedziału dla pewnego . Jest wiele rozwiązań tego zadania. Jednym z nich jest tzw. sortowanie kubełkowe. Bierzemy kubełków . Do kubełka wrzucamy wszystkie elementy z tablicy o wartości równej . Następnie wypisujemy zawartości kubełków, poczynając od kubełka . Kubełki reprezentujemy jako listy jednokierunkowe. Oto dokładniejszy zapis algorytmu sortowania kubełkowego.

Algorytm Sortowanie kubełkowe (BucketSort)


 1  for  to  do
 2    zainicjuj  jako listę pustą; 
 3  for  downto 1 do
 4    wstaw  na początek listy ;
 5  scal listy  w jedną listę, dołączając listę 
    po liście ;
 6  wpisz kolejne elementy z posortowanej listy na kolejne pozycje w tablicy ;

Zauważmy, że przeglądanie tablicy od końca i wrzucanie jej elementów na początki list gwarantuje, że tablica 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 , kroki 3-4 w czasie , krok 5 można wykonać w czasie , jeśli pamiętamy wskaźniki na końce list, lub w czasie , gdy musimy przejrzeć każdą listę w poszukiwaniu jej końca. Krok 6 zabiera czas . Otrzymujemy zatem algorytm sortujący, który działa w czasie . Gdy jest rzędu co najwyżej , 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 zliczamy, ile razy pojawia się ona w tablicy . Taka informacja pozwala już łatwo określić pozycje elementów o wartości w posortowanej tablicy. W tym celu wystarczy wiedzieć, ile jest elementów o wartościach mniejszych. Elementy o tej samej wartości umieszczamy następnie na pozycjach docelowych, w kolejności ich początkowego występowania w tablicy . Oto formalny zapis algorytmu:

Algorytm Sortowanie przez zliczanie


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

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

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 jest uporządkowanym alfabetem -elementowym i danych jest słów nad alfabetem , każde o długości . Inaczej mówiąc, słowo jest tablicą o wartościach z . W porządku leksykograficznym jest mniejsze od wtedy i tylko wtedy, gdy istnieje takie, że dla każdego oraz . Algorytm sortowania leksykograficznego jest teraz bardzo prosty. W sortowaniu słowa są przetwarzane od końca. Algorytm jest wykonywany w fazach ponumerowanych malejąco . Przed rozpoczęciem fazy o numerze słowa są już uporządkowane leksykograficzne względem swoich sufiksów o długościach równych , czyli podsłów składających się ze znaków z pozycji . W fazie -tej sortujemy słowa stabilnie względem znaków z pozycji . Stabilność gwarantuje, że porządek słów, które posiadają te same elementy na pozycji -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 będziemy przechowywali indeksy słów uporządkowanych względem swoich sufiksów.

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


 1  for  to  do 
 2    ;
 3  for  downto 1 do 
 4  //sortowanie stabilnie słów  
 5  //względem elementów z pozycji o numerze 
 6  begin
 7  //sortowanie przez zliczanie 
 8    for  to  do ;
 9    for  to  do 
 10     ;
 11   for  to  do ;
 12   for  downto 1 do
 13   begin 
 14     ; 
 15     
 16   end;
 17   
 18  end

Po zakończeniu wykonywania powyższego algorytmu mamy . Analiza tego algorytmu jest niezmiernie prosta. Wykonujemy faz. Czas działania każdej fazy wynosi . Cały algorytm działa więc w czasie proporcjonalnym do . Dla rzędu co najwyżej mamy algorytm o złożoności . Zauważmy, że wielkość to rozmiar danych - słów, każde o długości . 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 . Zauważmy, że słowa nad alfabetem można interpretować jako liczby całkowite bez znaku zapisane w układzie pozycyjnym przy podstawie . 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 słów nad alfabetem . Dla dalszych rozważań przyjmijmy, że jest rzędu co najwyżej . Niech będzie długością -tego słowa. Zauważmy, że rozmiar danych w tym zadaniu wynosi . Będziemy chcieli, żeby nasz algorytm sortował słowa w czasie liniowym ze względu na tę wielkość. Niech 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 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 , 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 i pozostałych słów o stałych długościach, niezależnych od , dostajemy algorytm działający w czasie , podczas gdy dane mają rozmiar . 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 wszystkie słowa, których długości są krótsze niż , 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 . Dlatego zamiast tablicy indeksów słów będziemy słowa sortowane w danej fazie trzymać na liście słów . 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 , to zerowanie liczników w każdej fazie prowadziłoby nadal do algorytmu kwadratowego ze względu na . Więcej, nie możemy też obliczać sum prefiksowych w tablicy (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 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 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 będzie listą numerów słów o długościach równych . Taką listę łatwo stworzyć w czasie sortując leksykograficznie pary - 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 , otrzymane w wyniku przejrzenia wszystkich słów . Takich par jest , 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 , natomiast w fazie o numerze 1 rozmiar alfabetu wynosi . Tak więc sortowanie wykonuje się w czasie . Niech będzie uporządkowaną listą tych symboli z , które występują na pozycji o numerze w słowach . Możemy teraz przystąpić do opisu algorytmu sortowania słów zmiennej długości. Zakładamy, że listy oraz są już zbudowane.

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


 1  zainicjuj  jako pustą listę;
 2  for  downto 1 do 
 3  begin
 4    dla każdego symbolu  z listy  uczyń pustą listę ;
 5    na początku listy  umieść listę ;
 6    przeglądaj listę  od początku do końca i każde napotkane słowo wstaw 
      na koniec listy  o numerze równej wartości symbolu z pozycji faza 
      w tym słowie;
 9    przeglądaj listy  w kolejności numerów znajdujących się na liście
       i połącz je w jedną listę , 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 , czyli w czasie liniowym.