SẮP THỨ TỰ NGOẠI Sắp thứ tự ngoại là sắp thứ tự trên tập tin. Khác với sắp xếp dãy trên bộ nhớ có số lượng phần tử nhỏ và truy xuất nhanh, tập tin có thể có số lượng phần tử rất lớn và thời gian truy xuất chậm. Do vậy việc sắp xếp trên các cấu trúc dữ liệu loại tập tin đòi hỏi phải áp dụng các phương pháp đặc biệt. Chương này sẽ giới thiệu một số phương pháp như sau: . | CHƯƠNG 1 - SẮP THỨ TỰ NGOẠI Sắp thứ tự ngoại là sắp thứ tự trên tập tin. Khác với sắp xếp dãy trên bộ nhớ có số lượng phần tử nhỏ và truy xuất nhanh tập tin có thể có số lượng phần tử rất lớn và thời gian truy xuất chậm. Do vậy việc sắp xếp trên các cấu trúc dữ liệu loại tập tin đòi hỏi phải áp dụng các phương pháp đặc biệt. Chương này sẽ giới thiệu một số phương pháp như sau Phương pháp trộn RUN Phương pháp trộn tự nhiên Phương pháp trộn đa lối cân bằng balanced multiway merging Phương pháp trộn đa pha Polyphase Merge 1. PHƯƠNG PHÁP TRỘN RUN Khái niệm cơ bản Run là một dãy liên tiếp các phần tử được sắp thứ tự. Ví dụ 1 2 3 4 5 là một run gồm có 5 phần tử Chiều dài run chính là số phần tử trong Run. Chẳng hạn run trong ví dụ trên có chiều dài là 5. Như vậy mỗi phần tử của dãy có thể xem như là 1 run có chiều dài là1. Hay nói khác đi mỗi phần tử của dãy chính là một run có chiều dài bằng 1. Việc tạo ra một run mới từ 2 run ban đầu gọi là trộn run merge . Hiển nhiên run được tạo từ hai run ban đầu là một dãy các phần tử đã được sắp thứ tự. ìiải thuật Giải thuật sắp xếp tập tin bằng phương pháp trộn run có thể tóm lược như sau Input f0 là tập tin cần sắp thứ tự. Output f0 là tập tin đã được sắp thứ tự. Gọi f1 f2 là 2 tập tin trộn. Các tập tin f0 f1 f2 có thể là các tập tin tuần tự text file hay có thể là các tập tin truy xuất ngẫu nhiên File of kiểu Bước 1 - Giả sử các phần tử trên f0 là 24 12 67 33 58 42 11 34 29 31 - f1 ban đầu rỗng và f2 ban đầu cũng rỗng. - 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 f0 24 12 67 33 58 42 11 34 29 31 f2 12 33 42 34 31 - Trộn f1 f2 thành f0 f0 12 24 33 67 42 58 11 34 29 31 Bước 2 -Phân bố m 2 phần tử lần lượt từ f0 vào f1 và f2 f1 12 24 42 58 29 31 f0 12 24 33 67 42 58 11 34 29 31 f2 33 67 11 34 - Trộn f1 f2 thành f0 f1 12 24 42 58 29 31 f0 12 24 33 67 11 34 42 58 29 31 f2 33 67 11 34 Bước 3 - Tương tự bước 2 phân bố m 4 phần tử lần lượt từ f0 vào f1 và f2 kết quả thu được như sau fl 12 24 33 67 29 31
