APP_Sortowanie_Szybkie.PDF
(
103 KB
)
Pobierz
Microsoft Word - APP_Sortowanie_Szybkie.doc
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:
g83
Inne pliki z tego folderu:
WzorceProjektowe.pdf
(1673 KB)
Wykłady z Podstaw inf. sem.2.doc
(259 KB)
Wielka Księga C++.doc
(1718 KB)
waradzyn_dizedziczenie.pdf
(311 KB)
technologie obiektowe.pdf
(203 KB)
Inne foldery tego chomika:
✘Język rosyjski
Automatyka
Budowa
Dokumenty
ELEKTRONIKA
Zgłoś jeśli
naruszono regulamin