Cấu trúc dữ liệu và giải thuật (phần 8)

Còn trong phần 8 này các bạn sẽ làm quen với thuật toán Trộn nhưng trong đó có bổ sung các thuật toán trộn khác nhau, như có trộn đa pha, nâng cao của thuật toán trộn
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật (phần 8) Polyphase Merge sort PolyphaseTr n a pha: Tr n a l i cân b ng các m ng chưa ư c s d ng 1 cách hi u qu b i vì trong cùng 1 l n duy t thì phân n a s m ng luôn luôn gi vai trò tr n (ngu n) và phân n a gi vai trò phân ph i ( ích) C i ti n: Thay i vai trò c a các m ng trong cùng 1 l n duy t Phương pháp tr n a pha Polyphase Merge sort PolyphaseGi i thu t:Ta xét ví d v i 3 m ng a1,a2,a3B1: Phân ph i luân phiên các run ban u c a a vào a1,a2B2: Tr n các run c a a1,a2 vào a3. Gi i thu t k t thúc n u a3 ch còn 1 runB3: Chép ½ run c a a3 vào a1B4: Tr n các run c a a1,a3 vào a2. Gi i thu t k t thúc n u a2 ch còn 1 runB5: Chép ½ s run c a a2 vào a1. L p l i B2 Polyphase Merge sort PolyphaseNhư c i m:- M t th i gia sao chép ½ s run c a m ng này vào m ng kia. Vi c sao chép này có th lo i b n u ta b t u v i Fn-1 run c a m ng 1 và Fn-2 run c a m ng 2. V i Fn-1, Fn-2 là các s liên ti p trong nãy Fibonaci Polyphase Merge sort PolyphaseVí d : a=[13,12,11,10,9,8,7,6,5,4,3,2,1] có t t c 13 run F6=13 (1 1 2 3 5 8 13) Có t t c 6 phase a1 có 8 run, a2 có 5 run Polyphase Merge sort PolyphasePhase a1 a2 a3 1 13,12,11,10,9,8,7,6 5,4,3,2,1 2 8,7,6 (5,13);(4,12);(3,11) (2,10);(1,9) 3 (5,8,13);(4,7,12) (2,10), (1,9) (3,6,11) 4 (2,5,8,10,13); (3,6,11) (1,4,7,9,12) 5 (1,4,7,9,12) (2,3,5,6,8,10,11,13 (1,2,3,4,5,6,7,8, ) 6 9,10,11,12,13)