Antoni M. Zaj czkowski: : Algorytmy i podstawy programowania – sortowanie szybkie

23 maja 2009

S

ORTOWANIE 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ó 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);

We 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.
Ł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

L

ITERATURA

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.).