tailieunhanh - Bài giảng Phân tích thiết kế và giải thuật - Chương 3: Sắp xếp ngoại

Bài giảng "Phân tích thiết kế và giải thuật - Chương 3: Sắp xếp ngoại" cung cấp cho người học các kiến thức: Sắp thứ tự ngoại là gì? một số phương pháp trộn, phương pháp trộn Run, phương pháp trộn tự nhiên, . | Bài giảng Phân tích thiết kế và giải thuật - Chương 3 Sắp xếp ngoại SẮP XẾP NGOẠI 1 Sắp thứ tự ngoại là gì Sắp thứ tự ngoại là sắp thứ tự trên tập tin Vì sao phải sắp xếp trên tập tin 2 3 Một số phương pháp trộn 1. Phương pháp trộn Run 2. Phương pháp trộn tự nhiên 3. Phương pháp trộn đa lối cân bằng Balanced multiway merging 4 1. Phương pháp trộn Run Run là một dãy liên tiếp các phần tử đã có thứ tự Ví dụ về Run 2 4 7 12 50 40 60 Chiều dài của Run chính là số phần tử trong Run Trong ví dụ trên có 2 run có độ dài lần lượt là 5 và 2 Mỗi phần tử của dãy chính là 1 run có độ dài bằng 1 5 1. Phương pháp trộn Run Việc tạo ra một run mới từ 2 run ban đầu gọi là trộn run merge . Run được tạo từ hai run ban đầu là một dãy các phần tử đã được sắp thứ tự. 6 1. Phương pháp trộn Run Mô tả bài toán Dữ liệu vào tập tin f0 cần sắp xếp Dữ liệu ra tập tin f0 đã được sắp xếp f1 f2 là hai tập tin phụ dùng để sắp xếp 7 1. Phương pháp trộn Run - Giả sử các phần tử trên f0 là 24 12 67 33 58 42 11 34 29 31 - Khởi tạo f1 f2 rỗng Bước 1 - Thực hiện phân bố m 1 phần tử lần lượt từ f0 vào f1 và f2 f1 24 67 58 11 29 f2 12 33 42 34 31 - Trộn f1 f2 thành f0 f0 12 24 33 67 42 58 11 34 29 31 8 1. Phương pháp trộn Run Bước 2 - Phân bố m 2 m 2 phần tử lần lượt từ f0 vào f1 và f2 f0 12 24 33 67 42 58 11 34 29 31 f1 12 24 42 58 29 31 f2 33 67 11 34 - Trộn f1 f2 thành f0 f0 12 24 33 67 11 34 42 58 29 31 f1 12 24 42 58 29 31 f2 33 67 11 34 9 1. Phương pháp trộn Run Bước 3 - Tương tự bước 2 phân bố m 2 m 4 phần tử lần lượt từ f0 vào f1 và f2 kết quả thu được như sau f0 12 24 33 67 11 34 42 58 29 31 f1 12 24 33 67 29 31 f2 11 34 42 58 - Trộn f1 f2 thành f0 f0 11 12 24 33 34 42 58 67 29 31 10 1. Phương pháp trộn Run Bước 4 - Phân bố m 2 m 8 phần tử lần lượt từ f0 vào f1 và f2 f0 11 12 24 33 34 42 58 67 29 31 f1 11 12 24 33 34 42 58 67 f2 29 31 - Trộn f1 f2 thành f0 f0 11 12 24 29 31 33 34 42 58 67 Bước 5 Lặp lại tương tự các bước trên cho đến khi chiều dài m của run cần phân bổ lớn hơn chiều dài n của f0