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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 -tej element wstawiamy do uporządkowanego ciągu , dla . Miejsce, w które należy wstawić element , można znaleźć za pomocą wyszukiwania binarnego.

Algorytm Sortowanie przez wstawianie z wyszukiwaniem binarnym


 InsertionSortWithBinarySearch
 1  for  to  do
 2  begin
 3    // jest już posortowana
 4    ; //odkładamy element z pozycji i
 5    //binarne wyszukiwanie największego  takiego, że  
 6       
 7    while  do
 8    //Niezmiennik:  oraz  jeśli tylko 
 9    begin
 10        
 15     if  then
 16       
 17     else
 18       
 19   end;
 20    
 21   // zostanie wstawiony na pozycję ; 
 22   //elementy większe przesuwamy o 1 pozycję w prawo
 23   for  downto  do
 24     
 25    
 26 end;

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

porównań.

Otrzymaliśmy więc algorytm, w którym wykonuje się 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 spełniają warunki oraz , dla pewnego .

Ćwiczenie 1

Jaka jest maksymalna liczba inwersji w tym przypadku?

Odpowiedź do ćwiczenia 1

Powstaje pytanie jak szybko możemy sortować w tym przypadku. Tak naprawdę naszym celem jest scalenie dwóch uporządkowanych ciągów i w jeden uporządkowany ciąg . Załóżmy, że dysponujemy dodatkową tablicą . Scalania będziemy wykonywać bezpośrednio w tablicy . Dlatego w pierwszym kroku naszego algorytmu kopiujemy podciąg do pomocniczej tablicy . Następnie przeglądamy ciągi i z lewa na prawo. W jednym kroku porównujemy ich czołowe elementy. Mniejszy z nich umieszczamy na docelowej pozycji w tablicy 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  do 
 4    for  to  do
 5        
 6    //właściwe scalanie
 7    
 8    while  and  do
 9    //Niezmiennik:  - scalone podciągi 
 10   begin
 11     
 12     if  then
 13       begin  end
 14     else
 15       begin  end
 16   end;
 17   //jeśli nie wyczerpaliśmy ciągu , to przepisujemy go do tablicy 
 18   for  to  do
 19     begin  end
 20 end;

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

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 będzie procedurą scalającą posortowaną podtablicę z posortowaną podtablicą , która w wyniku daje posortowaną podtablicę .

Ćwiczenie 2

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


Odpowiedź do ćwiczenia 2

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

Algorytm Procedura_MS



 1  procedure MS(l,p);
 2  begin
 3    if  then
 4      begin
 5         div ;
 6        ; 
 7        ;
 8         
 9      end
 10 end;      


Sam algorytm sortowania przez scalanie 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 można opisać za pomocą równania rekurencyjnego:

Dokładne rozwiązanie tego równania daje .

Ćwiczenie 3

Wykaż, że w algorytmie nie wykonuje się więcej niż przemieszczeń elementów.

Odpowiedź do ćwiczenia 3

Ćwiczenie 4

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

Odpowiedź do ćwiczenia 4

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 . 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ę , która scala uporządkowane ciągi z . Zakładamy przy tym, że (lewy ciąg jest nie dłuższy niż prawy) oraz (początek tablicy jest wystarczająco długi, żeby można go wykorzystać do scalania). Scalanie będzie się odbywało z pomocą podtablicy . Będziemy przy tym uważali, żeby nie zgubić zawartości tej podtablicy. Oto nasza procedura .


Algorytm Scalanie-2


 1  procedure ;
 2  begin
 3    //zamiana  z 
 4    for  to  do
 5        
 6    //właściwe scalanie
 7    
 8    while  and  do
 9    //Niezmiennik:  - scalone podciągi 
 10   begin
 11     
 12     if  then
 13       begin  end
 14     else
 15       begin  end
 16   end;
 17   //jeśli nie wyczerpaliśmy ciągu , 
 18   //to przepisujemy go na koniec tablicy 
 19   for  to  do
 20   begin  end
 21 end;

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

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

- podtablica jest już uporządkowana.

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

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

Algorytm SortowaniePrzezScalanie w Miejscu


1  if  then
2  begin 
3    
4    ;
5    while  do
6    begin
7      
8      ;
9      ;
10     
11   end;
12   Scal  z .
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ą , a oddzielnie dla scaleń procedurą . jest wywoływana dla ciągów o długościach . Jeżeli sortowanie ciągu długości wymaga co najwyżej porównań, to liczba porównań we wszystkich sortowaniach wynosi co najwyżej

