APP_Sortowanie_Szybkie.PDF

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

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 .

P L..R oznacza indeks tego elementu, nazywanego elementem

)

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 1 5

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 1 1 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 1 5

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 1 5

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 1 5

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

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: