TAILIEUCHUNG - Cấu trúc dữ liệu và giải thuật II - 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: . | 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

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• giải thuật
• phương pháp sắp xếp
• tổ chức dữ liệu
• t đề án tin họ
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp