Xem mẫu
- Minh H a
Cho dãy có 8 ph n t S p x p theo vi trí tăng d n
i=1; j=3
L R
X=2
1 2 3 5 7 9 10 15
i j
L=1
R=3
ðo n c n
s px p
71
This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM
© Dương Thành Ph t-www.thayphet.net
www.adultpdf.com
- Minh H a
Cho dãy có 8 ph n t S p x p theo vi trí tăng d n
1 2 3 5 7 9 10 15
Không còn ño n
nào c n s p x p
ðo n c n
s px p
72
This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM
© Dương Thành Ph t-www.thayphet.net
www.adultpdf.com
- 10 5 7 3 9 2 15 1
ðo n [1- 8]
7 9 5 15 10
ðo n [4- 8]
9 7 15 10
ðo n [5- 8]
9 10 15
ðo n [6- 8]
ðo n [6- 7] 9 10
5 7
ðo n [4- 5]
ðo n [1- 3] 1 2 3
73
This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM
© Dương Thành Ph t-www.thayphet.net
www.adultpdf.com
- Gi i thu t:
Bư c 1:
i=1;
Bư c 2:
j=N;
Trong khi (j>i) th c hi n:
N u a[j]N-1: H t dãy, d ng
Ngư c l i: L p l i Bư c 2
74
This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM
© Dương Thành Ph t-www.thayphet.net
www.adultpdf.com
- void QuickSort(int M[], int First, int Last)
Cài ð t {
int i, j, tam, x;
x = M[(First+Last)/2]; i = First; j = Last;
do {
while (M[i] X) j--;
if (i
- ðánh giá gi i thu t:
+ Trư ng h p t t nh t, khi m ng M có th t tăng:
S phép gán: Gmin = N-1
S phép so sánh: Smin = N×Log2(N)/2
S phép hoán v : Hmin = 0
+ Trư ng h p x u nh t, khi ph n t X ñư c ch n
gi a dãy con là giá tr l n nh t:
S phép gán: Gmax = N×(N-1)/2
S phép so sánh: Smax = (N-1)×(N-1)
S phép hoán v : Hmax = N×(N-1)/2
+ Trung bình:
S phép gán: Gavg = (N-1)×(N+2)/4
S phép so sánh: Savg = N×[Log2(N)+2N–2]/4
S phép hoán v : Havg = N×(N-1)/4
76
This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM
© Dương Thành Ph t-www.thayphet.net
www.adultpdf.com
- Chi phí trung bình O(n*log2n)
Chi phí cho trư ng h p x u nh t O(n2)
Chi phí này ph thu c vào cách ch n ph n t tr c:
- N u ch n ñư c ph n t có giá tr trung bình ta
s chia thành 2 dãy b ng nhau
- N u ch n nh m ph n t nh nh t (hay l n
O(n2)
nh t)
77
This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM
© Dương Thành Ph t-www.thayphet.net
www.adultpdf.com
- 2.3 Bài T p
1. Trình bày tư tư ng và minh h a gi i thu t tìm ki m
tuy n tính, tìm ki m nh phân
2. Cài ñ t thu t toán tìm tuy n tính b ng cách:
- S d ng vòng l p for
- S d ng vòng l p while
3. Trong trư ng h p các ph n t c a dãy ñã có th t
tăng (ho c gi m) hãy cài ñ t l i thu t toán tìm nh phân
78
This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM
© Dương Thành Ph t-www.thayphet.net
www.adultpdf.com
- 1. Trình bày tư tư ng và minh h a 5 gi i thu t s p x p
2. Cài ñ t 5 gi i thu t s p x p theo các trư ng h p và
ñi n k t qu s l n th c hi n các phép toán vào b ng
sau:
79
This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM
© Dương Thành Ph t-www.thayphet.net
www.adultpdf.com
nguon tai.lieu . vn