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 4

Tư tưởng: Tương tự như thuật toán trộn tự nhiên trên mảng, chúng ta tận dụng các đường chạy tự nhiên ban đầu trên tập tin Fd có chiều dài không cố định. Tiến hành phân phối luân phiên các đường chạy tự nhiên này của tập tin Fd về 2 tập tin phụ Ft1, Ft2.
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 trong giải thuật phần 4 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaätb. Thuaät toaùn saép xeáp troän töï nhieân (Natural Merge Sort):- Tö töôûng: Töông töï nhö thuaät toaùn troän töï nhieân treân maûng, chuùng ta taän duïng caùc ñöôøng chaïy töï nhieân ban ñaàu treân taäp tin Fd coù chieàu daøi khoâng coá ñònh. Tieán haønh phaân phoái luaân phieân caùc ñöôøng chaïy töï nhieân naøy cuûa taäp tin Fd veà 2 taäp tin phuï Ft1, Ft2. Sau ñoù troän töông öùng töøng caëp ñöôøng chaïy töï nhieân ôû 2 taäp tin phuï Ft1, Ft2 thaønh moät ñöôøng chaïy môùi coù chieàu daøi baèng toång chieàu daøi cuûa caëp hai ñöôøng chaïy ñem troän vaø ñöa veà taäp tin Fd. Nhö vaäy, sau moãi laàn phaân phoái vaø troän caùc ñöôøng chaïy töï nhieân treân taäp tin Fd thì soá ñöôøng chaïy töï nhieân treân taäp tin Fd seõ giaûm ñi moät nöûa, ñoàng thôøi chieàu daøi caùc ñöôøng chaïy töï nhieân cuõng ñöôïc taêng leân. Do ñoù, sau toái ña Log2(N) laàn phaân phoái vaø troän thì taäp tin Fd chæ coøn laïi 01 ñöôøng chaïy vôùi chieàu daøi laø N vaø khi ñoù taäp tin Fd trôû thaønh taäp tin coù thöù töï. Trong thuaät giaûi naøy chuùng ta söû duïng 2 taäp tin phuï (coù theå söû duïng nhieàu hôn) vaø quaù trình phaân phoái, troän caùc ñöôøng chaïy töï nhieân ñöôïc trình baøy rieâng bieät thaønh 2 thuaät giaûi: + Thuaät giaûi phaân phoái luaân phieân (taùch) caùc ñöôøng chaïy töï nhieân treân taäp tin Fd veà hai taäp tin phuï Ft1, Ft2; + Thuaät giaûi troän (nhaäp) caùc caëp ñöôøng chaïy töï nhieân treân hai taäp tin Ft1, Ft2 veà taäp tin Fd thaønh caùc ñöôøng chaïy töï nhieân vôùi chieàu daøi lôùn hôn; vaø chuùng ta cuõng giaû söû raèng caùc loãi thao taùc treân taäp tin seõ bò boû qua.- Thuaät toaùn phaân phoái: B1: Fd = fopen(DataFile, “r”) //Môû taäp tin döõ lieäu caàn saép xeáp ñeå ñoïc döõ lieäu B2: Ft1 = fopen(DataTemp1, “w”) //Môû taäp tin trung gian thöù nhaát ñeå ghi döõ lieäu B3: Ft2 = fopen(DataTemp2, “w”) //Môû taäp tin trung gian thöù hai ñeå ghi döõ lieäu B4: IF (feof(Fd)) //Ñaõ phaân phoái heát Thöïc hieän Bkt B5: fread(&a, sizeof(T), 1, Fd) //Ñoïc 1 phaàn töû cuûa run treân Fd ra bieán taïm a //Cheùp 1 ñöôøng chaïy töï nhieân töø Fd sang Ft1 B6: fwrite(&a, sizeof(T), 1, Ft1) //Ghi giaù trò bieán taïm a vaøo taäp tin Ft1 B7: IF (feof(Fd)) //Ñaõ phaân phoái heát Thöïc hieän Bkt B8: fread(&b, sizeof(T), 1, Fd) //Ñoïc tieáp 1 phaàn töû cuûa run treân Fd ra bieán taïm b B9: IF (a > b) // Ñaõ duyeät heát 1 ñöôøng chaïy töï nhieân B9.1: a = b // Chuyeån vai troø cuûa b cho a B9.2: Thöïc hieän B12 B10: a = b B11: Laëp laïi B6 //Cheùp 1 ñöôøng chaïy töï nhieân töø Fd sang Ft2 B12: fwrite(&a, sizeof(T), 1, Ft2) //Ghi giaù trò bieán taïm a vaøo taäp tin Ft2 B13: IF (feof(Fd)) //Ñaõ phaân phoái heát Thöïc hieän Bkt Trang: 70 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät B14: fread(&b, sizeof(T), 1, Fd) //Ñoïc 1 phaàn töû cuûa run treân Fd ra bieán taïm b B15: IF (a > b) // Ñaõ duyeät heát 1 ñöôøng chaïy töï nhieân B15.1: a = b // Chuyeån vai troø cuûa b cho a B15.2: Thöïc hieän B18 B16: a = b B17: Laëp laïi B12 B18: Laëp laïi B6 Bkt: Keát thuùc- Thuaät toaùn troän: B1: Ft1 = fopen(DataTemp1, “r”) //Môû taäp tin trung gian thöù nhaát ñeå ñoïc döõ lieäu B2: Ft2 = fopen(DataTemp2, “r”) //Môû taäp tin trung gian thöù hai ñeå ñoïc döõ lieäu B3: Fd = fopen(DataFile, “w”) //Môû taäp tin döõ lieäu ñeå ghi döõ lieäu B4: fread(&a1, sizeof(T), 1, Ft1) //Ñoïc 1 phaàn töû cuûa run treân Ft1 ra bieán taïm a1 B5: fread(&a2, sizeof(T), 1, Ft2) //Ñoïc 1 phaàn töû cuûa run treân Ft2 ra bieán taïm a2 B6: IF (a1 ≤ a2) // a1 ñöùng tröôùc a2 treân Fd B6.1: fwrite(&a1, sizeof(T), 1, Fd) B6.2: If (feof(Ft1)) //Ñaõ cheùp heát caùc phaàn töû trong Ft1 Thöïc hieän B21 //Cheùp caùc phaàn töû coøn laïi trong Ft2 veà Fd B6.3: fread(&b1, sizeof(T), 1, Ft1) //Ñoïc tieáp 1 phaàn töû treân Ft1 ra bieán taïm b1 B6.4: If (a1 > b1) //Ñaõ duyeät heát ñöôøng chaïy töï nhieân trong Ft1 B6.4.1: a1 = b1 // Chuyeån vai troø cuûa b1 cho a1 B6.4.2: Thöïc hieän B9 B6.5: a1 = b1 B6.6: Laëp laïi B6 B7: ELSE // a2 ñöùng tröôùc a1 treân Fd B7.1: fwrite(&a2, sizeof(T), 1, Fd) B7.2: If (feof(Ft2)) // Ñaõ cheùp heát caùc phaàn töû trong Ft2 Thöïc hieän B25 // Cheùp caùc phaàn töû coøn laïi trong Ft1 veà Fd B7.3: fread(&b2, sizeof(T), 1, Ft2) //Ñoïc tieáp 1 phaàn töû treân Ft2 ra bieán taïm b2 B ...