Algorytmy i struktury danych/Dolne granice i sortowanie pozycyjne: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
 
(Nie pokazano 39 wersji utworzonych przez 5 użytkowników)
Linia 1: Linia 1:
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ż <math>n\log n</math>.
 
 
Czy za pomocą porównań można sortować istotnie szybciej?
 
 
Odpowiedź brzmi NIE.
 
 
==Dolna granica==
 
 
Załóżmy, że chcemy posortować <math>n</math> różnych elementów <math>x_1, \ldots, x_n</math> i jedynym sposobem ustalenia porządku pomiędzy nimi jest porównywanie ich w parach. Wynikiem sortowania jest permutacja <math>x_{i_1} < x_{i_2} < \ldots < x_{i_n}</math>. Możliwych wyników sortowania jest oczywiście tyle, ile wszystkich permutacji zbioru <math>n</math>-elementowego, czyli <math>n!</math>. 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 <math>i:j</math>, <math>1 \le i < j \le n</math>. Każda taka para <math>i:j</math> oznacza, że interesuje nas wynik porównania <math>x_i</math> z <math>x_j</math>. Jeśli wynikiem porównania jest TAK, co oznacza, że <math>x_i</math> jest mniejsze od <math>x_j</math>, 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 <math>x_i</math> nie jest mniejsze od <math>x_j</math>, 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 <math>\{x_1,x_2,\ldots,x_n\}</math>, 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.
 
 
 
<center>[[Grafika:sortowanie.1.png]]</center>
 
 
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 <math>n</math>-elementów jest drzewem binarnym o <math>n!</math> liściach. Najmniejsza wysokość drzewa binarnego o <math>k</math> liściach wynosi <math>\lceil \log k \rceil</math>. Wynika stąd, że każdy algorytm sortujący przez porównania wykonuje w pesymistycznym przypadku <math>\lceil \log n! \rceil</math> porónań. Można pokazać, że  <math>\lceil \log n! \rceil \ge n\log n -1.45n</math>.
 
Podobne dolne ograniczenie zachodzi, gdy pytamy o średnią liczbę porównań w modelu losowych permutacji, tzn. gdy każdy z <math>n!</math> wyników sortowania jest możliwy z jednakowym prawdopodobieństwem <math>\frac{1}{n!}</math>. W tym wykładzie pominiemy dowód tego faktu.
 
 
 
==Sortowanie w czasie liniowym==
 
==Sortowanie w czasie liniowym==
  
Czy można sortować szybciej niż w czasie <math>O(n\log n)</math>. 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ę <math>a[1..n]</math>, jeśli wiemy, że jej elementami są liczby całkowite z przedziału <math>0..m-1</math>, dla pewnego <math>m\ge 1</math>. Jest wiele rozwiązań tego zadania. Jednym z nich jest tzw. sortowanie kubełkowe. Bierzemy <math>m</math> kubełków <math>B[0..m-1]</math>. Do kubełka <math>B[i]</math> wrzucamy wszystkie elementy z tablicy <math>a</math> o wartości równej <math>i</math>. Następnie wypisujemy zawartości kubełków, poczynając od kubełka <math>B[0]</math>. Kubełki reprezentujemy jako listy jednokierunkowe. Oto dokładniejszy zapis algorytmu sortowania kubełkowego.
+
Czy można sortować szybciej niż w czasie <math>O(n\log n)</math>? 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ę <math>a[1..n]</math>, jeśli wiemy, że jej elementami są liczby całkowite z przedziału <math>0..m-1</math> dla pewnego <math>m\ge 1</math>. Jest wiele rozwiązań tego zadania. Jednym z nich jest tzw. sortowanie kubełkowe. Bierzemy <math>m</math> kubełków <math>B[0..m-1]</math>. Do kubełka <math>B[i]</math> wrzucamy wszystkie elementy z tablicy <math>a</math> o wartości równej <math>i</math>. Następnie wypisujemy zawartości kubełków, poczynając od kubełka <math>B[0]</math>. Kubełki reprezentujemy jako listy jednokierunkowe. Oto dokładniejszy zapis algorytmu sortowania kubełkowego.
  
