index of cnpmpth02004slidepdf

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (274.42 KB, 19 trang )

(1)<div class='page_container' data-page=1>

CH

ƯƠ

NG 3

S

Ắ

P X

Ế

P VÀ TÌM KI

Ế

M NÂNG CAO

GV. Ngô Công Th

ắ

ng

B

ộ

môn Công ngh

ệ

ph

ầ

n m

ề

m

Khoa Công ngh

ệ

thông tin

Website: dse.vnua.edu.vn/ncthang

Email:

N

ộ

i dung Ch

ươ

ng 3

1. S

ắ

p x

ế

p nhanh (Quick Sort)

2. S

ắ

p x

ế

p vun

đố

ng (Heap Sort)

3. S

ắ

p x

ế

p hịa nh

ậ

p (Merge Sort)

4. Tìm ki

ế

m nh

ị

phân

</div>
(2)<div class='page_container' data-page=2>

1. S

ắ

p x

ế

p nhanh (Quick Sort)

1.1. Ph

ươ

ng pháp

• S

ắ

p

x

ế

p

nhanh

(quick sort) còn

đượ

c

s

ắ

p

x

ế

p phân

đ

o

ạ

n (partition sort).

• Ý t

ưở

ng thu

ậ

t tốn:

– Ch

ọ

n ng

ẫ

u nhiên m

ộ

t ph

ầ

n t

ử

x.

– Duy

ệ

t t

ừ

bên trái m

ả

ng cho t

ớ

i khi có m

ộ

t ph

ầ

n t

ử

a

i

>

=

x

– Sau

đ

ó duy

ệ

t t

ừ

bên ph

ả

i m

ả

ng cho t

ớ

i khi có m

ộ

t

ph

ầ

n t

ử

aj

=

<x

–

Đổ

i ch

ỗ

a

i

và a

j

– Ti

ế

p t

ụ

c duy

ệ

t và

đổ

i ch

ỗ

cho t

ớ

i khi 2 phía g

ặ

p nhau.

Ngơ Cơng Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 03 3.3

1.1. Ph

ươ

ng pháp (

ti

ế

p

)

• K

ế

t qu

ả

m

ả

ng

đượ

c

chia thành 2 ph

ầ

n:

</div>
(3)<div class='page_container' data-page=3>

Th

ủ

t

ụ

c s

ắ

p x

ế

p nhanh

Procedure Q_sort(L,R);

1) If L>=R then return;

2) i:=L; j:=R ; k:=(L+R) div 2;

3) x:=a[k];

4) Repeat

While a[i] <x Do i:=i+1;

While a[j] >x Do j:=j-1;

If i<j then a[i]

↔

a[j]

Until i=j

5) Call Q_sort(L,j-1); { Th

ự

c hi

ệ

n trên n

ử

a <x }

6) Call Q_sort(j+1,R); { Th

ự

c hi

ệ

n trên n

ử

a >x }

Return

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 03 3.5

1.2. Đ

ánh giá

• Ng

ườ

i ta

đ

ã ch

ứ

ng minh

đượ

c th

ờ

i gian trung

bình th

ự

c hi

ệ

n gi

ả

i thu

ậ

t là:

T

tb

= O(nlog

2

n)

• Nh

ư

v

ậ

y, v

ớ

i n khá l

ớ

n Quick sort có hi

ệ

u l

ự

c

</div>
(4)<div class='page_container' data-page=4>

2. S

ắ

p x

ế

p vun

đố

ng (Heap Sort)

2.1. Ph

ươ

ng pháp

• M

ộ

t cây nh

ị

phân có chi

ề

u cao h

đượ

c g

ọ

i là

đố

ng khi:

–

Là cây nh

ị

phân hoàn ch

ỉ

nh mà các nút lá

ở

m

ứ

c

h-1 ph

ả

i n

ằ

m phía bên trái.

–

Khoá

ở

nút cha bao gi

ờ

c

ũ

ng l

ớ

n h

ơ

n khố

ở

nút

con.

Ngơ Cơng Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 03 3.7

2. S

ắ

p x

ế

p vun

đố

ng (Heap Sort)

2.1. Ph

ươ

ng pháp

• Thu

ậ

t tốn s

ắ

p x

ế

p vun

đố

ng chia làm 2 giai

đ

o

ạ

n.

