Cấu trúc dữ liệu và giải thuật (phần 8) pdf
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (118.54 KB, 5 trang )
Polyphase Merge sort
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
Polyphase Merge sort
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
Polyphase Merge sort
Polyphase Merge sort
Nhượ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 F
n-1
run của mảng 1 và F
n-2
run của
mảng 2. Với F
n-1
, F
n-2
là các số liên tiếp trong nãy
Fibonaci
Polyphase Merge sort
Polyphase Merge sort
Ví dụ: a=[13,12,11,10,9,8,7,6,5,4,3,2,1]
có tất cả 13 run
F
6
=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
Polyphase Merge sort
Phase 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)
(3,6,11)
(2,10), (1,9)
4 (2,5,8,10,13);
(1,4,7,9,12)
(3,6,11)
5 (1,4,7,9,12) (2,3,5,6,8,10,11,13
)
6 (1,2,3,4,5,6,7,8,
9,10,11,12,13)
