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

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

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<i$ takiego, że $a[j-1]\leq x$ 
 6    $l:=0;p:=i;$   
 7    while $(p-l)>1$ do
 8    //Niezmiennik: $x<a[p]$ dla Parser nie mógł rozpoznać (błąd składni): {\displaystyle  p < i   \}
 oraz $a[l]\leq x$  
 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;$ 
 20   //$x$ zostanie wstawiony na pozycję $j$; elementy większe przesuwamy o 1 pozycję w prawo
 21   for $k:=i$ downto $j+1$ do
 22     $a[k]:=a[k-1];$
 23   $a[j]:=x$ 
 24 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ń.

Czyli otrzymaliśmy 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]\leq a[2]\leq \ldots \leq a[s]$ oraz $a[s+1]\leq a[s+2]\leq \ldots \leq a[n]$, dla pewnego $s,1\leq 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]$. 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\leq s)$ and $(j\leq 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]\leq 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\leq s-l+1)$ and $(j\leq 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]\leq 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]$ zdefiniowaną nastepują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)\leq 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ądkowanemu podciągowi 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 wszytkich przemieszczeń elementów wynosi co najwyżej ${\frac {3}{2}}n\lceil \log n\rceil$.

Ć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ć? Odpowiedź jest pozytywna. 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\leq r-s$ (lewy ciąg jest nie dłuższy niż prawy) oraz $p-1\geq 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(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\leq s-p+1)$ and $(j\leq 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]\leq 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]$, to przepisujemy go na koniec tablicy $a$
 18   for $j:=i$ to $s-p+1$ do
 19   begin $k:=k+1;Exchange(j,k)$ end
 20 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\geq {\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\leq \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 \leq \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 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$. Tak więc wszystkich scaleń jest nie więcej niż $\log n$. Stąd liczba porównań we wszystkich scaleniach nie przekracza $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 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ć które podtablice i kiedy 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, jak 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, jak i 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\leq p\leq r\leq n$:

$kopiec(p,r):$ dla każdego $i=p,p+1,\ldots ,r$, jeśli $2i\leq r$, to $a[i]\geq a[2i]$, oraz jeśli $2i+1\leq r$, to $a[i]\geq 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 widzisz 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]\leq a[\lfloor {\frac {i}{2}}\rfloor ]\leq a[\lfloor {\frac {i}{4}}\rfloor ]\leq \ldots \leq a[1]$.

Gdy zamienimy $a[1]$ z $a[n]$, to na pewno zachodzi 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)$, to 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\leq p<r\leq n$. W jaki sposób zmodyfikować podtablicę $a[p..r]$, żeby zachodziło $kopiec(p,r)$. Sytuacja jest dosyć prosta. Jeśli $2p>r$, to nic nie musimy robić. Jeśli $2p=r$, to wystarczy sprawdzić, czy $a[p]\geq a[r]$. W przypadku odpowiedzi pozytywnej nic nie robimy. Dla $a[p]<a[r]$ wystarczy zamienić $a[p]$ z $a[r]$. 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. Zamieniamy teraz $a[p]$ z $a[t]$. Zauważmy, że teraz $a[p]$ jest największe w całej podtablicy $a[p..r]$. Jeżeli $t+1\leq r$, to zachodzi $kopiec(t+1,r)$. Jeśli żądamy teraz, żeby zachodziło $kopiec(p,r)$, to musimy postąpić w taki sposób, aby spełniony był warunek $kopiec(t,r)$. Ale to jest to samo zadanie co właśnie rozważane, 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)$ ma zachodzić $kopiec(p,r)$
 3  begin
 4    $s:=p;v:=a[s];$
 5    while $2s\leq r$  do
 6    begin
 7      $t:=2s;$
 8      if $t<r$ and $a[t+1]>a[t]$ then $t:=t+1;$     
 9      if $a[s]\geq a[t]$ then 
 10     begin 
 11       $a[s]:=v;$ 
 12       $s:=r$  //sztuczne zakończenie pętli
 13     end 
 14     else 
 15     begin
 16       $a[s]:=a[t];$
 17       $s:=t$
 18     end
 19   end
 17 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}\leq r$.

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

 for $i:=n$ downto 2 do
 begin
   Zamień $a[i]$ z $a[1]$.
   $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)$, to sortowanie wymaga co najwyżej $2n\log n$ porównań.

Ćwiczenie 6

Ile co najwyżej 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ń).

Zatem dostajemy algorytm sortowania w miejscu, w którym wykonuje się 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\leq n$, a prawym synem węzła o numerze $i$ jest węzeł $2i+1$, o ile $2i+1\leq n$. 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 chcemy wykonywać 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 $S$ można zaimplementować w tablicy $S[1..maxN]$ wykorzystując 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 siegnię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 wstawiania 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, to 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[\lfloor {\frac {i}{2}}\rfloor ]<f)$ do
5    begin
6      $a[i]:=a[\lfloor {\frac {i}{2}}\rfloor ]$;
7      $i:=\lfloor {\frac {i}{2}}\rfloor$
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   $Increase(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), to dostajemy kolejkę priorytetową typu min. Niezwykle łatwo zaadaptować implementację kolejki typu max do 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. Tej samej metody można także użyć w inny sposób. Przypuśćmy, że chcemy posortować $n$-elementowy zbiór $X$. Jeżeli $X$ składa się z tylko 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\leq x_{0}\}$, $\{x_{0}\}$, $X_{2}=\{x\in X:x\geq 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}$, to 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ę z tylko jednego elementu, to 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?

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$, to 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 też, ż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ę ze 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, to 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\leq i<j\leq n$. Jeśli przez $Y$ oznaczymy zmienną losową, której wartością jest liczba porównań wykonywanych w algorytmie, to $Y=\sum _{1\leq i<j\leq n}Y_{i,j}$. Z liniowości wartości oczekiwanej wiemy, że $E[Y]=\sum _{1\leq i<j\leq n}E[Y_{i,j}]$. Ale $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\leq i<j\leq 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 definiowanym przez $p$.

Obserwacja

Elementy $1<i<j$ 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\neq 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\leq i<j\leq 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\leq l<r\leq 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\leq j\leq r$,

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

$a[i]\geq 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]\leq v$,
6    //             dla każdego $k=j,j+1,\ldots ,r+1$, $a[k]\geq v$,
7    //             $j-i\geq -1$.   
8      repeat $i:=i+1$ until $a[i]\geq v$;
9      repeat $j:=j-1$ until $a[j]\leq v$;
10     if $i<j$ then 
11       $Exchange(i,j)$; 
12   until $i\geq 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)\leq (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}\leq d_{i-1}/2$, dla każdego $i=2,3,\ldots ,h$. Ponieważ $d_{1}\leq 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.