1
Ch ng 2
Phântích ph c t p c a m t s
gi ithu t s pth t và tìmki m
2
N idung
1. Vàiph ngph p s pth t c n b n
2. Quicksort
3. X pth t d a vào c s
4. X pth t b ngph ngph ptr n
5. X pth t ngo i
6. Vàiph ngph ptìmki m c n b n
3
Nguy n t c v s pth t
Xét nh ngph ng pháp s pth t m t t ptin g mcác
m utin (record)cóch a khóa (key).Khóamàlàm tph n
c
a m utin, c dùng i u khi n vi c s pth t .
M
ctiêu: s p x p các m utinsao cho cáctr khóa c a
chúng có th
t theo m t quilu tth t nào ó.
N
u các t ptin c s pth t có th ch atrong b nh
chínhthì gi ithu t s pth t c g i là s p th t n i
(internalsorting).
Vi
c s pth t t ptin l u b nh ph c g i là s p th
t ngo i (externalsorting).
4
Hainh mph ngph p s pth t

S pth t b ngph ngph pch n
Ý t ng:
Tr ctiêntm ph n t nh nh ttrong m ng v hoán i
nó v
i ph n t ang v trí th nh ttrong m ng àr i
tìm ph
n t nh th nhì trong m ng và hoán inóv i
ph
n t ang v trí th nhì trong m và c th cho
nkhitoàn m ng ã c s pth t .”
390
→
205 205 →
182 182 205 →
45 390 390 390 →
235 235 235 235
7
Gi ithu t s pth t b ngph ngph pch n
procedure selection;
var i,j,min, t:integer;
begin
for i:=1 to N-1 do
begin
min :=i;
for j:=i+1 to N do
if a[j]<a[min] then min :=j;
t:=a[min];a[min]:=a[i];
a[i] :=t;
end;
end;

235 235 235 235
10
Gi ithu t s pth t b ngph ngph pch n
procedure insertion;
var i;j;v:integer;
begin
for i:=2 to N do
begin
v:=a[i];j:=i;
while a[j-1]> v do
begin
a[j]:= a[j-1];//pulldown
j:=j-1 end;
a[j]:=v;
end;
end;
11
Nh ng l ý v gi ithu t insertionsort
.Chúngtadùng m ttr khóa “c m canh” (sentinel) t i
a[0],làmcho nó nh
h n ph n t nh nh ttrong m ng.
2. Vòng l
p ngoài c a gi ithu t cth cthi N-1 l n.
Tr
ng h p x u nh t x y rakhi m ng ã có th t o
ng
c.Khi ó, vòng l ptrong cth cthi v i t ng s
l nsau ây:
(N-1)+(N-2)+ + 1=N(N-1)/2
=O(N

2
/4sosánh và N
2
/8hoán v trong
tr
ng h p trungbình.
Tính ch
t1.4: S pth t b ngph ngphápchèncó
ph c t ptuy ntính i v i m t m ng ã g ncó
th t .
13
2.Gi ithu tQuicksort
ithu t c n b n c a Quicksort c phátminh n m
i C. A. R. Hoare.
Quicksort
c achu ng vì nó không quá khó hi n
th
c hóa.
Quicksort ch
òi h i kho ng ch ng NlgN thaotác c n b n
s pth t N ph n t .
Nh
c i m c aQuicksort g m:
-Nólàm
t gi ithu t quy
-Nóc
n kho ng N
2
thaotác c n b ntrongtr ng h p
x

i) ph
n t a[i] c a v v trí úng n c a n , v i m t
giá tr
i nào ó,
ii) t
t c nh ng ph n t trongnhóm a[left], , a[i-1] thì nh
h n hay b ng a[i]
iii) t
t c nh ng ph n t trongnhóm a[i+1], , a[right] thì
l
n h n hay b ng a[i]
Example
:
16
Thí d v phânho ch
s chúngta ch nph n t th nh t hay ph n t t n cùng
trái (leftmost )nh
là ph n t s c a v v trí úng c a
nó (Ph
n t này c g ilàph n t ch t - pivot).
153 256 1 754565355 2 7 55
153 252 1 754565355 6 7 55
153 252 1 354565755 6 7 55
35 15 3
252 1 4 4565755 6 7 55
nh
h n sorted l n h n
17
Gi ithu tQuicksort
procedure quicksort2(left, right:integer);

N/2
là chiphí c avi c s pth t hai n a t ptin
và N là chiphí c
avi cxét t ng ph n t khi phân ho ch l n
u.
T
ch ng1, vi cgi i h th ctruy h i này ã a n l i
gi
i:
C
N
N lgN.
19
Phântích ph c t p:tr ng h p x unh t
M ttr ng h p x unh t c a Quicksort l khi t ptin c
th t r i.
Khi , ph n t th nh t s òi h i n sosánh nh n ra
r
ng nó nên úng v trí th nh t. H n n a,sau ó phân
o n bên tráilàr ngvàvà phân o n bênph i g mn–1
ph
n t .Do ó v i l n phân ho ch k , ph n t th hai s
òi h i n-1 sosánh nh n ra r ng nó nên úng v trí th
hai. Và c ti p t c nh th .
Nh
v y t ng s l nsosánh s là:
n +(n-1)+…+2 +1 = n(n+1)
2 =
(n
2

S h ng(N+1) bao g m s l nsosánh ph n t ch t v i t ng
ph
n t khác,thêmhai l nsosánh haipointergiaonhau.
Ph
n còn l ilàdo s ki n m iph n t v trí k có cùngxác
xu
t 1/N c làm ph n t ch t mà sau ó chúngta có
hai phân o n v i s ph n t l n l t là k-1 và N-k.
21
Ch r n + C
1
+ … + C
N-1
thì gi ng h t
C
N-1
+ C
N-2
+… + C
0
,nênta có
N
C
N
=(N+1) + (1/N)
2C
k-1
1
Ta có th
lo itr i l ngtính t ng b ngcách nhân c hai v

2/(k+1)
3
N N
C
N
/(N+1) 2 1/k 2 1/xdx = 2lnN
1 1
Suy ra:
C
N
2NlnN
23
ph c t ptr ng h ptrungbình c a
Quicksort
tt
V tac :
lnN= (log
2
N).(log
e
2)=
.69lgN
2NlnN 1.38 NlgN.
⇒T ng s sosánh trungbình c aQuicksortch kho ng
ch ng38 cao h n trong tr ng h p t tnh t.
M
nh . Quicksort c nkho ng2NlnNsosánhtrong
tr ng h ptrungbình.
24
Kh quygi ithu tQuicksort

thu
c m t t m h n nh nào ó.
Các ph
ng pháp s pth t mà l i d ngtínhch t s c a
cáckhóa
c g i là s p th t d a vào c s (radixsort).
Nh ng ph ng pháp này không ch sosánh các tr khóa
chúng x
lý và sosánh các ph n c akhóa.
S pth t d a vào c s coi cáctr khóa nh là nh ng s
c bi udi n d ng h c s M và làm vi c v i t ngký
s
(digit) n l .
V i h u h t m imáytính,th tti n l i làmvi c v i c
s 2 (M=2) n là c s th p phân(M=10).