Algorytmy i struktury danych/Sortowanie: MergeSort, HeapSort i QuickSort

From Studia Informatyczne

Czy można sortować przez porównania w czasie szybszym niż kwadratowy? Odpowiedź jest pozytywna.

Spis treści

Sortowanie przez wstawianie z wyszukiwaniem binarnym

Rozważmy jeszcze raz algorytm sortowania przez wstawianie. W tym algorytmie jedna faza polega głównie na umiejscowieniu wstawianego elementu w uporządkowanym ciągu - w fazie i-tej element a[i] wstawiamy do uporządkowanego ciągu a[1..i-1], dla i = 2,3, \ldots, n. Miejsce, w które należy wstawić element a[i], można znaleźć za pomocą wyszukiwania binarnego.

Algorytm Sortowanie przez wstawianie z wyszukiwaniem binarnym


 InsertionSortWithBinarySearch
 1  for i := 2 to n do
 2  begin
 3    //a[1..i-1] jest już posortowana
 4    x := a[i]; //odkładamy element z pozycji i
 5    //binarne wyszukiwanie największego j \le i takiego, że a[j-1] \le x 
 6    l := 0; p := i;   
 7    while (p - l) > 1 do
 8    //Niezmiennik: a[l] \le x oraz x < a[p] jeśli tylko p < i   \
 9    begin
 10     s := (l+p)\ div\ 2;   
 15     if x < a[s] then
 16       p := s;
 17     else
 18       l := s;
 19   end;
 20   j := l+1; 
 21   //x zostanie wstawiony na pozycję j; 
 22   //elementy większe przesuwamy o 1 pozycję w prawo
 23   for k := i downto j+1 do
 24     a[k] := a[k-1];
 25   a[j] := x 
 26 end;

W tym algorytmie liczbę wykonywanych porównań można wyznaczyć następująco: w iteracji o numerze i zewnętrznej pętli for wykonuje się co najwyżej \lceil \log i \rceil porównań pomiędzy elementami sortowanego ciągu, co w sumie daje

\sum_{i = 2} \lceil \log i \rceil = n\lceil \log n \rceil - 2^{\lceil \log n \rceil} + 1

porównań.

Otrzymaliśmy więc algorytm, w którym wykonuje się O(n\log n) porównań niezbędnych do wyszukiwania miejsc dla wstawianych elementów, ale (niestety) liczba przesunięć elementów w tablicy, koniecznych do zrobienia tych miejsc, jest w pesymistycznym przypadku kwadratowa. Ta obserwacja jest niezwykle pouczająca. Mówi ona, że dobór operacji dominujących dla analizy złożoności algorytmu jest kluczowy dla jakości tej analizy.

Sortowanie przez wstawianie z wyszukiwaniem binarnym jest też warte wspomnienia dlatego, że jego pomysłodawcą był wybitny polski matematyk Hugo Steinhaus. O tej metodzie sortowania Steinhaus wspomina w drugim wydaniu swojej znakomitej książki Kalejdoskop matematyczny z roku 1950.

Sortowanie przez scalanie (MergeSort)

Algorytm sortowania przez wstawianie działał bardzo dobrze dla ciągów "prawie" posortowanych. W tym przypadku "prawie" oznacza małą liczbę inwersji w sortowanym ciągu. Istnieją jednak ciągi, które zawierają kwadratową liczbę inwersji, a są łatwe do sortowania. Takim ciągiem jest oczywiście ciąg malejący. Innym przykładem może być ciąg składający się z dwóch uporządkowanych podciągów występujących jeden po drugim. Załóżmy, że elementy sortowanej tablicy a[1..n] spełniają warunki a[1] \le a[2] \le \ldots \le a[s] oraz a[s+1] \le a[s+2] \le \ldots \le a[n], dla pewnego s, 1\le s < n.

Ćwiczenie 1

Jaka jest maksymalna liczba inwersji w tym przypadku?

Odpowiedź do ćwiczenia 1

(n-s)s - ta wartość jest maksymalna dla s = \lfloor \frac{n}{2} \rfloor i wynosi \lfloor \frac{n}{2} \rfloor \lceil \frac{n}{2} \rceil.

Powstaje pytanie jak szybko możemy sortować w tym przypadku. Tak naprawdę naszym celem jest scalenie dwóch uporządkowanych ciągów a[1..s] i a[s+1..n] w jeden uporządkowany ciąg a[1..n]. Załóżmy, że dysponujemy dodatkową tablicą b[1..s]. Scalania będziemy wykonywać bezpośrednio w tablicy a. Dlatego w pierwszym kroku naszego algorytmu kopiujemy podciąg a[1..s] do pomocniczej tablicy b. Następnie przeglądamy ciągi a[s+1..n] i b[1..s] z lewa na prawo. W jednym kroku porównujemy ich czołowe elementy. Mniejszy z nich umieszczamy na docelowej pozycji w tablicy a i na koniec w ciągu, z którego pochodził mniejszy element, przesuwamy się o jedną pozycję w prawo. Formalny zapis tego algorytmu został przedstawiony jako procedura Merge-1.

Algorytm Scalanie-1


 1  procedure Merge-1;
 2  begin
 3    //kopiowanie a[1..s] do b[1..s]
 4    for i := 1 to s do
 5      b[i] := a[i];  
 6    //właściwe scalanie
 7    i := 1; j := s+1; k := 0;
 8    while (i \le s) and (j \le n) do
 9    //Niezmiennik: a[1..k] - scalone podciągi b[1..i-1], a[s+1..j-1]
 10   begin
 11     k := k+1;
 12     if b[i] \le a[j] then
 13       begin a[k] := b[i]; i := i+1 end
 14     else
 15       begin a[k] := a[j]; j := j+1 end
 16   end;
 17   //jeśli nie wyczerpaliśmy ciągu b, to przepisujemy go do tablicy a
 18   for j := i to s do
 19     begin k := k+1; a[k] := b[j] end
 20 end;

Przeanalizujmy złożoność algorytmu Merge-1. Dopóki nie wyczerpiemy jednego z podciągów a[s+1..n] lub b[1..s], po każdym porównaniu elementów b[i] z a[j] mniejszy z nich trafia na swoją docelową pozycję w tablicy a. Zatem liczba porównań wynosi w pesymistycznym przypadku n-1. Niestety, oprócz porównań wielokrotnie przemieszczamy sortowane elementy. Wszystkich takich przemieszczeń mamy w pesymistycznym przypadku s+n: przepisanie a[1..s] do b[1..s] plus umieszczenie każdego elementu na jego docelowej pozycji w tablicy a. Zatem przemieszczeń jest nie więcej niż 2n.