{{algorytm|Sortowanie kubełkowe||
+
{{algorytm|Sortowanie kubełkowe (BucketSort)||
 
   1  '''for''' <math>i := 0</math> '''to''' <math>m-1</math> '''do'''
 
   1  '''for''' <math>i := 0</math> '''to''' <math>m-1</math> '''do'''
 
   2    zainicjuj <math>B[i]</math> jako listę pustą;  
 
   2    zainicjuj <math>B[i]</math> jako listę pustą;  
Linia 26: Linia 10:
 
   5  scal listy <math>B</math> w jedną listę, dołączając listę <math>B[i+1]</math>
 
   5  scal listy <math>B</math> w jedną listę, dołączając listę <math>B[i+1]</math>
 
     po liście <math>B[i]</math>;
 
     po liście <math>B[i]</math>;
   6  wpisz po kolei elementy z posortowanej listy na kolejne pozycje w tablicy <math>a</math>;
+
   6  wpisz kolejne elementy z posortowanej listy na kolejne pozycje w tablicy <math>a</math>;
 
}}
 
}}
  
Zauważmy, że przeglądanie tablicy <math>a</math> od końca i wrzucanie jej elementów na początki list <math>B</math> gwarantuje, że tablica <math>a</math> 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 <math>O(m)</math>, kroki 3-4 w czasie <math>O(n)</math>, krok 5 można wykonać w czasie O(m), jeśli pamiętamy wskaźniki na końce list, lub w czasie <math>O(n+m)</math>, gdy musimy przejrzeć każdą listę w poszukiwaniu jej końca. Krok 6 zabiera czas <math>O(n)</math>. Otrzymujemy zatem algorytm sortujący, który działa w czasie <math>O(n+m)</math>. Gdy <math>m</math> jest rzędu co najwyżej <math>n</math> nasz algorytmy wykonuje tylko liniową liczbę operacji!
+
Zauważmy, że przeglądanie tablicy <math>a</math> od końca i wrzucanie jej elementów na początki list <math>B</math> gwarantuje, że tablica <math>a</math> 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 <math>O(m)</math>, kroki 3-4 w czasie <math>O(n)</math>, krok 5 można wykonać w czasie <math>O(m)</math>, jeśli pamiętamy wskaźniki na końce list, lub w czasie <math>O(n+m)</math>, gdy musimy przejrzeć każdą listę w poszukiwaniu jej końca. Krok 6 zabiera czas <math>O(n)</math>. Otrzymujemy zatem algorytm sortujący, który działa w czasie <math>O(n+m)</math>. Gdy <math>m</math> jest rzędu co najwyżej <math>n</math>, 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 <math>i = 0, 1, \ldots, m-1</math> zliczamy ile razy pojawia się ona w tablicy <math>a[1..n]</math>. Taka informacja pozwala już łatwo określić pozycje elementów o wartości <math>i</math> w posortowanej tablicy. W tym celu wystarczy wiedzieć ile jest elementów o wartościach mniejszych. Elementy o tej samej wartości <math>i</math> umieszczamy następnie na pozycjach docelowych, w kolejności ich początkowego występowania w tablicy <math>a</math>. Oto formalny zapis algorytmu:
+
Ten sam wynik można osiągnąć za pomocą sortowania przez zliczanie. W tym algorytmie dla każdej wartości <math>i = 0, 1, \ldots, m-1</math> zliczamy, ile razy pojawia się ona w tablicy <math>a[1..n]</math>. Taka informacja pozwala już łatwo określić pozycje elementów o wartości <math>i</math> w posortowanej tablicy. W tym celu wystarczy wiedzieć, ile jest elementów o wartościach mniejszych. Elementy o tej samej wartości <math>i</math> umieszczamy następnie na pozycjach docelowych, w kolejności ich początkowego występowania w tablicy <math>a</math>. Oto formalny zapis algorytmu:
  
{{algorytm|Sortowanie przez zliczanie||
+
{{algorytm|Sortowanie przez zliczanie|CountSort|
 
   1  //zliczanie wystąpień poszczególnych wartości w tablicy <math>a</math>
 
   1  //zliczanie wystąpień poszczególnych wartości w tablicy <math>a</math>
 
   2  '''for''' <math>i := 0</math> '''to''' <math>m-1</math> '''do''' <math>t[i] := 0</math>;
 
   2  '''for''' <math>i := 0</math> '''to''' <math>m-1</math> '''do''' <math>t[i] := 0</math>;
Linia 52: Linia 36:
 
}}
 
}}
  