</div>
(5)<div class='page_container' data-page=5></div>
(6)<div class='page_container' data-page=6></div>
(7)<div class='page_container' data-page=7>

- L

ặ

p l

ạ

i các b

ướ

c t

ươ

ng t

ự

cho các cây còn l

ạ

i.

Cu

ố

i cùng ta thu

đượ

c dãy

đ

ã s

ắ

p là s=(11, 23, 42, 58, 65,

74)

* Gi

ả

i thu

ậ

t vun

đố

ng:

- M

ộ

t lá coi nh

ư

cây con là m

ộ

t

đố

ng.

- Thu

ậ

t toán ti

ế

n hành t

ừ

đ

áy lên: Chuy

ể

n

đổ

i thành

đố

ng

cho m

ộ

t cây con mà cây con trái và cây con ph

ả

i c

ủ

a g

ố

c

đ

ã

là m

ộ

t

đố

ng.

Cây nh

ị

phân hoàn ch

ỉ

nh có n nút thì v

ớ

i ch

ỉ

s

ố

[n/2] tr

ở

lên

có th

ể

là nút cha: [n/2], [n/2 ]-1, . . . , 1.

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 03 3.13

a) Th

ủ

t

ụ

c vun

đố

ng:

Ch

ỉ

nh lý cây nh

ị

phân con hoàn ch

ỉ

nh g

ố

c i trên cây nh

ị

phân có n nút

để

tr

ở

thành “

đố

ng” v

ớ

i

đ

i

ề

u ki

ệ

n cây con

trái và cây con ph

ả

i có g

ố

c là 2i và 2i+1

đ

ã là

đố

ng.

Procedure ADJUST(i,n)

1. { Kh

ở

i

đầ

u }

Key:=K[i]; j:=2*i;

2. { Ch

ọ

n con

ứ

ng v

ớ

i khoá l

ớ

n nh

ấ

t trong 2 con c

ủ

a i }

While j<=n Do

Begin

</div>
(8)<div class='page_container' data-page=8>

a) Th

ủ

t

ụ

c vun

đố

ng:

3. { So sánh khoá cha v

ớ

i khoá l

ớ

n nh

ấ

t }

If Key > K[j] then Begin

K[j/2]:=Key;

Return;

End;

K[j/2]:=K[j]; j:=2*j;

End; {K

ế

t thúc while}

4. {

Đư

a Key vào v

ị

trí c

ủ

a nó }

K[j/2]:=Key;

5. Return;

Ngơ Cơng Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 03 3.15

b) Th

ủ

t

ụ

c s

ắ

p x

ế

p vun

đố

ng:

Procedure Heap_Sort(K,n)

1. { T

ạ

o

đố

ng ban

đầ

u }

For i:=[n/2] Downto 1 Do

Call ADJUST(i,n)

2. { S

ắ

p x

ế

p }

For i:= n-1 Downto 1 Do

Begin

tg:=K[1]; K[1]:=K[i+1];

K[i+1]:=tg;

Call ADJUST(1,i);

End;

3. Return

5.2.

Đ

ánh giá

</div>
(9)<div class='page_container' data-page=9>

3. S

ắ

p x

ế

p ki

ể

u hoà nh

ậ

p ( MERGE SORT)

3.1. Phép hoà nh

ậ

p 2

đườ

ng

Th

ự

c hi

ệ

n h

ợ

p nh

ấ

t các b

ả

n ghi c

ủ

a 2 b

ả

ng

đ

ã

đượ

c s

ắ

p

x

ế

p thành 1 b

ả

ng

đượ

c s

ắ

p.

a) Ph

ươ

ng pháp:

So sánh 2 khoá nh

ỏ

nh

ấ

t ( ho

ặ

c l

ớ

n nh

ấ

t c

ủ

a 2 b

ả

ng)

để

đư

a vào mi

ề

n s

ắ

p x

ế

p.

Quá trình c

ứ

ti

ế

p t

ụ

c cho t

ớ

i khi 2 b

ả

ng

đ

ã c

ạ

n.

b) Gi

ả

i thu

ậ

t:

B

ả

ng 1: (x

b

, ..., x

m

)

B

ả

ng 2: (x

m+1

, ..., x

n

)

B

ả

ng s

ắ

p: (z

b

, ..., z

n

)

Ví d

ụ

: B

ả

ng 1: (3, 5, 10, 16 )

B

ả

ng 2: (1, 4, 15 )

B

ả

ng s

ắ

p: (1, 3, 4, 5, 10, 15, 16)

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 03 3.17

* Th

ủ

t

ụ

c nh

ư

sau:

Procedure MERGE(X,b,m,n,Z);

1. i:=k:=b; j:=m+1;

2. While (i<=m) and (j<=n) Do

Begin If x[i]<=x[j] then

Begin Z[k]:=x[i];

i:=i+1;

End

Else Begin z[k]:=x[j];

j:=j+1;

End;

</div>
(10)<div class='page_container' data-page=10>

* Th

ủ

t

ụ

c nh

ư

sau:

3. { M

ộ

t trong 2 b

ả

ng con

đ

ã c

ạ

n }

If i>m then (zk, ..., zn):= (xj, ..., xn)

Else (zk, ..., zn):= (xi, ..., xm)

4. Return

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 03 3.19

3.2. S

ắ

p x

ế

p ki

ể

u hòa nh

ậ

p tr

ự

c ti

ế

p (Straight two way

merge )

* B

ả

ng con

đ

ã

đượ

c s

ắ

p g

ọ

i là m

ộ

t m

ạ

ch ( run).

* M

ỗ

i b

ả

n ghi coi nh

ư

1 m

ạ

ch có

độ

dài ( kích th

ướ

c )

là 1. N

ế

u hồ nh

ậ

p 2 b

ả

ng nh

ư

v

ậ

y ta

đượ

c 1 m

ạ

ch

m

ớ

i có

độ

dài =2. Hồ nh

ậ

p 2 m

ạ

ch có

độ

dài là 2 ta

đượ

c m

ộ

t m

ạ

ch có

độ

dài là 4, ...

* Th

ủ

t

ụ

c MPASS th

ự

c hi

ệ

n m

ộ

t b

ướ

c c

ủ

a s

ắ

p x

ế

p

hồ nh

ậ

p. Nó hịa nh

ậ

p t

ừ

ng c

ặ

p m

ạ

ch k

ề

c

ậ

n nhau,

có

độ

dài L, t

ừ

b

ả

ng X sang b

ả

ng Y, n là s

ố

l

ượ

ng

</div>
(11)<div class='page_container' data-page=11>

Procedure MPASS(X,Y,n,L)

1. i:=1;

2. Hồ nh

ậ

p c

ặ

p m

ạ

ch có

độ

dài L }

While i<= n-(2L-1) Do

Begin Call MERGE(X,i,i+L-1,i+2L-1, Y)

i:=i+2L;

End;

3. { Hồ nh

ậ

p c

ặ

p m

ạ

ch cịn l

ạ

i cu

ố

i cùng

v

ớ

i t

ổ

ng

độ

dài <2L}

If i+L-1 <n then Call MERGE(X,i,i+L-1,n,Y)

Else (y

i

, ..., y

n

):= (x

i

, ..., x

n

);

Return

</div>
(12)<div class='page_container' data-page=12>

3.3. Đ

ánh giá

Th

ờ

i gian th

ự

c hi

ệ

n trung bình c

ủ

a gi

ả

i thu

ậ

t là:

Ttb = O(nlog

2

n)

* Nh

ậ

n xét chung:

- V

ớ

i n nh

ỏ

có th

ể

dùng các ph

ươ

ng pháp:

ch

ọ

n tr

ự

c ti

ế

p, chèn tr

ự

c ti

ế

p,

đổ

i ch

ỗ

tr

ự

c

ti

ế

p.

- V

ớ

i n l

ớ

n: N

ế

u dãy khố khơng s

ắ

p dùng

Quick sort, n

ế

u dãy khố có s

ắ

p dùng Heap

sort.

Ngơ Cơng Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 03 3.23

4. Tìm ki

ế

m nh

ị

phân

Bài tốn tìm ki

ế

m

* Bài tốn tìm ki

ế

m

đượ

c phát bi

ể

u nh

ư

Cho m

ộ

t b

ả

ng g

ồ

m n b

ả

n ghi r

1

, r

2

, . . . , r

n

; r

i

(

1<= i <=n ) t

ươ

ng

ứ

ng v

ớ

i m

ộ

t khố k

i

. Hãy tìm

b

ả

n ghi có giá tr

ị

khố t

ươ

ng

ứ

ng b

ằ

ng x cho

tr

ướ

c.

</div>
(13)<div class='page_container' data-page=13>

