Antoni M. Zajączkowski: : Algorytmy i podstawy programowania  sortowanie szybkie
23 maja 2009
SORTOWANIE SZYBKIE
Sortowanie szybkie (quick sort) jest obecnie uważane za najefektywniejszy algorytm sorto-
wania wewnętrznego (Aho, Hopcroft, Ullman, 2003). Algorytm ten został opracowany przez
Hoare a (1962), który zastosował zasadę  dziel i zwyciężaj (divide and conquer).
W przypadku sortowania pewnej niepustej tablicy jednowymiarowej T wybierany jest naj-
pierw jeden jej element, nazywany elementem dzielącym (pivot), a pozostałe elementy gru-
powane są w dwóch podtablicach tak, że w jednej umieszczane są elementy o kluczach nie
większych od klucza elementu dzielącego, a w drugiej umieszczane są elementy o kluczach
większych lub równych kluczowi elementu dzielącego. Następnie, każda z podtablic jest sor-
towana przez rekurencyjne wywołania opisanego algorytmu.
Ponieważ zasadniczym krokiem w tym algorytmie sortowania jest podział sortowanej tablicy,
Wirth (2001) nazywa sortowanie szybkie, sortowaniem przez podział.
1. Opis algorytmu
Niech T(L..R) oznacza tablicę jednowymiarową, której pierwszy i ostatni indeks ozna-
czamy odpowiednio przez L i R. Tablicę tę należy posortować w porządku rosnącym wg
kluczy jej elementów.
Jak wspomnieliśmy, najważniejszą częścią algorytmu sortowania szybkiego jest procedura
realizująca podział tablicy wejściowej, przy czym podział ten musi spełniać warunki
(Sedgewick, 1983):
1. Element T(P) zostaje umieszczony w końcowym położeniu  nie będzie już przesu-
wany, przy czym P " L..R oznacza indeks tego elementu, nazywanego elementem
dzielącym.
2. Wszystkie elementy podtablicy T(L..P - 1) mają klucze mniejsze, lub równe klu-
czowi elementu T(P).
3. Wszystkie elementy podtablicy T(P + 1..R) mają klucze większe, lub równe klu-
czowi elementu T(P).
Po wykonaniu takiego podziału sortowane są podtablice T(L..P - 1) i T(P + 1..R)
przez rekurencyjne wywołanie algorytmu.
Prototyp algorytmu sortowania szybkiego możemy zapisać w postaci (Sedgewick, 1983):
procedure Recursive_Quick_Sort (List : in out List_Type;
Left_End : in Index_Type; Right_End : in Index_Type) is
Pivot_Index : Index_Type;
begin
if Right_End > Left_End then
Partition(List, Left_End, Right_End_End, Pivot_Index);
Recursive_Quick_Sort(List, Left_End, Pivot_Index - 1);
Recursive_Quick_Sort(List, Pivot_Index + 1, Right_End_End);
end if;
end Recursive_Quick_Sort; ,
przy czym procedura Partition dokonuje podziału tablicy wejściowej i wyznacza indeks
elementu dzielącego w jego docelowym położeniu.
Zwróćmy uwagę na to, że tablica jest sortowana w miejscu i dlatego parametr List jest ro-
dzaju in out.
Antoni M. Zajączkowski: : Algorytmy i podstawy programowania  sortowanie szybkie
23 maja 2009
2. Działanie algorytmu
Działanie algorytmu wyjaśnimy sortując tablicę, której kluczami elementów są wielkie litery,
a indeksami są liczby całkowite, przy czym wprowadzimy odpowiednie deklaracje i omó-
wimy wybrane instrukcje tak, że póz
niej łatwo będzie napisać program w Adzie implementu-
jący algorytm sortowania szybkiego.
Zgodnie z tym, wprowadzamy deklaracje
subtype Key_Type is Character range 'A'..'Z';
type Element is record
Key : Key_Type;
-- Data : Data_Type;
end record;
type List_Type is array (Integer range <>) of Element;
Nagłówek procedury Recursive_Quik_Sort przyjmuje postać
procedure Recursive_Quik_Sort (List : in out List_Type;
Left_End : in Integer; Right_End : in Integer);
Wez
my pod uwagę tablicę, której elementy tworzą początkowo następujący ciąg (Sedgewick,
1983):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A S O R T I N G E X A M P L E
Zaczynając podział musimy wybrać pewien element dzielący. W naszej implementacji przyj-
miemy, że jest nim ostatni (w niebieskiej ramce) element tablicy, który jest zmienną lokalną
Pivot : Element;
Znając początkowe położenie elementu dzielącego
Pivot := List(Right_End); -- List(Right_End) = 'E'
przeglądamy tablicę w prawo, zaczynając od pierwszego elementu, aż do momentu, gdy znaj-
dziemy element o kluczu większym lub równym kluczowi elementu dzielącego. W tym celu
stosujemy zmienną lokalną
Left_Index : Integer := Left_End  1; -- Left_Index = 0
Następnie, zaczynając od ostatniego elementu, przeglądamy tablicę w lewo, aż znajdziemy
element o kluczu mniejszym lub równym kluczowi elementu dzielącego. Stosujemy tu
zmienną lokalną
Right_Index : Integer := Right_End; -- Right_Index = 15
Przeglądanie (skanowanie) tablicy możemy zorganizować następująco:
loop -- scan from the left end
Left_Index := Left_Index + 1;
exit when List (Left_Index).Key >= Pivot.Key;
end loop;
loop -- scan from the right end
Right_Index := Right_Index - 1;
exit when List (Right_Index).Key <= Pivot.Key;
end loop;
W naszym przykładzie wykonanie tych pętli daje
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A S O R T I N G E X A M P L E
przy czym klucze elementów znalezionych przy przeglądaniu w prawo i lewo zaznaczono od-
powiednio czerwoną i zieloną ramką.
Antoni M. Zajączkowski: : Algorytmy i podstawy programowania  sortowanie szybkie
23 maja 2009
Pętle zatrzymują się, gdy odpowiednio Left_Index = 2 i Right_Index = 11.
A
atwo zauważyć, że znalezione elementy nie są we właściwych położeniach względem siebie,
a więc należy zamienić ich pozycje.
Temp := List (Left_Index); -- Temp = List(2)
List (Left_Index) := List (Right_Index);
List (Right_Index) := Temp;
Po tej zamianie dostajemy
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A A O R T I N G E X S M P L E
Zaczynając od wyznaczonych w poprzednio indeksów, ponownie przeglądamy tablicę
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A A O R T I N G E X S M P L E
i zamieniamy znalezione elementy
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A A E R T I N G O X S M P L E
-- Temp = List(3)
Kolejne przeglądanie zatrzymuje się, gdy Left_Index = 4 i Right_Index = 3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A A E R T I N G O X S M P L E
W tym przypadku indeksy lewy i prawy spełniają warunek Right_Index <=
Left_Index, który jest warunkiem zakończenia pętli zewnętrznej sterującej procesem
dwustronnego przeglądania tablicy. Pętla ta może mieć postać
loop
-- Dwustronne_Skanowanie;
exit when Right_Index <= Left_Index
end loop;
Po wyjściu z pętli zewnętrznej nasza tablica ma postać
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A A R E T I N G O X S M P L E
Teraz należy już tylko zamienić element przechowywany w lokalnej zmiennej Temp z ele-
mentem dzielącym
List (Right_Index) := List (Left_Index);
List (Left_Index) := List (Right_Index);
List (Right_End) := Temp;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A A E E T I N G O X S M P L R
Zauważmy, że po zakończeniu opisanego podziału, element dzielący znalazł się w docelo-
wym położeniu, a podtablice List(1..3) i List(5..15) mogą być sortowane niezależ-
nie przez rekurencyjne wywołania procedury Recursive_Quick_Sort:
Recursive_Quick_Sort (List, Left_End, Left_Index-1);
Recursive_Quick_Sort (List, Left_Index + 1, Right_End);
Zadanie obliczeniowe. Napisać, uruchomić i przetestować program w Adzie implementujący
algorytm sortowania szybkiego. Algorytm powinna realizować procedura z odpowiednio za-
projektowanym interfejsem (parametrami formalnymi). Procedura ta powinna wyznaczać
liczbę przesunięć (zamian) elementów oraz prezentować stan sortowanej tablicy po wykona-
Antoni M. Zajączkowski: : Algorytmy i podstawy programowania  sortowanie szybkie
23 maja 2009
niu każdego etapu algorytmu. Wykonać też obliczenia dla przypadku posortowanej tablicy i
tablicy posortowanej wg porządku malejącego.
Program: Test_Recursive_Quick_Sort
LITERATURA
Aho, A.V, J.E. Hopcroft, J.D. Ullman. (2003). Algorytmy i struktury danych. Helion, Gliwice,
Polska (tłum. z ang.).
Hoare, C.A.R. (1962). Quicksort. Computer Journal. 5, 10 - 15.
Sedgewick, R. (1983). Algorithms. Addison-Wesley, Reading, Mass.
Wirth, N. (2001). Algorytmy + struktury danych = programy. WNT, Warszawa (tłum. z ang.).