Scalenia kosztują nas co najwyżej tyle porównań, ile wynosi długość scalonego ciągu. Długość taka oczywiście nigdy nie przekracza . Długości kolejnych, krótszych scalanych podtablic wynoszą odpowiednio . Wszystkich scaleń jest więc nie więcej niż . Liczba porównań we wszystkich scaleniach nie przekracza więc . Zatem liczba wszystkich porównań wykonywanych w algorytmie sortowania przez scalanie w miejscu nie przekracza nigdy . 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 . W sumie jednak mamy algorytm działający w miejscu i o złożoności czasowej

Na koniec zauważmy jedno drobne "oszustwo". Procedura i wzorowana na niej procedura 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 , bardzo łatwo z góry ustalić, kiedy i które podtablice są ze sobą scalane. Załóżmy, że sortujemy przez scalanie procedurą tablicę o długości , dla pewnego . Zauważmy, że w takim przypadku scalamy najpierw podtablice jednoelementowe z , z , itd., potem podtablice dwuelementowe z , z , itd., a na koniec podtablicę z . Ł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 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  downto  do
 2  begin
 3    ;
 4    
 5  end;

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

dla każdego , jeśli , to , oraz jeśli , to .

Załóżmy,że zachodzi warunek . Nietrudno zauważyć, że element jest największy w całej tablicy .

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

Gdy zamienimy z , na pewno zachodzi wtedy warunek , ale niestety może nie zachodzić (i zazwyczaj nie zachodzi) . Gdybyśmy umieli szybko przywrócić warunek , wówczas byłoby największe w . Zamieniwszy z zredukowalibyśmy znowu rozmiar naszego zadania. Postępując tak jeszcze 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 dla pewnego , . W jaki sposób zmodyfikować podtablicę , żeby zachodziło . Sytuacja jest dosyć prosta. Jeśli , nic nie musimy robić. Jeśli , wystarczy sprawdzić, czy . W przypadku odpowiedzi pozytywnej nic nie robimy. Dla wystarczy zamienić z . A co, gdy ? W tym przypadku wybieramy większy z elementów . Niech będzie tym elementem. Jeśli , warunek jest spełniony. W przeciwnym razie zamieniamy miejscami z . Jeżeli , to zachodzi . Jeśli żądamy teraz, żeby zachodziło , musimy postąpić w taki sposób, aby spełniony był warunek . 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  ;
 2  //zachodzi ; po wykonaniu  
 3  //ma zachodzić 
 4  begin
 5    
 6    while   do
 7    begin
 8      
 9      if  then if  then      
 10     if  then 
 11     begin 
 12        
 13         //sztuczne zakończenie pętli
 14     end 
 15     else 
 16     begin
 17       
 18       
 19     end
 20   end;
 21   if  then  
 21 end     

Ćwiczenie 5

Wykaż, że maksymalna liczba porównań pomiędzy elementami tablicy w algorytmie PoprawKopiec(p,r) wynosi .

Wskazówka do ćwiczenia 5

Załóżmy, że zachodzi . Wówczas sortowanie jest bardzo proste.

 for  downto 2 do
 begin
   ; //zamiana  z     
   
 end

Wykonanie kosztuje pesymistycznie porównań. Zatem jeśli zachodzi , sortowanie wymaga co najwyżej porównań.

Ćwiczenie 6

Ile najwięcej wykonamy przemieszczeń elementów?


Odpowiedź do ćwiczenia 6.


Pozostaje pokazać, w jaki sposób przeorganizować wejściową tablicę , żeby zaszło . Sytuacja staje się jasna, gdy zauważymy, że niezależnie od zawartości tablicy zachodzi .

Dlaczego?

Zatem warunek dostajemy zapewniając kolejno zachodzenie warunków . Formalnie możemy to zapisać następująco:

 for  downto 1 do
   ;