1- Tìm

đượ

c b

ả

n ghi có giá tr

ị

khố t

ươ

ng

ứ

ng

b

ằ

ng x. Lúc

đ

ó ta nói phép tìm ki

ế

m

đượ

c tho

ả

.

2- Khơng tìm

đượ

c b

ả

n ghi nào có giá tr

ị

khố b

ằ

ng

x . Khi

đ

ó ta nói phép tìm ki

ế

m khơng tho

ả

.

Sau phép tìm ki

ế

m khơng tho

ả

n

ế

u có u c

ầ

n b

ổ

sung b

ả

n ghi m

ớ

i có khố x vào b

ả

ng. Gi

ả

i thu

ậ

t

này g

ọ

i là “ Tìm ki

ế

m có b

ổ

sung”.

Khố c

ủ

a m

ỗ

i b

ả

n ghi chính là

đặ

c

đ

i

ể

m nh

ậ

n bi

ế

t

c

ủ

a b

ả

n ghi

đ

ó trong tìm ki

ế

m, ta coi nó là

đạ

i di

ệ

n

c

ủ

a b

ả

n ghi trong gi

ả

i thu

ậ

t.

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 03 3.25

4.1. Ý t

ưở

ng gi

ả

i thu

ậ

t

* Ph

ươ

ng pháp tìm ki

ế

m th

ự

c hi

ệ

n trên dãy khóa

đ

ã

s

ắ

p x

ế

p, có n

ộ

i dung nh

ư

sau:

- T

ươ

ng t

ự

nh

ư

tra tìm t

ừ

trong t

ừ đ

i

ể

n ho

ặ

c danh

b

ạ đ

i

ệ

n tho

ạ

i. Ch

ỉ

khác là trong tra c

ứ

u ta ch

ọ

n t

ừ

ng

ẫ

u nhiên, cịn trong tìm ki

ế

m nh

ị

phân ln ch

ọ

n

khố “

ở

gi

ữ

a” d

ẫ

y khố.

- Gi

ả

s

ử

có dãy khố k

L

, . . ., k

R

thì khố

ở

gi

ữ

a là

k

i

v

ớ

i

</div>
(14)<div class='page_container' data-page=14>

+ Tìm ki

ế

m s

ẽ

k

ế

t thúc n

ế

u: x=k

i

+ N

ế

u x<k

i

tìm ki

ế

m s

ẽ

đượ

c th

ự

c hi

ệ

n ti

ế

p

v

ớ

i k

L

, . . . , k

i-1

v

ớ

i cách t

ươ

ng t

ự

.

+ N

ế

u x>k

i

tìm ki

ế

m s

ẽ

đượ

c th

ự

c hi

ệ

n ti

ế

p

v

ớ

i k

i+1

, . . . , k

r

v

ớ

i cách t

ươ

ng t

ự

.

Qúa trình tìm ki

ế

m k

ế

t thúc khi tìm th

ấ

y m

ộ

t

khố mong mu

ố

n ho

ặ

c dãy khố r

ỗ

ng

( khơng tìm th

ấ

y ).

Ngơ Cơng Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 03 3.27

* Gi

ả

i thu

ậ

t:

Cho dãy K g

ồ

m n khoá, s

ắ

p x

ế

p theo th

ứ

t

ự

t

ă

ng d

ầ

n. Tìm khố có

giá tr

ị

=x.

Dùng bi

ế

n L, R, m: ch

ỉ

s

ố

đầ

u, ch

ỉ

s

ố

cu

ố

i, ch

ỉ

s

ố

gi

ữ

a c

ủ

a khố k.

N

ế

u tìm th

ấ

y cho ra ch

ỉ

s

ố

c

ủ

a khố

đ

ó, n

ế

u khơng tìm th

ấ

y cho ra

0.

Function Binary_search(K,n,x)

1. { Kh

ở

i t

ạ

o }

L:=1; R:=n;

2. { Tìm ki

ế

m }

While L<= R Do

Begin

</div>
(15)<div class='page_container' data-page=15>

4. { So sánh }

If x<k[m] then R:=m-1

Else IF x>k[m] then L:=m+1

Else Return (m);

End; {End of While}

5. { Khơng tìm th

ấ

y }

Return (0)

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 03 3.29

* Gi

ả

i thu

ậ

t vi

ế

t d

ạ

ng

đệ

quy nh

ư

