Xem mẫu
- 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
61
This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM
© Dương Thành Ph t-www.thayphet.net
www.adultpdf.com
- Cài ð t
void bubblesort(t M[],int N)
{
for ( int i=0 ; ii ; j--)
if(M[j]
- ðánh giá gi i thu t:
Ð i v i gi i thu t n i b t, s lư ng các phép so
sánh x y ra không ph thu c vào tình tr ng c a dãy
s ban ñ u
Nhưng s lư ng phép hoán v th c hi n tùy thu c
vào k t q a so sánh
63
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.2.6.Gi i Thu t S p X p Nhanh – Quick Sort
Ý Tư ng:
Phân ho ch dãy M thành 2 dãy con th a mãn ñi u
ki n: “1/2 Dãy bên trái ch a các ph n t nh hơn
các ph n t c a 1/2 Dãy bên ph i”
N u dãy con có nhi u hơn 1 ph n t thì th c hi n
s p x p dãy con (ð qui).
64
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
i=1; j=8
L R
X=3
10 5 7 3 9 2 15 1
i j
L=1
R=8
ðo n 1 ðo n 2
ðo n c n
L=1 L=4
s px p
R=3 R=8
65
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
i=4; j=8
L R
X=5
1 2 3 7 9 5 15 10
L=4
i j
R=8
L=1
ðo n 2
ðo n 1
R=3
L=4 L=5
ðo n c n
R=5 R=8
s px p
66
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
i=5; j=8
L R
X=7
L=5 1 2 3 5 9 7 15 10
R=8
L=4
i j
R=5
L=1
ðo n 2
R=3
L=6
ðo n c n R=8
s px p
67
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
i=6; j=8
L R
X=15
L=6 1 2 3 5 7 9 15 10
R=8
L=4
i j
R=5
L=1
ðo n 1
R=3
L=6
ðo n c n R=7
s px p
68
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
i=6; j=7
X=15
L R
L=6 1 2 3 5 7 9 10 15
R=7
L=4
i j
R=5
L=1
R=3
ðo n c n
s px p
69
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
i=4; j=5
X=5
L R
1 2 3 5 7 9 10 15
L=4
i j
R=5
L=1
R=3
ðo n c n
s px p
70
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