Podobnie jak w sortowaniu kubełkowym nasz algorytm działa w czasie <math>O(n+m)</math> i jest algorytmem liniowym dla każdego <math>m</math>, które jest rzędu co najwyżej <math>n</math>.
+
Podobnie jak w sortowaniu kubełkowym nasz algorytm działa w czasie <math>O(n+m)</math> i jest algorytmem liniowym dla każdego <math>m</math>, które jest rzędu co najwyżej <math>n</math>.
  
 
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 <math>\Sigma = \{0 < 1 <... < m-1\}</math> jest uporządkowanym alfabetem <math>m</math>-elementowym i danych jest <math>n</math> słów <math>w[1], w[2], \ldots, w[n]</math> nad alfabetem <math>\Sigma</math>, każde o długości <math>k</math>. Inaczej mówiąc, słowo <math>w[i]</math> jest tablicą <math>w[i][1..k]</math> o wartościach z <math>\Sigma</math>. W porządku leksykograficznym <math>w[i]</math> jest mniejsze od <math>w[j]</math> wtedy i tylko wtedy, gdy istnieje <math>1\le l \le k</math> takie, że <math>w[i][s] = w[j][s]</math> dla każdego <math>s = 1,2,...,l-1</math> oraz <math>w[i][l] < w[j][l]</math>. Algorytm sortowania leksykograficznego jest teraz bardzo prosty. W sortowaniu słowa są przetwarzane od końca. Algorytm jest wykonywany w <math>k</math> fazach ponumerowanych malejąco <math>k, k-1, \ldots,1</math>. Przed rozpoczęciem fazy o numerze <math>i</math> słowa <math>w</math> są już uporządkowane leksykograficzne względem swoich sufiksów o długościach równych <math>k-i</math>, czyli podsłów składających się ze znaków z pozycji <math>i+1,i+2,\ldots,k</math>. W fazie <math>i</math>-tej sortujemy słowa <math>w</math> stabilnie względem znaków z pozycji <math>i</math>. Stabilność gwarantuje, że porządek słów, które posiadają te same elementy na pozycji <math>i</math>-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 <math>a</math> będziemy przechowywali indeksy słów <math>w</math> uporządkowanych względem swoich sufiksów.
 
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 <math>\Sigma = \{0 < 1 <... < m-1\}</math> jest uporządkowanym alfabetem <math>m</math>-elementowym i danych jest <math>n</math> słów <math>w[1], w[2], \ldots, w[n]</math> nad alfabetem <math>\Sigma</math>, każde o długości <math>k</math>. Inaczej mówiąc, słowo <math>w[i]</math> jest tablicą <math>w[i][1..k]</math> o wartościach z <math>\Sigma</math>. W porządku leksykograficznym <math>w[i]</math> jest mniejsze od <math>w[j]</math> wtedy i tylko wtedy, gdy istnieje <math>1\le l \le k</math> takie, że <math>w[i][s] = w[j][s]</math> dla każdego <math>s = 1,2,...,l-1</math> oraz <math>w[i][l] < w[j][l]</math>. Algorytm sortowania leksykograficznego jest teraz bardzo prosty. W sortowaniu słowa są przetwarzane od końca. Algorytm jest wykonywany w <math>k</math> fazach ponumerowanych malejąco <math>k, k-1, \ldots,1</math>. Przed rozpoczęciem fazy o numerze <math>i</math> słowa <math>w</math> są już uporządkowane leksykograficzne względem swoich sufiksów o długościach równych <math>k-i</math>, czyli podsłów składających się ze znaków z pozycji <math>i+1,i+2,\ldots,k</math>. W fazie <math>i</math>-tej sortujemy słowa <math>w</math> stabilnie względem znaków z pozycji <math>i</math>. Stabilność gwarantuje, że porządek słów, które posiadają te same elementy na pozycji <math>i</math>-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 <math>a</math> będziemy przechowywali indeksy słów <math>w</math> uporządkowanych względem swoich sufiksów.
Linia 58: Linia 42:
 
