Tìm hiểu tầm quan trọng của cấu trúc dữ liệu và giải thụât trong một đề án tin học phần 3

L = 16 10: Kết thúc thuật toán - Phân tích thuật toán: + Trong thuật giải này chúng ta luôn thực hiện log2(N) lần phân phối và trộn các run.
Nội dung trích xuất từ tài liệu:
Tìm hiểu tầm quan trọng của cấu trúc dữ liệu và giải thụât trong một đề án tin học phần 3 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät 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. Trang: 47 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät+ ÔÛ 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 25Ta 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ùcrun môùi troän veà hai ñaàu daõy kia nhö sau:Laàn 1: L = 1Troä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áthôï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 25Tmp: 25 81 57 69 14 77 74 56 63 9Ñoåi vai troø cuûa M vaø Tmp cho nhauM: 25 81 57 69 14 77 74 56 63 9Laàn 2: L = 2Troä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áthôï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 9Tmp: 9 25 63 81 14 77 74 69 57 56 Trang: 48 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät Ñoåi vai troø cuûa M vaø Tmp cho nhau M: 9 25 63 81 14 77 74 69 57 56 Laàn 3: L = 4 Troän caùc caëp run coù chieàu daøi L = 4 treân M thaønh caùc run coù chieàu daøi L = 8 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: 9 25 63 81 14 77 74 69 57 56 Tmp: 9 25 56 57 63 69 74 81 77 14 Ñoåi vai troø cuûa M vaø Tmp cho nhau M: 9 25 56 57 63 69 74 81 77 14 ...