sau:

L, r là ch

ỉ

s

ố

đầ

u, ch

ỉ

s

ố

cu

ố

i c

ủ

a dãy K, bi

ế

n nguyên Loc

để

đư

a ra ch

ỉ

s

ố

ứ

ng v

ớ

i khố c

ầ

n tìm, n

ế

u khơng tìm

th

ấ

y thì Loc =0.

Function Binary_search(L,R,x)

1. If L>R then Loc:=0

Else

begin m:=(L+R) div 2;

If x<k[m] then

Loc:=Binary_search(L,m-1,x)

Else If x>k[m] then

Loc:=Binary_search(m+1,R,x)

Else Loc:=m;

end;

</div>
(16)<div class='page_container' data-page=16>

4.2.

Đ

ánh giá

Phép tính tích c

ự

c là phép so sánh

L<= r

C

min

=1

Ng

ườ

i ta

đ

ã tính

đượ

c

C

max

=[log

2

n ]

T

tb

=O(log

2

n )

Tìm ki

ế

m nh

ị

phân t

ố

t h

ơ

n tìm ki

ế

m tu

ầ

n t

ự

nh

ư

ng dãy k ph

ả

i

đượ

c s

ắ

p.

Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 03 3.31

5. Cây nh

ị

phân tìm ki

ế

m

5.1.

Đị

nh ngh

ĩ

a cây nh

ị

phân tìm ki

ế

m

* Cây nh

ị

phân tìm ki

ế

m

ứ

ng v

ớ

i n khoá k

1

, k

2

, ..., k

n

là m

ộ

t

cây nh

ị

phân mà m

ỗ

i nút c

ủ

a nó

đề

u

đượ

c

đị

nh danh b

ở

i

m

ộ

t khố nào

đ

ó trong các khố

đ

ã cho.

Đố

i v

ớ

i m

ọ

i nút

trên cây tính ch

ấ

t sau

đ

ây ln

đượ

c tho

ả

mãn:

- M

ọ

i khố thu

ộ

c cây con trái c

ủ

a m

ộ

t nút

đề

u nh

ỏ

h

ơ

n

khoá

ứ

ng v

ớ

i nút

đ

ó.

- M

ọ

i khố thu

ộ

c cây con ph

ả

i c

ủ

a m

ộ

t nút

đề

u l

ớ

n h

ơ

n

khố

ứ

ng v

ớ

i nút

đ

ó.

Chú ý : Khố là s

ố

thì so sánh s

ố

bình th

ườ

ng, Khố là ch

ữ

</div>
(17)<div class='page_container' data-page=17>

Ngơ Cơng Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 03 3.33

5.2. Gi

ả

i thu

ậ

t tìm ki

ế

m

*

Đố

i v

ớ

i m

ộ

t cây nh

ị

phân

để

tìm ki

ế

m xem m

ộ

t khố

x nào

đ

ó có trên cây

đ

ó khơng? Ta có th

ể

th

ự

c hi

ệ

n

nh

ư

So sánh x v

ớ

i khoá

ở

g

ố

c và m

ộ

t trong 4 tình hu

ố

ng

đ

ây s

ẽ

xu

ấ

t hi

ệ

n:

1- Khơng có g

ố

c cây ( cây r

ỗ

ng): X khơng có trên cây,

</div>
(18)<div class='page_container' data-page=18>

2- X trùng v

ớ

i khố

ở

g

ố

c: Phép tìm ki

ế

m

đượ

c

tho

ả

mãn.

3- X nh

ỏ

h

ơ

n khố

ở

g

ố

c: Tìm ki

ế

m

đượ

c th

ự

c hi

ệ

n

ti

ế

p t

ụ

c b

ằ

ng cách xét cây con trái c

ủ

a g

ố

c v

ớ

i cách

làm t

ươ

ng t

ự

.

4- X l

ớ

n h

ơ

n khoá

ở

g

ố

c: Tìm ki

ế

m

đượ

c th

ự

c hi

ệ

n

ti

ế

p t

ụ

c b

ằ

ng cách xét cây con ph

ả

i c

ủ

a g

ố

c v

ớ

i

cách làm t

ươ

ng t

ự

.

Ví d

ụ

Tìm x=28 trên cây a: So x và 35, x<35 nên ta

tìm trên cây con trái c

ủ

a 35

</div>
(19)<div class='page_container' data-page=19></div>