{{algorytm|Sortowanie leksykograficzne słów o tych samych długościach||
 
{{algorytm|Sortowanie leksykograficzne słów o tych samych długościach||
 
   1  '''for''' <math>j := 1</math> '''to''' <math>n</math> '''do'''  
 
   1  '''for''' <math>j := 1</math> '''to''' <math>n</math> '''do'''  
   2    <math>a[i] := i</math>;
+
   2    <math>a[j] := j</math>;
 
   3  '''for''' <math>faza := k</math> '''downto''' 1 '''do'''  
 
   3  '''for''' <math>faza := k</math> '''downto''' 1 '''do'''  
 
   4  //sortowanie stabilnie słów <math>w[a[1]], w[a[2]],\ldots, w[a[n]]</math>  
 
   4  //sortowanie stabilnie słów <math>w[a[1]], w[a[2]],\ldots, w[a[n]]</math>  
Linia 71: Linia 55:
 
   13  '''begin'''  
 
   13  '''begin'''  
 
   14    <math>b[t[w[a[j]][faza]]] := a[j]</math>;  
 
   14    <math>b[t[w[a[j]][faza]]] := a[j]</math>;  
   15    <math>t[w[a[j]][faza]] := t[w[a[j]][faza]] - 1</math>;
+
   15    <math>t[w[a[j]][faza]] := t[w[a[j]][faza]] - 1</math>
 
   16  '''end''';
 
   16  '''end''';
 
   17  <math> a := b </math>
 
   17  <math> a := b </math>
Linia 77: Linia 61:
 
}}
 
}}
  
