Cấu trúc dữ liệu và giải thuật (phần 7) 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 (285.37 KB, 10 trang )
Merge sort tr
Merge sort tr
ự
ự
c ti
c ti
ế
ế
p
p
41
Merge sort tr
Merge sort tr
ự
ự
c ti
c ti
ế
ế
p
p
Đánh giá thuật toán:
- Chi phí thực hiện MergeSort là O(nlgn)
- Nhược điểm: Không tận dụng được đặc tính của
dãy cần sắp xếp. Ví dụ: Trường hợp dãy đã có sẵn
thứ tự
- Thuật toán Merge sort cải tiến: Phương pháp
trộn tự nhiên (Natural Merge sort)
42
Natural Merge sort
Natural Merge sort
Khái niệm đường chạy (run): Một đường chạy
của dãy a là 1 dãy con không giảm của a. Nghĩa
là, đường chạy r = (a
i
,a
i+1
,…,a
j
) phải thỏa điều
kiện:
Ví du: Cho dãy a=[12,2,8,5,1,6,4,15] có 5 đường
chạy gồm (12),(2,8),(5),(1,6),(4,15)
Natural Merge sort
Natural Merge sort
Thuật toán:
- B1: r = 0; // r dùng để đếm số đường chạy
- B2: Tách dãy a=[a1,a2,…,an] thành 2 dãy b,c theo
nguyên tắc luân phiên từng đường chạy
- B3: Trộn từng cặp đường chạy của 2 dãy b,c vào a
- B4: Nếu r<=2 thì trở lại bước 2. Ngược lại: Dừng
Natural Merge sort
Natural Merge sort
Ví dụ: Cho dãy a=[5,1,2,8,4,17,10,12,4,3,24,1,4]
B1:(5);(1,2,8);(4,17);(10,12);(4);(3,24);(1,4) r=7
B2:b=[(5);(4,17);(4);(1,4)]
c=[(1,2,8);(10,12);(3,24)]
B3:a=[1,2,5,8,4,10,12,17,3,4,24,1,4)
(1,2,5,8);(4,10,12,17);(3,4,24);(1,4) r=4 B2
B2:b=[(1,2,5,8);(3,4,24)]
c=[(4,10,12,17);(1,4)]
B3:a=[1,2,4,5,8,10,12,17,1,3,4,4,24]
Natural Merge sort
Natural Merge sort
B3:a=[1,2,4,5,8,10,12,17,1,3,4,4,24]
(1,2,4,5,8,10,12,17);(1,3,4,4,24) r=2 B2
B2: b=[(1,2,4,5,8,10,12,17)]
c=[(1,3,4,4,24)]
B3: a=[1,1,2,3,4,4,4,5,8,10,12,17,24]
(1,1,2,3,4,4,4,5,8,10,12,17,24) r=1 Dừng
Natural Merge sort
Natural Merge sort
Ưu và nhược điểm:
- Thuật toán trộn tự nhiên tận dụng được các đường
chạy tự nhiên của dãy
- Tuy nhiên, trộn tự nhiên đòi hỏi không gian bộ nhớ
để lưu các dãy phụ b, c
- Thuật toán trộn tự nhiên thường ứng dụng trong
các cấu trúc dữ liệu là danh sách liên kết hoặc file
Polyphase Merge sort
Polyphase Merge sort
Trộn đa lối cân bằng:
Thay vì thực hiện 2 giai đoạn: Phân phối và trộn
như Thuật toán Merge sort thông thường, trộn đa
pha cân bằng chỉ cần thực hiện 1 giai đoạn trộn
- Ti
ế
t ki
ệ
m ½ chi phí
- C
ầ
n s
ố lượ
ng b
ộ
nh
ớ
trung gian g
ấ
p
đ
ôi
Polyphase Merge sort
Polyphase Merge sort
Ví dụ: a=[3,5,2,7,12,8,4,15,20,1,2,8,23,7,21,27]
Dùng 6 mảng trung gian
B1: Phân phối các run luân phiên vào a1,a2,a3
a1: (3,5);(4,15,20)
a2: (2,7,12);(1,2,8,23)
a3: (8);(7,21,27)
B2: Trộn các run của a1,a2,a3 và luân phiên phân
phối vào b1,b2,b3
Polyphase Merge sort
Polyphase Merge sort
b1: (2,3,5,7,8,12)
b2: (1,2,4,7,8,15,20,21,23,27)
b3: NULL
Run =2 Tiếp tục trộn b1,b2,b3 vào ngược lại
a1,a2,a3
a1: 1,2,2,3,4,5,7,7,8,8,12,15,20,21,23,27
a2:NULL
a3: NULL
Run =1. Kết thúc
