tailieunhanh - Polyphase Merge sort

Tham khảo tài liệu 'polyphase merge sort', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | UNIVERSITY Polyphase Merge sort Trộ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 UNIVERSITY Polyphase Merge sort Giải thuật Ta xét ví dụ với 3 mảng a1 a2 a3 B1 Phân phối luân phiên các run ban đầu của a vào a1 a2 B2 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 run B3 Chép run của a3 vào a1 B4 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 run B5 Chép số run của a2 vào a1. Lặp lại B2 UNIVERSITY Polyphase Merge sort Nhược điểm - Mất thời gia sao chép Y1 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 .

TỪ KHÓA LIÊN QUAN