Po zakończeniu wykonywania powyższego algorytmu mamy <math>w[a[1]]\le w[a[2]]\le \ldots \le w[a[n]]</math>. Analiza tego algorytmu jest niezmiernie prosta. Wykonujemy <math>k</math> faz. Czas działania każdej fazy wynosi <math>O(n+m)</math>. Tak więc cały algorytm działa w czasie proporcjonalnym do <math>kn + km</math>. Dla <math>m</math> rzędu co najwyżej <math>n</math> mamy algorytm o złożoności <math>O(kn)</math>. Zauważmy, że wielkość <math>kn</math> to rozmiar danych - <math>n</math> słów, każde o długości <math>k</math>. 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 <math>n</math>.  
+
Po zakończeniu wykonywania powyższego algorytmu mamy <math>w[a[1]]\le w[a[2]]\le \ldots \le w[a[n]]</math>. Analiza tego algorytmu jest niezmiernie prosta. Wykonujemy <math>k</math> faz. Czas działania każdej fazy wynosi <math>O(n+m)</math>. Cały algorytm działa więc w czasie proporcjonalnym do <math>kn + km</math>. Dla <math>m</math> rzędu co najwyżej <math>n</math> mamy algorytm o złożoności <math>O(kn)</math>. Zauważmy, że wielkość <math>kn</math> to rozmiar danych - <math>n</math> słów, każde o długości <math>k</math>. 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 <math>n</math>.  
Zauważmy, że słowa nad alfabetem <math>\Sigma = \{0,\ldots, m-1\}</math> można interpretować jako liczby całkowite bez znaku zapisane w układzie pozycyjnym przy podstawie <math>m</math>. Dlatego uprawnione jest mówić w tym miejscu o ‘’’sortowaniu pozycyjnym’’’.
+
Zauważmy, że słowa nad alfabetem <math>\Sigma = \{0,\ldots, m-1\}</math> można interpretować jako liczby całkowite bez znaku zapisane w układzie pozycyjnym przy podstawie <math>m</math>. 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.
 
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 <math>n</math> słów <math>w_1, w_2, \ldots, w_n</math> nad alfabetem <math>\Sigma = \{0,1,\ldots, m-1\}</math>. Dla dalszych rozważań przyjmijmy, że <math>m</math> jest rzędu co najwyżej <math>n</math>. Niech <math>l_i\ge 1</math> będzie długością <math>i</math>-tego słowa. Zauważmy, że rozmiar danych w tym zadaniu wynosi <math>\sum_{i=1}^n l_i</math>. Będziemy chcieli, żeby nasz algorytm sortował słowa <math>w</math> w czasie liniowym ze względu na tę wielkość. Niech <math>l_{max}</math> 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 <math>l_{max}</math> symbolem, który będzie traktowany jako mniejszy od każdego symbolu z <math>\Sigma</math>. W naszym przypadku tym symbolem może być po prostu -1. Niestety takie podejście daje algorytm, którego czas działania wynosi <math>O(nl_{max})</math>, 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 <math>n</math> i pozostałych słów o stałych długościach, niezależnych od <math>n</math>, dostajemy algorytm działający w czasie O(n^2), podczas gdy dane mają rozmiar <math>O(n)</math>. 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 <math>i</math> wszystkie słowa, których długości są krótsze niż <math>i</math>, 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 <math>i</math>. Dlatego zamiast tablicy indeksów słów będziemy słowa sortowane w danej fazie trzymać na liście słów <math>a</math>. 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 <math>n</math>, to zerowanie liczników w każdej fazie prowadziłoby nadal do algorytmu kwadratowego ze względu na <math>n</math>. Więcej, nie możemy też obliczać sum prefiksowych w tablicy <math>t</math> (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 <math>B</math> 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 <math>w</math> 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 <math>L_i</math> będzie listą numerów słów o długościach równych <math>i</math>. Taką listę łatwo stworzyć w czasie <math>O(n+l_{max})</math> sortując leksykograficznie pary <math>(l_i,i)</math> - 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 <math>(pozycja,symbol)</math>, otrzymane w wyniku przejrzenia wszystkich słów <math>w</math>. Takich par jest <math>\sum_{i = 1}^n l_i</math>, 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 <math>m</math>, natomiast w fazie o numerze 1 rozmiar alfabetu wynosi <math>l_{max}</math>. Tak więc sortowanie wykonuje się w czasie <math>O(\sum_{i = 1}^n l_i)</math>. Niech <math>S_i</math> będzie uporządkowaną listą tych symboli z <math>\Sigma</math>, które występują na pozycji o numerze <math>i</math> w słowach <math>w</math>.  
+
Załóżmy, że chcemy posortować leksykograficznie <math>n</math> słów <math>w_1, w_2, \ldots, w_n</math> nad alfabetem <math>\Sigma = \{0,1,\ldots, m-1\}</math>. Dla dalszych rozważań przyjmijmy, że <math>m</math> jest rzędu co najwyżej <math>n</math>. Niech <math>l_i\ge 1</math> będzie długością <math>i</math>-tego słowa. Zauważmy, że rozmiar danych w tym zadaniu wynosi <math>\sum_{i=1}^n l_i</math>. Będziemy chcieli, żeby nasz algorytm sortował słowa <math>w</math> w czasie liniowym ze względu na tę wielkość. Niech <math>l_{max}</math> 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 <math>l_{max}</math> symbolem, który będzie traktowany jako mniejszy od każdego symbolu z <math>\Sigma</math>. W naszym przypadku tym symbolem może być po prostu -1. Niestety takie podejście daje algorytm, którego czas działania wynosi <math>O(nl_{max})</math>, 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 <math>n</math> i pozostałych słów o stałych długościach, niezależnych od <math>n</math>, dostajemy algorytm działający w czasie <math>O(n^2)</math>, podczas gdy dane mają rozmiar <math>O(n)</math>. 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 <math>i</math> wszystkie słowa, których długości są krótsze niż <math>i</math>, 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 <math>i</math>. Dlatego zamiast tablicy indeksów słów będziemy słowa sortowane w danej fazie trzymać na liście słów <math>a</math>. 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 <math>n</math>, to zerowanie liczników w każdej fazie prowadziłoby nadal do algorytmu kwadratowego ze względu na <math>n</math>. Więcej, nie możemy też obliczać sum prefiksowych w tablicy <math>t</math> (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 <math>B</math> 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 <math>w</math> 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 <math>L_i</math> będzie listą numerów słów o długościach równych <math>i</math>. Taką listę łatwo stworzyć w czasie <math>O(n+l_{max})</math> sortując leksykograficznie pary <math>(l_i,i)</math> - 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 <math>(pozycja,symbol)</math>, otrzymane w wyniku przejrzenia wszystkich słów <math>w</math>. Takich par jest <math>\sum_{i = 1}^n l_i</math>, 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 <math>m</math>, natomiast w fazie o numerze 1 rozmiar alfabetu wynosi <math>l_{max}</math>. Tak więc sortowanie wykonuje się w czasie <math>O(\sum_{i = 1}^n l_i)</math>. Niech <math>S_i</math> będzie uporządkowaną listą tych symboli z <math>\Sigma</math>, które występują na pozycji o numerze <math>i</math> w słowach <math>w</math>.  
 
Możemy teraz przystąpić do opisu algorytmu sortowania słów zmiennej długości. Zakładamy, że listy <math>L_i</math> oraz <math>S_i</math> są już zbudowane.
 
Możemy teraz przystąpić do opisu algorytmu sortowania słów zmiennej długości. Zakładamy, że listy <math>L_i</math> oraz <math>S_i</math> są już zbudowane.
  
Linia 90: Linia 74:
 
   4    dla każdego symbolu <math>s</math> z listy <math>S_i</math> uczyń pustą listę <math>B[i]</math>;
 
   4    dla każdego symbolu <math>s</math> z listy <math>S_i</math> uczyń pustą listę <math>B[i]</math>;
 
   5    na początku listy <math>a</math> umieść listę <math>L_i</math>;
 
   5    na początku listy <math>a</math> umieść listę <math>L_i</math>;
   6    przeglądaj listę <math>a</math> od początku do końca i każde słowo
+
   6    przeglądaj listę <math>a</math> od początku do końca i każde napotkane słowo wstaw
       z listy <math>a</math> wstaw na koniec listy <math>B</math> o numerze równej wartości symbolu z pozycji ''faza''  
+
       na koniec listy <math>B</math> o numerze równej wartości symbolu z pozycji ''faza''  
 
       w tym słowie;
 
       w tym słowie;
 
   9    przeglądaj listy <math>B</math> w kolejności numerów znajdujących się na liście
 
   9    przeglądaj listy <math>B</math> w kolejności numerów znajdujących się na liście
Linia 100: Linia 84:
  
 
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 <math>\sum_{i = 1}^n l_i</math>, czyli w czasie liniowym.
 
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 <math>\sum_{i = 1}^n l_i</math>, 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ż <math>n\log n</math>.
 +
 +
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ć <math>n</math> różnych elementów <math>x_1, \ldots, x_n</math> i jedynym sposobem ustalenia porządku pomiędzy nimi jest porównywanie ich w parach. Wynikiem sortowania jest permutacja <math>x_{i_1} < x_{i_2} < \ldots < x_{i_n}</math>. Możliwych wyników sortowania jest oczywiście tyle, ile wszystkich permutacji zbioru <math>n</math>-elementowego, czyli <math>n!</math>. Każdy algorytm sortowania przez porównania można zapisać za pomocą drzewa decyzyjnego.
 +
<br>
 +
 +
'''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 <math>i:j</math>, <math>1 \le i < j \le n</math>. Każda taka para <math>i:j</math> oznacza, że interesuje nas wynik porównania <math>x_i</math> z <math>x_j</math>. Jeśli wynikiem porównania jest TAK, co oznacza, że <math>x_i</math> jest mniejsze od <math>x_j</math>, 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 <math>x_i</math> nie jest mniejsze od <math>x_j</math>, 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 <math>\{x_1,x_2,\ldots,x_n\}</math>, stosowna permutacja wyznaczająca ten porządek znajduje się właśnie w liściu na końcu ścieżki.
 +
<br>
 +
 +
Na rysunku poniżej przedstawiono sortujące drzewo decyzyjne dla 3 elementów.
 +
 +
 +
<center>[[Grafika:sortowanie.1.png]]</center>
 +
 +
 +
<br>
 +
Niech <math>S(n)</math>  oznacza minimalną liczbę porównań  zawsze wystarczającą
 +
do posortowania <math>n</math> elementów. Liczbę <math>S(n)</math> można z dołu oszacować za pomocą drzewa decyzyjnego.
 +
 +
<br>
 +
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 <math>n</math> elementów jest drzewem binarnym o <math>n!</math> liściach. Najmniejsza wysokość drzewa binarnego o <math>k</math> liściach wynosi <math>\lceil \log k \rceil</math>. Wynika stąd, że każdy algorytm sortujący przez porównania wykonuje w pesymistycznym przypadku <math>C(n)= \lceil \log n! \rceil</math> porównań. Można pokazać, że  <math>\lceil \log n! \rceil \ge n\log n -1.45n</math>.
 +
 +
<br> Zatem zachodzi <br>
 +
<center>
 +
<math> S(n)\ge C(n)= \lceil \log n! \rceil\ \ge \ n\log n -1.45n</math>
 +
</center>
 +
<br>
 +
 +
Podobne dolne ograniczenie zachodzi, gdy pytamy o średnią liczbę porównań w modelu losowych permutacji, tzn. gdy każdy z <math>n!</math> wyników sortowania jest możliwy z jednakowym prawdopodobieństwem <math>\frac{1}{n!}</math>. W tym wykładzie pominiemy dowód tego faktu.
 +
 +
 +
<br>
 +
 +
==Dokładne liczenie pesymistycznej liczby porównań  dla problemu sortowania ==
 +
Problem dokładnego wyznaczenia liczby <math>S(n)</math> 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 <math>C(n)</math>.
 +
Dla <math>n\le11</math> niezależnie odkryli tę metodę również Trybuła i Czen.
 +
Oznaczmy przez <math>F(n)</math> liczbę porównań wymaganą przez FJA do posortowania <math>n</math>
 +
elementów.
 +
 +
Początkowe wartości <math>C(n)</math> i <math>F(n)</math> przedstawia tabela.
 +
 +
<br>
 +
<center>
 +
<math>
 +
\begin{array}{|c|ccccccccccccccccccccc|}
 +
\hline
 +
n &1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20&21&22\\
 +
C(n) &0&1&3&5&7&10&13&16&19&22&26&29&33&37&41&45&49&53&57&62&66&70\\
 +
F(n) &0&1&3&5&7&10&13&16&19&22&26&30&34&38&42&46&50&54&58&62&66&71\\
 +
\hline
 +
\end{array}
 +
</math>
 +
</center>
 +
<br>
 +
 +
Jak widać, dla <math>n\le11</math> i <math>n=20,21</math> zachodzi <math>F(n)=C(n)</math>,
 +
zatem FJA jest optymalny w tych przypadkach.
 +
Dla <math>n=12,13,\ldots,19,22</math> mamy <math>F(n)=C(n)+1</math>.
 +
Prowadząc wyczerpujące obliczenia komputerowe, Wells odkrył,
 +
że <math>S(12)=F(12)=30</math>.
 +
Knuth postawił problem znalezienia następnej wartości <math>S(13)</math>.
 +
Przypuszczał on, że <math>S(13)=33</math> i <math>S(14)=37</math>.
 +
Udoskonalając metodę Wellsa i  intensywnie wykorzystując obliczenia
 +
komputerowe, Marcin Peczarski (w swoich pracach magisterskiej i doktorskiej na Wydziale MIMUW)
 +
pokazał, że:
 +
 +
<br>
 +
<center><math>S(13)=34</math>, <math>S(14)=38</math>, <math>S(15)=42</math>
 +
i <math>S(22)=71</math>.</center>
 +
<br>
 +
 +
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 <math>n\le15</math> i <math>n=20,21,22</math>.
 +
Z drugiej strony najmniejszą liczbą elementów, dla której znamy algorytm lepszy od FJA jest 47.
 +
Schulte M&ouml;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 <math>n</math>,
 +
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 <math>m</math> i <math>n-m</math>
 +
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 <math>n</math> elementów za pomocą FJA.
 +
 +
Opiszemy teraz działanie FJA.
 +
Sortowanie <math>n</math> elementów <math>u_1,u_2,\ldots,u_n</math> za pomocą FJA można podzielić na
 +
3 fazy.
 +
 +
'''Faza 1.'''
 +
Wykonujemy porównania dowolnie wybranych <math>\lfloor n/2\rfloor</math> rozłącznych
 +
par elementów.
 +
Powiedzmy, że są to porównania:
 +
 +
<br>
 +
<center><math>u_1\!:\!u_2,\ u_3\!:\!u_4,\ \ldots,
 +
\ u_{2\lfloor n/2\rfloor-1}\!:\!u_{2\lfloor n/2\rfloor}.</math></center>
 +
<br>
 +
 +
Gdy <math>n</math> jest liczbą nieparzystą, to element <math>u_n</math> nie jest w tej fazie
 +
porównywany.
 +
 +
'''Faza 2.'''
 +
Używając rekurencyjnie FJA,
 +
sortujemy <math>\lfloor n/2\rfloor</math> większych elementów znalezionych w fazie 1.
 +
Dostajemy posortowany ciąg elementów, który oznaczamy
 +
<math>a_1,a_2,\ldots,a_{\lfloor n/2\rfloor}</math>.
 +
Przez <math>b_i</math> oznaczamy element, który był porównywany w fazie 1 z elementem
 +
<math>a_i</math> i okazał się od niego mniejszy.
 +
Gdy <math>n</math> jest liczbą nieparzystą, to element <math>u_n</math>, który nie był porównywany
 +
w fazie 1 oznaczamy przez <math>b_{\lceil n/2\rceil}</math>.
 +
 +
'''Faza 3.'''
 +
Elementy <math>b_1,a_1,a_2,\ldots,a_{\lfloor n/2\rfloor}</math> tworza ciąg posortowany,
 +
nazwijmy go łańcuchem głównym.
 +
Pozostałe elementy <math>b_2,b_3,\ldots,b_{\lceil n/2\rceil}</math> wstawiamy binarnie do
 +
łańcucha głównego w następującej kolejności:
 +
 +
<br>
 +
<center><math>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,</math></center>
 +
<br>
 +
 +
gdzie <math>t_k=(2^{k+1}+(-1)^k)/3</math>.
 +
Kolejne wstawiane elementy wydłużają łańcuch główny.
 +
Przy czym element <math>b_i</math> dla <math>i\le\lfloor n/2\rfloor</math> jest wstawiany do tej
 +
części łańcucha głównego, gdzie są elementy mniejsze od <math>a_i</math>.
 +
 +
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.
 +
 +
<br>
 +
<center>
 +
<math>
 +
\begin{array}{ccccccccccccc}
 +
4& &8& &16& &32& &64& &128& &\ldots\\
 +
1& &3& &5& &11& &21& &43& &\ldots\\
 +
& &2& &4& &10& &20& &42\\
 +
& & & & & &9& &19& &41\\
 +
& & & & & &8& &18& &40\\
 +
& & & & & &7& &17& &39\\
 +
& & & & & &6& &16& &38\\
 +
& & & & & & & &\vdots& &\vdots\\
 +
& & & & & & & &12& &34\\
 +
& & & & & & & & & &\vdots\\
 +
& & & & & & & & & &22\\
 +
\end{array}
 +
</math>
 +
</center>
 +
<br>
 +
 +
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.

Aktualna wersja na dzień 08:59, 29 wrz 2020

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.

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 dla problemu sortowania - drzewa decyzyjne

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



Niech oznacza minimalną liczbę porównań zawsze wystarczającą do posortowania elementów. Liczbę 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 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 .


Zatem zachodzi


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.



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

Problem dokładnego wyznaczenia liczby 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 . Dla niezależnie odkryli tę metodę również Trybuła i Czen. Oznaczmy przez liczbę porównań wymaganą przez FJA do posortowania elementów.

Początkowe wartości i przedstawia tabela.



Jak widać, dla i zachodzi , zatem FJA jest optymalny w tych przypadkach. Dla mamy . Prowadząc wyczerpujące obliczenia komputerowe, Wells odkrył, że . Knuth postawił problem znalezienia następnej wartości . Przypuszczał on, że i . Udoskonalając metodę Wellsa i intensywnie wykorzystując obliczenia komputerowe, Marcin Peczarski (w swoich pracach magisterskiej i doktorskiej na Wydziale MIMUW) pokazał, że:


, , i .


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 i . 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 , 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 i 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 elementów za pomocą FJA.

Opiszemy teraz działanie FJA. Sortowanie elementów za pomocą FJA można podzielić na 3 fazy.

Faza 1. Wykonujemy porównania dowolnie wybranych rozłącznych par elementów. Powiedzmy, że są to porównania:



Gdy jest liczbą nieparzystą, to element nie jest w tej fazie porównywany.

Faza 2. Używając rekurencyjnie FJA, sortujemy większych elementów znalezionych w fazie 1. Dostajemy posortowany ciąg elementów, który oznaczamy . Przez oznaczamy element, który był porównywany w fazie 1 z elementem i okazał się od niego mniejszy. Gdy jest liczbą nieparzystą, to element , który nie był porównywany w fazie 1 oznaczamy przez .

Faza 3. Elementy tworza ciąg posortowany, nazwijmy go łańcuchem głównym. Pozostałe elementy wstawiamy binarnie do łańcucha głównego w następującej kolejności:



gdzie . Kolejne wstawiane elementy wydłużają łańcuch główny. Przy czym element dla jest wstawiany do tej części łańcucha głównego, gdzie są elementy mniejsze od .

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.