Jeśli umiemy scalać, to możemy też sortować. Bardzo łatwo opisać taki algorytm rekurencyjnie. Jeśli sortowany ciąg składa się tylko z 1 elementu, to jest on oczywiście posortowany. Załóżmy zatem, że sortowany ciąg ma co najmniej 2 elementy. Dzielimy go na dwa podciągi złożone z kolejnych elementów. Sortujemy każdy z nich niezależnie rekurencyjnie, a potem scalamy. Oczywiście mamy wybór w podziale wyjściowego ciągu na dwa mniejsze, ale okazuje się, że najlepiej jest, gdy długości obu sortowanych podciągów różnią się co najwyżej o 1. Niech Merge(l,p,s) będzie procedurą scalającą posortowaną podtablicę a[l..s] z posortowaną podtablicą a[s+1..p], która w wyniku daje posortowaną podtablicę a[l..p].

Ćwiczenie 2

Przerób tak kod procedury Merge-1, żeby otrzymać procedurę Merge(l,p,s). Procedura Merge powinna wykonywać co najwyżej p-l porównań i co najwyżej s-l+1+p-l+1 przemieszczeń elementów.


Odpowiedź do ćwiczenia 2

Algorytm Scalanie


 1  procedure Merge(l, p, s) ;
 2  begin
 3    //kopiowanie a[l..s] do b[1..s-l+1]
 4    for i := l to s do
 5      b[i-l+1] := a[i];  
 6    //właściwe scalanie
 7    i := 1; j := s+1; k := l-1;
 8    while (i \le s-l+1) and (j \le p) do
 9    //Niezmiennik: a[l..k] - scalone podciągi b[1..i-1], a[s+1..j-1]
 10   begin
 11     k := k+1;
 12     if b[i] \le a[j] then
 13       begin a[k] := b[i]; i := i+1 end
 14     else
 15       begin a[k] := a[j]; j := j+1 end
 16   end;
 17   //jeśli nie wyczerpaliśmy ciągu b, to przepisujemy go do tablicy a
 18   for j := i to s-l+1 do
 19     begin k := k+1; a[k] := b[j] end
 20 end;


Możemy teraz przystąpić do zapisu sortowania przez scalanie. Niech MS(l,p) będzie rekurencyjną procedurą sortującą tablicę a[l..p], którą to definiujemy następująco:

Algorytm Procedura_MS



 1  procedure MS(l,p);
 2  begin
 3    if l < p then
 4      begin
 5        s := (l+p) div 2;
 6        MS(l,s); 
 7        MS(s+1,p);
 8        Merge(l,p,s) 
 9      end
 10 end;      


Sam algorytm sortowania przez scalanie MergeSort ma teraz postać:

Algorytm Sortowanie przez scalanie



 1 algorytm MergeSort;
 2 begin
 3   MS(1,n)
 4 end


Pesymistyczną liczbę porównań wykonywanych przez algorytm MergeSort można opisać za pomocą równania rekurencyjnego:

T(n) =\left\{ \begin{array}{ll} 0 & \mbox{dla } n = 1\\ T(\lfloor \frac{n}{2} \rfloor) + T(\lceil \frac{n}{2} \rceil) + n-1 & \mbox{dla } n > 1 \end{array} \right.

Dokładne rozwiązanie tego równania daje T(n) \le n\lceil \log n \rceil.

Ćwiczenie 3

Wykaż, że w algorytmie MergeSort nie wykonuje się więcej niż \frac{3}{2}n \lceil \log n \rceil przemieszczeń elementów.

Odpowiedź do ćwiczenia 3

Rozważ drzewo scaleń dla algorytmu MergeSort. W liściach tego drzewa znajdują się, patrząc z lewa na prawo, elementy sortowanego ciągu a[1], a[2], \ldots, a[n]. Każdy węzeł wewnętrzny odpowiada scaleniu uporządkowanego podciągu elementów z lewego poddrzewa z uporządkowanym podciągiem elementów z prawego podddrzewa. Liczba przemieszczeń scalanych elementów nie jest większa niż \frac{3}{2} razy suma długości tych ciągów. Na danym poziomie drzewa każdy element bierze udział tylko w jednym scalaniu. Poziomów w drzewie jest \lceil \log n\rceil + 1. Zatem łączna liczba wszystkich przemieszczeń elementów wynosi co najwyżej \frac{3}{2}n \lceil \log n \rceil.

Grafika:Sortowanie.2.png

Ćwiczenie 4

Podaj przykład 8-elementowej permutacji liczb 1, 2, \ldots, 16, dla której algorytm MergeSort wykonuje jednocześnie największą liczbę porównań i największą liczbę przemieszczeń elementów.


Odpowiedź do ćwiczenia 4

8,4,6,2,7,3,5,1

Sortowanie przez scalanie w miejscu

Słabością algorytmu MergeSort jest pomocnicza tablica używana do scalania. Czy można jej się pozbyć? Tak, można to zrobić na dwa sposoby. Pierwszy sposób polega na wykonywaniu scaleń w miejscu, czyli w samej tablicy a. Niestety liczba porównań i przemieszczeń elementów znacząco rośnie, choć jest nadal liniowa. Sam algorytm nie jest intuicyjny i pominiemy go w tych notatkach. Drugi sposób polega na wykonaniu sortowania przez scalanie przy złamaniu zasady, że długości scalanych ciągów różnią się co najwyżej o 1. Z opisanej procedury Merge-1 wynika, że scalanie dwóch ciągów możemy wykonać w taki sposób, żeby długość pomocniczej tablicy była równa długości krótszego ze scalanych ciągów. Rozważmy teraz procedurę Merge-2(p,r,s), która scala uporządkowane ciągi a[p..s] z a[s+1..r]. Zakładamy przy tym, że s-p+1 \le r-s (lewy ciąg jest nie dłuższy niż prawy) oraz p-1 \ge s-p+1 (początek tablicy jest wystarczająco długi, żeby można go wykorzystać do scalania). Scalanie będzie się odbywało z pomocą podtablicy a[1..p-1]. Będziemy przy tym uważali, żeby nie zgubić zawartości tej podtablicy. Oto nasza procedura Merge-2(p,r,s).


Algorytm Scalanie-2


 1  procedure Merge-2(p,r,s);
 2  begin
 3    //zamiana a[p..s] z a[1..s-p+1]
 4    for i := p to s do
 5      Exchange(i-p+1,i);  
 6    //właściwe scalanie
 7    i := 1; j := s+1; k := p-1;
 8    while (i \le s-p+1) and (j \le r) do
 9    //Niezmiennik: a[p..k] - scalone podciągi a[1..i-1], a[s+1..j-1]
 10   begin
 11     k := k+1;
 12     if a[i] \le a[j] then
 13       begin Exchange(i,k); i := i+1 end
 14     else
 15       begin Exchange(k,j); j := j+1 end
 16   end;
 17   //jeśli nie wyczerpaliśmy ciągu a[1..s-p+1], 
 18   //to przepisujemy go na koniec tablicy a
 19   for j := i to s-p+1 do
 20   begin k := k+1; Exchange(j,k) end
 21 end;

Zauważmy, że po wykonaniu powyższego algorytmu mamy następującą sytuację:

- podtablica a[1..p-1] zawiera te same elementy, które znajdowały się w niej przed rozpoczęciem scalania (być może przepermutowane),

- podtablica a[p..r] jest już uporządkowana.

Oznaczmy przez MergeSortBis(p,r) procedurę, która sortuje przez scalanie podtablicę a[p..r]. Załóżmy przy tym, że p-1 \ge \frac{r-p+1}{2}. Procedurę MergeSortBis implementujemy podobnie jak algorytm MergeSort, tylko zamiast procedury Merge-1 wykorzystujemy procedurę Merge-2. Możemy teraz opisać algorytm "sortowania przez scalanie w miejscu". Idea algorytmu jest następująca. Dzielimy tablicę a na dwie (prawie) równe części a[1..\lceil \frac{n}{2} \rceil] oraz a[\lceil \frac{n}{2} \rceil + 1..n]. Sortujemy prawą część tablicy algorytmem MergeSortBis wykorzystując lewą część jako tablicę pomocniczą. Dalsza część algorytmu ma strukturę rekurencyjną. Załóżmy, że w tablicy a mamy już posortowany sufiks a[p..n] dla pewnego 1<p\le \lceil \frac{n}{2} \rceil + 1. Jeśli p-1 = 1, to kończymy sortowanie wstawiając a[1] do uporządkowanego ciągu a[2..n], tak jak w sortowaniu przez wstawianie. Jeśli p > 2, wówczas dzielimy tablicę a[1..p-1] na podtablicę a[1..\lceil \frac{p-1}{2}\rceil] i a[\lceil \frac{p-1}{2}\rceil + 1..p-1], sortujemy przez scalanie podtablicę a[\lceil \frac{p-1}{2}\rceil + 1..p-1], scalamy uporządkowaną podtablicę a[\lceil \frac{p-1}{2}\rceil + 1..p-1] z podtablicą a[p..n] i sortujemy dalej rekurencyjnie przy założeniu, że a[\lceil \frac{p-1}{2}\rceil + 1..n] jest już posortowane.

Algorytm sortowania przez scalanie w miejscu można teraz zapisać następująco.

Algorytm SortowaniePrzezScalanie w Miejscu


1  if n > 1 then
2  begin 
3    p := n - \lfloor \frac{n}{2} \rfloor + 1;
4    MergeSortBis(p,n);
5    while p > 2 do
6    begin
7      l := p - \lfloor \frac{p-1}{2}\rfloor+1;
8      MergeSortBis(l,p-1);
9      Merge-2(l,n,p-1);
10     p := l
11   end;
12   Scal a[1] z a[2..n].
13 end

Zastanówmy się teraz nad złożnością przedstawionego algorytmu. Zanalizujemy najpierw liczbę porównań. Odzielnie analizujemy porównania wykonywane dla sortowania procedurą MergeSortBis, a oddzielnie dla scaleń procedurą Merge-2. MergeSortBis jest wywoływana dla ciągów o długościach \lfloor \frac{n}{2} \rfloor, \lfloor \frac{n}{4} \rfloor, \ldots. Jeżeli sortowanie ciągu długości k wymaga co najwyżej k\log k porównań, to liczba porównań we wszystkich sortowaniach wynosi co najwyżej

\frac{n}{2} \log \frac{n}{2} + \frac{n}{4}\log \frac{n}{4} \ldots  \le \log n\sum_{k=1}^{\infty} \frac{n}{2^k} = n\log n.

Scalenia kosztują nas co najwyżej tyle porównań, ile wynosi długość scalonego ciągu. Długość taka oczywiście nigdy nie przekracza n. Długości kolejnych, krótszych scalanych podtablic wynoszą odpowiednio \lfloor \frac{n}{4} \rfloor, \lfloor \frac{n}{8} \rfloor, \ldots, 1. Wszystkich scaleń jest więc nie więcej niż \log n. Liczba porównań we wszystkich scaleniach nie przekracza więc n\log n. Zatem liczba wszystkich porównań wykonywanych w algorytmie sortowania przez scalanie w miejscu nie przekracza nigdy 2n\log n. Niestety przemieszczeń będzie znacznie więcej. Każde porównanie może wymagać zamiany miejscami dwóch elementów (dwa przemieszczenia, trzy instrukcje przypisania). Dlatego liczba przemieszczeń może wynieść prawie 4n\log n. W sumie jednak mamy algorytm działający w miejscu i o złożoności czasowej O(n\log n).

Na koniec zauważmy jedno drobne "oszustwo". Procedura MergeSort i wzorowana na niej procedura MergeSortBis są procedurami rekurencyjnymi. Implementacja rekursji wymaga stosu, w tym przypadku o logarytmicznej wysokości. Żeby mieć w pełni algorytm sortowania w miejscu, powinniśmy pozbyć się stosu. W przypadku zwykłego sortowania przez scalanie, a takie jest zaimplementowane w MergeSortBis, bardzo łatwo z góry ustalić, kiedy i które podtablice są ze sobą scalane. Załóżmy, że sortujemy przez scalanie procedurą MergeSort tablicę o długości 2^k, dla pewnego k > 0. Zauważmy, że w takim przypadku scalamy najpierw podtablice jednoelementowe a[1] z a[2], a[3] z a[4], itd., potem podtablice dwuelementowe a[1..2] z a[3..4], a[5..6] z a[7..8], itd., a na koniec podtablicę a[1..2^{k-1}] z a[2^{k-1}+1..2^k]. Łatwo zaimplementować taki ciąg scaleń za pomocą iteracji. Szczegóły tej implementacji i jej uogólnienie na tablice o długościach różnych od potęg dwójki, pozostawiamy jako dobre ćwiczenie algorytmiczno-programistyczne.

Sortowanie kopcowe (HeapSort)

Przypomnijmy sobie schemat algorytmu sortowania przez wybór. Podstawowa operacja w tym algorytmie polega na wybraniu największego elementu w zbiorze sortowanych elementów, usunięciu go z tego zbioru i umieszczeniu na ostatniej pozycji w posortowanym ciągu. Następnie postępujemy tak samo z mniejszym zbiorem, znajdując i umieszczając na pozycji docelowej element drugi co do wielkości (licząc od największych). Postępując tak wielokrotnie dostaniemy uporządkowany ciąg elementów ze zbioru, który należało uporządkować. Łatwo zauważyć, że dla wydajnej implementacji powyższego algorytmu musimy umieć szybko znajdować element największy w danym zbiorze elementów oraz usuwać taki element ze zbioru. Dodatkowo musimy pamiętać, że elementy sortowanego zbioru znajdują się w tablicy a[1..n], a naszym celem jest uporządkowanie tej tablicy. Oto raz jeszcze algorytm sortowania przez wybór.

Algorytm Schemat algorytmu sortowania przez wybór


 SelectionSort 
 1  for i := n downto 2 do
 2  begin
 3    j := Max(i);
 4    Exchange(i,j)
 5  end;

Żeby można było wydajnie zaimplementować ten algorytm, musimy w każdej iteracji mieć tak zorganizowane elementy w podtablicy a[1..i], żeby łatwo było wyznaczać pozycję elementu największego, a następnie, po zamianie go z a[i], przywracać szybko właściwą organizację tablicy a[1..i-1]. W tym celu definiujemy warunek kopiec(p,r), gdzie (p,r) jest parą indeksów takich, że 1\le p \le r \le n:

kopiec(p,r): dla każdego i = p, p+1,\ldots, r, jeśli 2i \le r, to a[i] \ge a[2i], oraz jeśli 2i+1\le r, to a[i]\ge a[2i+1].

Załóżmy,że zachodzi warunek kopiec(1,n). Nietrudno zauważyć, że element a[1] jest największy w całej tablicy a.

Jeśli nie wiesz, dlaczego tak jest, zobacz ukryty fragment tekstu.

Jeśli zachodzi kopiec(1,n), to dla każdego i = 2,3, \ldots, n, mamy a[i] \le a[\lfloor \frac{i}{2}\rfloor] \le a[\lfloor \frac{i}{4}\rfloor] \le \ldots \le a[1].

Gdy zamienimy a[1] z a[n], na pewno zachodzi wtedy warunek kopiec(2,n-1), ale niestety może nie zachodzić (i zazwyczaj nie zachodzi) kopiec(1,n-1). Gdybyśmy umieli szybko przywrócić warunek kopiec(1,n-1), wówczas a[1] byłoby największe w a[1..n-1]. Zamieniwszy a[1] z a[n-1] zredukowalibyśmy znowu rozmiar naszego zadania. Postępując tak jeszcze n-3 razy, posortowalibyśmy cały ciąg. W jaki sposób zatem poprawić kopiec, gdy został on zepsuty w jednym miejscu?

Rozważmy trochę ogólniejsze zagadnienie. Załóżmy, że zachodzi warunek kopiec(p+1,r) dla pewnego p, 1\le p < r \le n. W jaki sposób zmodyfikować podtablicę a[p..r], żeby zachodziło kopiec(p,r). Sytuacja jest dosyć prosta. Jeśli 2p > r, nic nie musimy robić. Jeśli 2p = r, wystarczy sprawdzić, czy a[p] \ge a[r]. W przypadku odpowiedzi pozytywnej nic nie robimy. Dla a[p] < a[r] wystarczy zamienić a[p] z a[r]. A co, gdy 2p < r? W tym przypadku wybieramy większy z elementów a[2p], a[2p+1]. Niech a[t] będzie tym elementem. Jeśli a[p] \ge a[t], warunek kopiec(p,r) jest spełniony. W przeciwnym razie zamieniamy miejscami a[p] z a[t]. Jeżeli t+1 \le r, to zachodzi kopiec(t+1,r). Jeśli żądamy teraz, żeby zachodziło kopiec(p,r), musimy postąpić w taki sposób, aby spełniony był warunek kopiec(t,r). A to jest to samo zadanie jak to, które właśnie rozważamy, tylko o mniejszym rozmiarze. Zatem postępujemy analogicznie. Oto formalny zapis tego algorytmu.

Algorytm Poprawianie kopca


 1  PoprawKopiec(p,r);
 2  //zachodzi kopiec(p+1,r); po wykonaniu PoprawKopiec(p,r) 
 3  //ma zachodzić kopiec(p,r)
 4  begin
 5    s := p; v := a[s];
 6    while 2s \le r  do
 7    begin
 8      t := 2s;
 9      if t < r then if a[t+1] > a[t] then t := t+1;     
 10     if v \ge a[t] then 
 11     begin 
 12       a[s] := v; 
 13       s := r+1  //sztuczne zakończenie pętli
 14     end 
 15     else 
 16     begin
 17       a[s] := a[t];
 18       s := t
 19     end
 20   end;
 21   if s \le r then a[s] := v 
 21 end     

Ćwiczenie 5

Wykaż, że maksymalna liczba porównań pomiędzy elementami tablicy a w algorytmie PoprawKopiec(p,r) wynosi 2\lfloor \log \frac{r}{p} \rfloor.

Wskazówka do ćwiczenia 5

Ta liczba wynosi 2m, gdzie m jest największą liczbą całkowitą taką, że p2^m \le r.

Załóżmy, że zachodzi kopiec(1,n). Wówczas sortowanie jest bardzo proste.

 for i := n downto 2 do
 begin
   Exchange(1,i); //zamiana a[1] z a[i]    
   PoprawKopiec(1,i-1)
 end

Wykonanie PoprawKopiec(1,i-1) kosztuje pesymistycznie 2\lfloor \log (i-1) \rfloor porównań. Zatem jeśli zachodzi kopiec(1,n), sortowanie wymaga co najwyżej 2n\log n porównań.

Ćwiczenie 6

Ile najwięcej wykonamy przemieszczeń elementów?


Odpowiedź do ćwiczenia 6.

n\log n.


Pozostaje pokazać, w jaki sposób przeorganizować wejściową tablicę a, żeby zaszło kopiec(1,n). Sytuacja staje się jasna, gdy zauważymy, że niezależnie od zawartości tablicy a zachodzi kopiec(\lfloor \frac{n}{2} \rfloor+1,n).

Dlaczego?

Ponieważ 2(\lfloor \frac{n}{2} \rfloor + 1) > n.

Zatem warunek kopiec(1,n) dostajemy zapewniając kolejno zachodzenie warunków kopiec(\lfloor \frac{n}{2} \rfloor,n),  kopiec(\lfloor \frac{n}{2} \rfloor-1,n), \ldots, kopiec(1,n). Formalnie możemy to zapisać następująco:

 for i := n \mbox{ div } 2 downto 1 do
   PoprawKopiec(i,n);

Nasze dotychczasowe rozważania pozwalają stwierdzić, że liczba porównań potrzebnych do budowy kopca nie jest większa niż n\log n. Dokładniejsza analiza pokazuje, że tych porównań jest co najwyżej 4n (co najwyżej 2n przemieszczeń).


Wiemy już w jaki sposób zbudować kopiec i jak go wykorzystać do sortowania. Łącząc obie fazy - fazę budowy kopca i fazę właściwego sortowania - dostajemy algorytm znany pod angielską nazwą HeapSort (Sortowanie kopcowe).

Algorytm Sortowanie kopcowe (HeapSort)


1  begin
2  //budowa kopca
3    for i := n \mbox{ div } 2 downto 1 do
4      PoprawKopiec(i,n);
5  //właściwe sortowanie
6    for i := n downto 2 do
7    begin
8      Exchange(1,i);
9      PoprawKopiec(1,i-1)
10   end
11 end;

Algorytm HeapSort sortuje w miejscu i wykonuje nie więcej niż 2n\log n + O(n) porównań i nie więcej niż n\log n + O(n) przemieszczeń elementów.

Kopiec (Heap)

Pozostaje nam wytłumaczyć, dlaczego w opisie przedstawionego algorytmu pojawia się słowo kopiec. Spójrzmy raz jaszcze na tablicę a[1..n], dla której zachodzi warunek kopiec(1,n). Podany warunek narzuca pewną strukturę na zawartość tablicy a. Żeby dostrzec tę strukturę rozważmy zupełne drzewo binarne o n węzłach. W zupełnym drzewie binarnym wszystkie poziomy są wypełnione węzłami, z wyjątkiem poziomu ostatniego, który jest wypełniany od strony lewej do prawej tak, żeby w całym drzewie było łącznie n węzłów. Wysokość zupełnego drzewa binarnego wynosi \lfloor \log n \rfloor. Jeśli teraz ponumerujemy węzły drzewa kolejno 1, 2,\ldots, n, poczynając od korzenia, a następnie poziomami i na każdym poziomie z lewa na prawo, to lewym synem węzła o numerze i w drzewie jest węzeł o numerze 2i, o ile tylko 2i \le n, a prawym synem węzła o numerze i jest węzeł 2i+1, o ile 2i+1 \le n.

Grafika:sortowanie.3.png

Jak widać, do implementacji zupełnego drzewa binarnego nie potrzebujemy struktury dowiązaniowej. Takie drzewo można ukryć w tablicy. Wówczas i-ta pozycja w tablicy odpowiada węzłowi o numerze i, natomiast element a[i] jest wartością (kluczem) umieszczanym w i-tym węźle drzewa. Warunek kopiec(1,n) można teraz zapisać następująco:


Dla każdego węzła klucz umieszczony w tym węźle jest nie mniejszy od kluczy znajdujących się w jego synach.


Przyjęło się nazywać kopcem każde drzewo binarne (niekoniecznie zupełne), w którego węzłach klucze są rozmieszczane zgodnie z powyższym warunkiem.

Kopiec zupełny można wykorzystać do implementacji dynamicznego, skończonego multizbioru S składającego się z elementów z uniwersum z liniowym porządkiem, na którym wykonujemy następujące operacje:

Make(S):: S := \emptyset;

Insert(S,e):: wstaw nowy element e do S;

Max(S):: jeśli S nie jest pusty, to podaj element maksymalny w S;

DeleteMax(S):: usuń z S element Max(S).

Załóżmy, że znamy górne ograniczenie maxN na liczbę elementów S. Wówczas do implementacji S można wykorzystać tablicę S[1..maxN] ze strukturę kopca zupełnego. Niech n będzie aktualną liczbą elementów w zbiorze S. Najłatwiejsze do zaimplementowania są operacje utworzenia pustego kopca i sięgnięcia po element maksymalny. Obie można wykonać w czasie stałym.

Algorytm Utwórz pusty kopiec


1 Make::
2 begin
3   n := 0
4 end;

Algorytm Element maksymalny


1 Max::
2 begin
3   if n > 0 then
4     return(a[1])
5 end;

Nietrudno też zapisać operację usuwania elementu maksymalnego. Robiliśmy to już w algorytmie sortowania kopcowego.

Algorytm Usuń element maksymalny


1 DeleteMax::
2 begin
3   if n > 0 then
4   begin  
5     a[1] := a[n]; 
6     n := n - 1;
8     PoprawKopiec(1,n)
9   end;

Już wiemy, że operacja DeleteMax wykonuje się w czasie O(\log n).

Przed zapisaniem operacji wstawienia nowego elementu rozważmy operację IncreaseKey(S,e,f), która polega na zamianie wskazanego elementu e w zbiorze S na element większy f. Zastanówmy się, co stanie się z kopcem, gdy element w danym węźle zamienimy na element większy. Zauważmy, że może to zaburzyć warunek kopca, ale tylko wtedy, gdy element w ojcu badanego węzła będzie mniejszy od nowo wstawionego elementu. Jeśli teraz zamienimy miejscami te dwa elementy, problem z zachowaniem warunku kopca przesuniemy o jeden poziom w górę drzewa. Postępując dalej w ten sam sposób przywrócimy w końcu warunek kopca, ponieważ w ostateczności znajdziemy się w korzeniu drzewa. Oto procedura IncreaseKey.

Algorytm Zamiana wskazanego elementu na większy


1  IncreaseKey(i,f)::
2  //zmiana elementu e=S[i] na większy f 
3  begin
4    while (i>1) AND (a[i \mbox{ div } 2] < f) do
5    begin
6      a[i] := a[i \mbox{ div 2 }];
7      i := i \mbox{ div } 2
8    end;
9    a[i] := f 
10 end;

Złożoność algorytmu zamiany klucza na mniejszy wynosi O(\log i) (wykonujemy co najwyżej \lfloor \log i \rfloor porównań). Mając taką procedurę łatwo już zaproponować algorytm wstawiania nowego elementu do zbioru, który działa w czasie O(\log n).

Algorytm Wstaw nowy element


1 Insert(e)::
2 begin
3   n := n + 1;
4   IncreaseKey(n,e)
5 end;

Dynamiczny zbiór S z operacjami Make, Insert, Max, DeleteMax to abstrakcyjna struktura danych zwana kolejką priorytetową typu max. Jednym ze sposobów implementacji kolejki priorytetowej jest kopiec zupełny. Jeśli zamienimy operacje Max i DeleteMax na Min i DeleteMin (odpowiednio znajdowanie i usuwanie elementu minimalnego), dostaniemy kolejkę priorytetową typu min. Niezwykle łatwo zaadaptować implementację kolejki typu max do implementacji kolejki typu min. Wystarczy w opisach procedur zamienić nierówności przy porównaniach kluczy na nierówności przeciwne. W ten sam sposób łatwo otrzymać odpowiednik operacji IncreaseKey, czyli operację zmniejszenia klucza DecreaseKey. O kolejkach priorytetowych i ich zastosowaniach będzie jeszcze mowa w dalszych wykładach.

Sortowanie szybkie (QuickSort)

W sortowaniu przez scalanie dzieliliśmy sortowany ciąg na dwa mniejsze (o równych lub prawie równych rozmiarach), rekurencyjnie sortowaliśmy mniejsze podciągi, a na koniec scalaliśmy posortowane podciągi w jeden. Metodą algorytmiczną zastosowaną w tym algorytmie jest dziel i zwyciężaj. Z tej metody można także skorzystać w inny sposób. Przypuśćmy, że chcemy posortować n-elementowy zbiór X. Jeżeli X składa się tylko z jednego elementu, to nic nie trzeba robić. W przeciwnym razie wybieramy dowolny element x_0 z X, a następnie dzielimy X na trzy zbiory: X_1 = \{x \in X: x \le x_0\}, \{x_0\}, X_2 = \{x\in X: x \ge x_0 \}.

Zauważmy, że nawet gdy X jest multizbiorem, to każdy ze zbiorów X_1, X_2 ma mniej elementów niż X. Może oczywiście zdarzyć się, że jeden z tych zbiorów jest pusty. Jeśli teraz rekurencyjnie posortujemy X_1 i X_2, a następnie wypiszemy najpierw elementy X_1, potem x_0, a na koniec elementy X_2, dostaniemy uporządkowany ciąg elementów zbioru X. Pomysł powyższego algorytmu pochodzi od Hoare'a.

Zanim przedstawimy wydajną implementację tego algorytmu, zanalizujemy jego złożoność w przedstawionej wersji rekurencyjnej. Zajmiemy się liczbą porównań. Liczba przemieszczeń elementów będzie zależała od konkretnej implementacji. Ile porównań jest nam potrzebnych do dokonania podziału zbioru X? Niewątpliwie n-1 - każdy z elementów z X-\{x_0\} porównujemy z x_0. (Uwaga: przy implementacji przedstawionej poniżej liczba porównań wyniesie w pesymistycznym przypadku n+1. Nie ma to jednak wpływu na asymptotyczną złożoność algorytmu, jak i nawet na stałą przy dominującym składniku funkcji złożoności.) Działanie algorytmu można przedstawić za pomocą drzewa binarnego, w którego węzłach zapisano elementy wykorzystywane w podziałach stosownych zbiorów. W korzeniu drzewa znajduje się element dzielący cały zbiór X. W korzeniu lewego poddrzewa - element dzielący podzbiór X_1, a w korzeniu prawego poddrzewa - element dzielący podzbiór X_2, itd. Jeśli zbiór składa się tylko z jednego elementu, oczywiście żadnego podziału nie dokonujemy, a jedyny element takiego zbioru jest w liściu drzewa. Porządek elementów w całym zbiorze X wyznaczamy przechodząc drzewo działania algorytmu w porządku infiksowym.

Ćwiczenie 7

Uzasadnij, że na i-tym poziomie drzewa wykonujemy nie więcej niż n-i-1 porównań.

Odpowiedź do ćwiczenia 7

Elementy, względem których dokonujemy podziałów na danym poziomie drzewa nie biorą udziału w podziałach na poziomach niższych (o większych numerach).

Maksymalna wysokość drzewa wynosi n-1. Zatem w pesymistycznym przypadku wykonujemy n-1 + n-2 + \ldots + 1 = \frac{n(n-1)}{2} porównań.

Ćwiczenie 8

Załóżmy, że porządkujemy zbiór X = \{1,2, \ldots, n\}. Ile jest różnych drzew o wysokości n-1 odpowiadających wykonaniom naszego algorytmu?

Grafika:sortowanie.4.png
Rys. Przykładowe drzewo wykonania dla X=\{1,\ldots,7\}

Wskazówka do ćwiczenia 8

Elementem dzielącym musi być 1 lub n.

Odpowiedź do ćwiczenia 8

2^{n-1}

Odpowiedzmy sobie teraz na pytanie, kiedy wykonamy najmniejszą liczbę porównań. Jeśli wysokość drzewa wynosi h, wykonamy ich nie więcej niż h(n-1). Zatem najlepszym jest drzewo o jak najmniejszej wysokości, na przykład zupełne drzewo binarne, lub drzewo, w którym elementy zbioru X są rozmieszczone w następujący sposób:

w korzeniu znajduje się element "środkowy" (\lfloor \frac{n}{2} \rfloor co do wielkości licząc od najmniejszego); w korzeniu lewego poddrzewa element "środkowy" ze zbioru X_1; w korzeniu prawego poddrzewa element "środkowy" ze zbioru X_2; itd.

Wysokość takiego poddrzewa wynosi \lfloor \log n \rfloor. Zatem w tym przypadku liczba porównań nie przekroczy n\log n. To jest tyle, ile w sortowaniu przez scalanie. Zauważmy, że żeby wysokość drzewa obliczeń była logarytmiczna, elementy dzielące nie muszą być "środkowymi" w swoich zbiorach. Wystarczy zagwarantować, żeby rozmiary zbiorów otrzymywanych w wyniku podziału były o stały czynnik mniejsze od rozmiaru zbioru dzielonego. Na przykład, gdybyśmy chcieli tylko, żeby rozmiary dzielonych zbiorów wynosiły co najwyżej \frac{3}{4} rozmiaru dzielonego zbioru, wystarczy za element dzielący wybierać dowolny z elementów, który ma w dzielonym zbiorze co najmniej \frac{1}{4} elementów mniejszych i co najmniej \frac{1}{4} elementów większych. Zatem w takim przypadku dobrzy kandydaci na element dzielący stanowią połowę wszystkich elementów dzielonego zbioru. Innymi słowy, gdy element dzielący wybieramy losowo, to z prawdopodobieństwem \frac{1}{2} trafiamy na "dobry" element. To jest właśnie idea algorytmu szybkiego sortowania, znanego powszechnie pod angielską nazwą QuickSort. Jeżeli element dzielący będziemy wybierać losowo, jest duża szansa na to, że sortowanie zajmie O(n\log n) porównań. Spróbujmy teraz formalnie zanalizować liczbę porównań wykonywanych przez nasz algorytm, przy założeniu, że za element dzielący bierzemy losowy element ze zbioru X, przy czym zakładamy, że każdy element może zostać wybrany z jednakowym prawdopodobieństwem \frac{1}{|X|}. Dodatkowo bez straty ogólności załóżmy, że X = \{1,2,\ldots, n\}. (Uwaga: to założenie nie byłoby uprawnione, gdyby X był multizbiorem.) Niech Y_{i,j} będzie zmienną losową przyjmującą wartość 1, gdy i jest porównywane z j podczas sortowania, oraz 0 w przeciwnym przypadku, dla każdych 1\le i < j \le n. Jeśli przez Y oznaczymy zmienną losową, której wartością jest liczba porównań wykonywanych w algorytmie, to Y = \sum_{1\le i < j \le n}Y_{i,j}. Z liniowości wartości oczekiwanej wiemy, że E[Y] =  \sum_{1\le i < j \le n}E[Y_{i,j}]. Zauważmy, że E[Y_{i,j}] = p_{i,j}, gdzie p_{i,j} jest prawdopodobieństwem tego, że i jest porównywane z j, dla każdych 1\le i < j \le n. Ile wynosi p_{i,j}? Żeby obliczyć to prawdopodobieństwo, ustalmy pewne obliczenie dla zbioru X = \{1,2,\ldots, n\} i niech T będzie drzewem tego obliczenia. Rozważmy permutację p = <p_1, p_2, ..., p_n> liczb 1,2,\ldots, n występujących w węzłach tego drzewa, przy przeglądaniu jego węzłów poziomami od strony lewej do prawej, poczynając od korzenia.

Na podstawie permutacji p łatwo sprawdzić, czy dwa elementy 1< i < j są porównywane w sortowaniu odpowiadającym p.

Obserwacja

Elementy i, j, 1\le i < j \le n są porównywane w sortowaniu definiowanym przez p wtedy i tylko wtedy, gdy w permutacji p jeden z elementów i, j występuje przed wszystkimi elementami i+1, i+2, \ldots, j-1.

Ćwiczenie 9

Uzasadnij powyższą obserwację.


Odpowiedź do ćwiczenia 9

Niech k będzie tym elementem spośród i, i+1, \ldots, j, który pojawia się w p jako pierwszy. Niech S będzie podzbiorem \{1,2,\ldots, n\}, który podczas sortowania jest dzielony względem k. Nietrudno zauważyć, że \{i, i+1,\ldots,j\} \subset S. Jeśli k \ne i, j, to i, j nie będą ze sobą porównywane, ponieważ i powędruje do lewego poddrzewa k, a j powędruje do prawego poddrzewa k.

Obserwacja pozwala łatwo policzyć prawdopodobieństwo p_{i,j} - prawdopodobieństwo porównania i,j podczas sortowania. Ponieważ i,j są ze sobą porównywane tylko wtedy, gdy i lub j pojawi się jako pierwsze spośród i,i+1, \ldots, j, a wybór każdego elementu jako elementu dzielącego jest jednakowo prawdopodobny, to p_{i,j} = \frac{2}{j-i+1}. Stąd mamy E[Y_{i,j}] = \frac{2}{j-i+1}, i dalej

E[Y] = \sum_{1\le i<j \le n} \frac{2}{j-i+1} =

\sum_{i = 1}^{n-1} \sum_{j= i+1}^n \frac{2}{j-i+1} = 2 \sum_{i = 1}^{n-1}(\frac{1}{2} + \frac{1}{3} + \ldots \frac{1}{n-i+1}) =

2\sum_{i = 1}^{n-1}(H_{n-i+1} - 1) =

2\sum_{i = 2}^n(H_i - 1) = 2\sum_{i = 1}^n H_i -2n +1,

gdzie H_k jest k-tą liczbą harmoniczną. Wynika stąd, że oczekiwana liczba porównań w randomizowanym algorytmie QuickSort wynosi \frac{2}{\log e}n\log n + O(n). Współczynnik przy n\log n wynosi w przybliżeniu 1.4.

Zajmiemy się teraz nierandomizowaną wersją algorytmu QuickSort. Tak jak dotychczas naszym celem jest posortowanie tablicy a[1..n]. Bez straty ogólności przyjmijmy, że dany jest strażnik a[n+1] o wartości nie mniejszej od największego elementu w tablicy a. Tak jak w wersji randomizowanej podstawą algorytmu jest podział danego (multi-) zbioru elementów względem wybranego elementu tego zbioru. Będziemy zakładali, że elementy dzielonego zbioru składają się na podtablicę a[l..r], dla pewnych 1\le l <r \le n. Za element dzielący będziemy brali a[l]. Niech v = a[l]. Naszym celem będzie takie przemieszczenie elementów podtablicy a[l..r], żeby zaszły następujące warunki:

a[j] = v, dla pewnego l\le j \le r,

a[i] \le v, dla każdego i = l, l+1, \ldots, j-1,

a[i] \ge v, dla każdego i = j+1, j+2, \ldots, r.

Jednym słowem, jeśli elementami dzielonego zbioru X są elementy z podtablicy a[l..r], to w wyniku podziału dostajemy X_1 = \{a[l],a[l+1],\ldots, a[j-1]\} oraz X_2 = \{a[j+1],a[j+2],\ldots, a[r]\}.

Podziału a[l..r] dokonujemy za pomocą funkcji Partition(l,r), której wartością będzie docelowa pozycja v=a[l].

Algorytm Podział


1  Partition(l,r)::
2  begin
3    v := a[l]; i := l; j := r+1;
4    repeat
5    //Niezmiennik: dla każdego k=l,l+1,\ldots,i, a[k]\le   v,
6    //             dla każdego k=j,j+1,\ldots,r+1, a[k] \ge v,
7    //             j-i \ge -1.   
8      repeat i := i+1 until a[i] \ge v;
9      repeat j := j-1 until a[j] \le v;
10     if i < j then 
11       Exchange(i,j); 
12   until i \ge j;
13   a[l] := a[j]; a[j] := v; 
14   return j
15 end;

Zauważmy, że procedura Partition wykonuje co najwyżej j-i+2 porównania. To jest co najwyżej o 2 więcej niż w przypadku, gdy każdy element dzielonego zbioru (poza elementem dzielącym) jest porównywany z elementem dzielącym.

Mając w ręku procedurę podziału łatwo już zrealizować sortowanie podtablicy a[l..r]. Dokonamy tego za pomocą rekurencyjnej procedury QS(l,r).

Algorytm QuickSort - wersja rekurencyjna


1  QS(l,r)::
2  begin
3    if (r - l) > 1 then
4    begin
5         j := Partition(l,r); 
6         QS(l,j-1); 
7         QS(j+1,r)
8    end
9  end;

Żeby posortować całą tablicę a, wystarczy wywołać QS(1,n).

W tak zapisanym szybkim sortowaniu nie mamy randomizacji i niestety złe dane będziemy zawsze sortować w czasie kwadratowym. Jeśli jednak dane są losowe, nasz algorytm będzie miał takie same walory jak algorytm randomizacyjny. Zauważmy, że jeśli w tablicy a zapisano losową permutację (przyjmujemy, że każda permutacja jest jednakowo prawdopodobna), to a[1] = k z prawdopodobieństwem \frac{1}{n}, dla każdego k = 1,2,\ldots,n. Więcej, można pokazać, że w wyniku podziału względem v = a[1], elementy podtablicy a[1..j-1] tworzą losową permutację (każda permutacja tych elementów jest jednakowo prawdopodobna), jak i elementy podtablicy a[j+1..r] tworzą losową permutację. Wynika stąd, że w przypadku losowych danych algorytm QS zachowuje się tak, jak algorytm randomizowany, a oczekiwana liczba porównań jest taka sama, z dokładnością do składnika mniejszego rzędu. Liczba przemieszczeń elementów nigdy nie przekroczy liczby wykonywanych porównań.

Nietrudno powyższy algorytm przerobić na algorytm randomizowany. Wystarczy tylko na samym początku procedury Partition wylosować indeks k z przedziału l, l+1, \ldots, r i zamienić elementy a[l] i a[k].

Niski współczynnik przy n\log n (1.4) tłumaczy, dlaczego ten algorytm nazywamy szybkim. Zauważmy, że sortowanie przez scalanie wymagało dodatkowej tablicy i dużej liczby przemieszczeń elementów. W sortowaniu kopcowym współczynnik przy n\log n wynosił 2.

Rekurencyjna wersja szybkiego sortowania ma jeszcze jedną, ukrytą wadę. Potrzebna jest dodatkowa pamięć na stos służący do realizacji rekursji. Niestety w pesymistycznym przypadku rozmiar stosu może być liniowy ze względu na n. Szczęśliwie oba wywołania rekurencyjne są na końcu procedury QS i jedno z nich łatwo zamienić na iterację, a na stos można odkładać tylko parametry drugiego wywołania. Ponieważ mamy dwa wywołania, możemy sami podjąć decyzję, które z nich wykonywać iteracyjnie, a parametry którego odkładać na stos. Naszym celem jest ograniczenie rozmiaru stosu. Nietrudno zauważyć, że na stos należy odkładać parametry większego przedziału. Ponieważ w iteracji będziemy przetwarzali przedział o rozmiarze co najmniej połowę mniejszym od rozmiaru przedziału dzielonego, to liczba przedziałów aktualnie znajdujących się na stosie nigdy nie przekroczy \log n. Dokładną analizę rozmiaru stosu pozostawiamy jako ćwiczenie. Zanim jednak do tego przystąpimy, zapiszmy nierekurencyjną wersję algorytmu szybkiego sortowania. W zapisie tej procedury S jest stosem na który odkładamy parametry l,r przedziału do posortowania. Operacja Push(S,l,r) oznacza włożenie pary (l,r) na stos S, natomiast operacja Pop(S,l,r) oznacza pobranie i usunięcie końców przedziału z wierzchołka stosu S i zapisanie ich w zmiennych l,r. Funkcja Empty(S) służy do sprawdzania, czy stos jest pusty. Jeśli S jest pusty, to Empty przyjmuje wartość PRAWDA, w przeciwnym razie Empty przyjmuje wartość FAŁSZ. Oto nierekurencyjna wersja szybkiego sortowania.

Algorytm QuickSort - wersja nierekurencyjna


1  begin 
2    zainicjuj stos S z jedną parą (1,n); //sortujemy   tablicę a[1..n]
3    repeat  
4      Pop(S,l,r); //pobranie parametrów kolejnej podtablicy do sortowania
5      //chcemy posortować a[l..r]
6      while l < r do //dopóki sortowana podtablica ma co najmniej
7      //2 elementy
8      begin
9        j := partition(l,r); //dzielimy a[l..r]
10       //krótszą podtablicę przetwarzamy iteracyjnie, końce dłuższej
11       //odkładamy na stos  
12       if (j-l) \le (r-j) then  
13       begin Push(S,j+1,r); r := j-1 end  
14       else 
15       begin Push(S,l,j-1); l := j+1 end
16     end 
17   until Empty(S)
18 end;

Ćwiczenie 10

Udowodnij, że wysokość stosu nigdy nie będzie większa niż \log n.

Odpowiedź do ćwiczenia 10

Dokonamy analizy stosu S po wykonaniu każdej operacji Push w wierszu 13 lub 15. Zauważmy, że jeżeli na stos odkładamy parametry przedziału o długości d, to do iteracji kierujemy przedział o długośch g takiej, że $g \le d$. Niech (d_1,g_1), (d_2,g_2),\ldots,(d_h,g_h) będzie ciągiem par (d,g), które odpowiadają przedziałom odłożonym na stosie w kolejności od spodu do szczytu stosu. Zauważmy, że d_i \le d_{i-1}/2, dla każdego i = 2,3,\ldots,h. Ponieważ d_1 \le g_1 < n, to wysokość stosu nie będzie nigdy większa niż \log n.

Z ćwiczenia wynika, że dla n = 1000000, rozmiar stosu nie przekroczy 20.