Tìm hiểu tầm quan trọng của cấu trúc dữ liệu trong giải thuật phần 3 ppsx

Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät

Trang: 47

Phaân phoái M thaønh Temp1, Temp2:

M: 32 36 41 47 21 52 57 65 50 70

Temp1:N1=6 32 36 41 47 50 70

Temp2: N2=4 21 52 57 65

Troän Temp1, Temp2 thaønh M:

Temp1:N1=6 32 36 41 47 50 70

Temp2: N2=4 21 52 57 65

M: 21 32 36 41 47 52 57 65 50 70

Laàn 4: L = 8

Phaân phoái M thaønh Temp1, Temp2:

M: 21 32 36 41 47 52 57 65 50 70

Temp1: N1=8 21 32 36 41 47 52 57 65

Temp2: N2=2 50 70

Troän Temp1, Temp2 thaønh M:

Temp1: N1=8 21 32 36 41 47 52 57 65

Temp2: N2=2 50 70

M: 21 32 36 41 47 50 52 57 65 70

L = 16 > 10: Keát thuùc thuaät toaùn

- Phaân tích thuaät toaùn:

+ Trong thuaät giaûi naøy chuùng ta luoân thöïc hieän log2(N) laàn phaân phoái vaø troän caùc run.

Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät

Trang: 48

+ ÔÛ moãi laàn phaân phoái run chuùng ta phaûi thöïc hieän: N pheùp gaùn vaø 2N pheùp so saùnh

(N pheùp so saùnh heát ñöôøng chaïy vaø N pheùp so saùnh heát daõy).

+ ÔÛ moãi laàn troän run chuùng ta cuõng phaûi thöïc hieän: N pheùp gaùn vaø 2N+N/2 pheùp so

saùnh (N pheùp so saùnh heát ñöôøng chaïy, N pheùp so saùnh heát daõy vaø N/2 pheùp so

saùnh giaù trò caùc caëp töông öùng treân 2 daõy phuï).

+ Trong moïi tröôøng hôïp:

Soá pheùp gaùn: G = 2N×Log2(N)

Soá pheùp so saùnh: S = (4N+N/2)×Log2(N)

Soá pheùp hoaùn vò: Hmin = 0

+ Trong thuaät giaûi naøy chuùng ta söû duïng 02 daõy phuï, tuy nhieân toång soá phaàn töû ôû 02

daõy phuï naøy cuõng chæ baèng N, do vaäy ñaõ taïo ra söï laõng phí boä nhôù khoâng caàn

thieát. Ñeå giaûi quyeát vaán ñeà naøy chuùng ta chæ caàn söû duïng 01 daõy phuï song chuùng

ta keát hôïp quaù trình troän caùc caëp run coù chieàu daøi L töông öùng ôû hai ñaàu daõy

thaønh caùc run coù chieàu daøi 2L vaø phaân phoái luaân phieân veà hai ñaàu cuûa moät daõy

phuï. Sau ñoù chuùng ta ñoåi vai troø cuûa 02 daõy naøy cho nhau.

+ Tröôùc khi hieäu chænh laïi thuaät giaûi chuùng ta xeùt daõy M goàm 10 phaàn töû sau ñeå minh

hoïa cho quaù trình naøy:

Giaû söû ta caàn saép xeáp maûng M coù 10 phaàn töû sau (N = 10):

M: 81 63 69 74 14 77 56 57 9 25

Ta thöïc hieän caùc laàn troän caùc caëp run ôû hai ñaàu daõy naøy vaø keát hôïp phaân phoái caùc

run môùi troän veà hai ñaàu daõy kia nhö sau:

Laàn 1: L = 1

Troän caùc caëp run coù chieàu daøi L = 1 treân M thaønh caùc run coù chieàu daøi L = 2 vaø keát

hôïp phaân phoái luaân phieân caùc run naøy veà hai ñaàu daõy Tmp:

M: 81 63 69 74 14 77 56 57 9 25

Tmp: 25 81 57 69 14 77 74 56 63 9

Ñoåi vai troø cuûa M vaø Tmp cho nhau

M: 25 81 57 69 14 77 74 56 63 9

Laàn 2: L = 2

Troän caùc caëp run coù chieàu daøi L = 2 treân M thaønh caùc run coù chieàu daøi L = 4 vaø keát

hôïp phaân phoái luaân phieân caùc run naøy veà hai ñaàu daõy Tmp:

M: 25 81 57 69 14 77 74 56 63 9

Tmp: 9 25 63 81 14 77 74 69 57 56