Nasze dotychczasowe rozważania pozwalają stwierdzić, że liczba porównań potrzebnych do budowy kopca nie jest większa niż . Dokładniejsza analiza pokazuje, że tych porównań jest co najwyżej (co najwyżej 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  downto 1 do
4      ;
5  //właściwe sortowanie
6    for  downto 2 do
7    begin
8      ;
9      
10   end
11 end;

Algorytm HeapSort sortuje w miejscu i wykonuje nie więcej niż porównań i nie więcej niż 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ę , dla której zachodzi warunek . Podany warunek narzuca pewną strukturę na zawartość tablicy . Żeby dostrzec tę strukturę rozważmy zupełne drzewo binarne o 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 węzłów. Wysokość zupełnego drzewa binarnego wynosi . Jeśli teraz ponumerujemy węzły drzewa kolejno , 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 w drzewie jest węzeł o numerze , o ile tylko , a prawym synem węzła o numerze jest węzeł , o ile .

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 -ta pozycja w tablicy odpowiada węzłowi o numerze , natomiast element jest wartością (kluczem) umieszczanym w -tym węźle drzewa. Warunek 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 składającego się z elementów z uniwersum z liniowym porządkiem, na którym wykonujemy następujące operacje:

;

wstaw nowy element do ;

jeśli nie jest pusty, to podaj element maksymalny w ;

usuń z element .

Załóżmy, że znamy górne ograniczenie na liczbę elementów . Wówczas do implementacji można wykorzystać tablicę ze strukturę kopca zupełnego. Niech będzie aktualną liczbą elementów w zbiorze . 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 ::
2 begin
3   
4 end;

Algorytm Element maksymalny


1 ::
2 begin
3   if  then
4     
5 end;

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

Algorytm Usuń element maksymalny


1 ::
2 begin
3   if  then
4   begin  
5     ; 
6     ;
8     
9   end;

Już wiemy, że operacja wykonuje się w czasie .

Przed zapisaniem operacji wstawienia nowego elementu rozważmy operację , która polega na zamianie wskazanego elementu w zbiorze na element większy . 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 .

Algorytm Zamiana wskazanego elementu na większy


1  ::
2  //zmiana elementu  na większy  
3  begin
4    while  AND  do
5    begin
6      ;
7      
8    end;
9     
10 end;

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

Algorytm Wstaw nowy element


1 ::
2 begin
3   
4   
5 end;

Dynamiczny zbiór z operacjami , , , to abstrakcyjna struktura danych zwana kolejką priorytetową typu max. Jednym ze sposobów implementacji kolejki priorytetowej jest kopiec zupełny. Jeśli zamienimy operacje i na i (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 , czyli operację zmniejszenia klucza . 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ć -elementowy zbiór . Jeżeli składa się tylko z jednego elementu, to nic nie trzeba robić. W przeciwnym razie wybieramy dowolny element z , a następnie dzielimy na trzy zbiory: , , .

Zauważmy, że nawet gdy jest multizbiorem, to każdy ze zbiorów ma mniej elementów niż . Może oczywiście zdarzyć się, że jeden z tych zbiorów jest pusty. Jeśli teraz rekurencyjnie posortujemy i , a następnie wypiszemy najpierw elementy , potem , a na koniec elementy , dostaniemy uporządkowany ciąg elementów zbioru . 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 ? Niewątpliwie - każdy z elementów z porównujemy z . (Uwaga: przy implementacji przedstawionej poniżej liczba porównań wyniesie w pesymistycznym przypadku . 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 . W korzeniu lewego poddrzewa - element dzielący podzbiór , a w korzeniu prawego poddrzewa - element dzielący podzbiór , 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 wyznaczamy przechodząc drzewo działania algorytmu w porządku infiksowym.

Ćwiczenie 7

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

Odpowiedź do ćwiczenia 7

Maksymalna wysokość drzewa wynosi . Zatem w pesymistycznym przypadku wykonujemy porównań.

Ćwiczenie 8

Załóżmy, że porządkujemy zbiór . Ile jest różnych drzew o wysokości odpowiadających wykonaniom naszego algorytmu?

Sortowanie.4.png
Rys. Przykładowe drzewo wykonania dla

Wskazówka do ćwiczenia 8

Odpowiedź do ćwiczenia 8

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

w korzeniu znajduje się element "środkowy" ( co do wielkości licząc od najmniejszego); w korzeniu lewego poddrzewa element "środkowy" ze zbioru ; w korzeniu prawego poddrzewa element "środkowy" ze zbioru ; itd.

Wysokość takiego poddrzewa wynosi . Zatem w tym przypadku liczba porównań nie przekroczy . 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 rozmiaru dzielonego zbioru, wystarczy za element dzielący wybierać dowolny z elementów, który ma w dzielonym zbiorze co najmniej elementów mniejszych i co najmniej 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 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 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 , przy czym zakładamy, że każdy element może zostać wybrany z jednakowym prawdopodobieństwem . Dodatkowo bez straty ogólności załóżmy, że . (Uwaga: to założenie nie byłoby uprawnione, gdyby był multizbiorem.) Niech będzie zmienną losową przyjmującą wartość 1, gdy jest porównywane z podczas sortowania, oraz 0 w przeciwnym przypadku, dla każdych . Jeśli przez oznaczymy zmienną losową, której wartością jest liczba porównań wykonywanych w algorytmie, to . Z liniowości wartości oczekiwanej wiemy, że . Zauważmy, że , gdzie jest prawdopodobieństwem tego, że jest porównywane z , dla każdych . Ile wynosi ? Żeby obliczyć to prawdopodobieństwo, ustalmy pewne obliczenie dla zbioru i niech będzie drzewem tego obliczenia. Rozważmy permutację liczb 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 łatwo sprawdzić, czy dwa elementy są porównywane w sortowaniu odpowiadającym .

Obserwacja

Elementy , są porównywane w sortowaniu definiowanym przez wtedy i tylko wtedy, gdy w permutacji jeden z elementów występuje przed wszystkimi elementami .

Ćwiczenie 9

Uzasadnij powyższą obserwację.

Odpowiedź do ćwiczenia 9

Obserwacja pozwala łatwo policzyć prawdopodobieństwo - prawdopodobieństwo porównania podczas sortowania. Ponieważ są ze sobą porównywane tylko wtedy, gdy lub pojawi się jako pierwsze spośród , a wybór każdego elementu jako elementu dzielącego jest jednakowo prawdopodobny, to . Stąd mamy , i dalej

,

gdzie jest -tą liczbą harmoniczną. Wynika stąd, że oczekiwana liczba porównań w randomizowanym algorytmie wynosi . Współczynnik przy wynosi w przybliżeniu 1.4.

Zajmiemy się teraz nierandomizowaną wersją algorytmu . Tak jak dotychczas naszym celem jest posortowanie tablicy . Bez straty ogólności przyjmijmy, że dany jest strażnik o wartości nie mniejszej od największego elementu w tablicy . 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ę , dla pewnych . Za element dzielący będziemy brali . Niech . Naszym celem będzie takie przemieszczenie elementów podtablicy , żeby zaszły następujące warunki:

, dla pewnego ,

, dla każdego ,

, dla każdego .

Jednym słowem, jeśli elementami dzielonego zbioru są elementy z podtablicy , to w wyniku podziału dostajemy oraz .

Podziału dokonujemy za pomocą funkcji , której wartością będzie docelowa pozycja .

Algorytm Podział


1  
2  begin
3    
4    repeat
5    //Niezmiennik: dla każdego , ,
6    //             dla każdego , ,
7    //             .   
8      repeat  until ;
9      repeat  until ;
10     if  then 
11       ; 
12   until ;
13    
14   return 
15 end;

Zauważmy, że procedura wykonuje co najwyżej 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 . Dokonamy tego za pomocą rekurencyjnej procedury .

Algorytm QuickSort - wersja rekurencyjna


1  
2  begin
3    if  then
4    begin
5         ; 
6          
7         
8    end
9  end;

Żeby posortować całą tablicę , wystarczy wywołać .

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 zapisano losową permutację (przyjmujemy, że każda permutacja jest jednakowo prawdopodobna), to z prawdopodobieństwem , dla każdego . Więcej, można pokazać, że w wyniku podziału względem , elementy podtablicy tworzą losową permutację (każda permutacja tych elementów jest jednakowo prawdopodobna), jak i elementy podtablicy tworzą losową permutację. Wynika stąd, że w przypadku losowych danych algorytm 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 z przedziału i zamienić elementy i .

Niski współczynnik przy (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 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 . 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 . Dokładną analizę rozmiaru stosu pozostawiamy jako ćwiczenie. Zanim jednak do tego przystąpimy, zapiszmy nierekurencyjną wersję algorytmu szybkiego sortowania. W zapisie tej procedury jest stosem na który odkładamy parametry przedziału do posortowania. Operacja oznacza włożenie pary na stos , natomiast operacja oznacza pobranie i usunięcie końców przedziału z wierzchołka stosu i zapisanie ich w zmiennych . Funkcja służy do sprawdzania, czy stos jest pusty. Jeśli jest pusty, to przyjmuje wartość PRAWDA, w przeciwnym razie przyjmuje wartość FAŁSZ. Oto nierekurencyjna wersja szybkiego sortowania.

Algorytm QuickSort - wersja nierekurencyjna


1  begin 
2    zainicjuj stos  z jedną parą ; //sortujemy   tablicę 
3    repeat  
4      ; //pobranie parametrów kolejnej podtablicy do sortowania
5      //chcemy posortować 
6      while  do //dopóki sortowana podtablica ma co najmniej
7      //2 elementy
8      begin
9         //dzielimy 
10       //krótszą podtablicę przetwarzamy iteracyjnie, końce dłuższej
11       //odkładamy na stos  
12       if  then  
13       begin  end  
14       else 
15       begin  end
16     end 
17   until 
18 end;

Ćwiczenie 10

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

Odpowiedź do ćwiczenia 10

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

<flash>file=Quick.swf|width=550|height=400</flash>