Tiểu Luận Nghiên cứu sắp xếp ngoài

Nội dung
I. Mở đầu. 2
II. Phát biểu bài toán. 2
III. Phương pháp nghiên cứu. 3
1. Phương pháp. 3
2. Đánh giá các giải thuật xử lí ngoài 3
IV. Thiết kế cấu trúc dữ liệu và giải thuật. 4
1. sắp xếp bằng phương pháp trộn tự nhiên (Phương pháp 1). 4
1.1 Tư tưởng. 4
1.2 Giải thuật 4
1.3 Cài đặt chương trình. 8
1.4 Đánh giá giải thuật 11
2. sắp xếp ngoài bằng phương pháp trộn khác ( phương pháp 2). 11
2.1 Tư tưởng:. 11
2.2 Giải thuật:. 12
2.3 Cài đặt chương trình:. 14
2.4 Đánh giá giải thuật:. 16
3. Cải tiến sắp xếp trộn (phương pháp 3). 16
3.1 Tư tưởng. 16
3.2 Giải thuật 16
3.3 Đánh giá giải thuật 18
4. Trộn nhiều đường (phương pháp 4). 19
4.1 Tư tưởng. 19
4.2 Giải thuật 19
4.3. Cài đặt chương trình tham khảo chương trình chạy bằng C++). 21
4.4. Đánh giá giải thuật:. 26



I. Mở đầu Sắp xếp một danh sách các đối tượng theo một thứ tự nào đó là một bài toán thường được vận dụng trong các ứng dụng tin học. Ví dụ ta cần sắp xếp danh sách thí sinh theo tên với thứ tự Alphabet hoặc sắp xếp danh sách sinh viên theo điểm trung bình từ cao đến thấp. Một ví dụ khác là khi cần tìm kiếm một đối tượng trong một danh sách các đối tượng bằng giải thuật tìm kiếm nhị phân thì danh sách các đối tượng này phải được sắp xếp trước đó.
Tóm lại sắp xếp là một yêu cầu không thể thiếu trong khi thiết kế các phần mềm. Do đó việc nghiên cứu các phương pháp sắp xếp là rất cần thiết để vận dụng trong khi lập trình.
Ta đã biết đến các phương pháp sắp xếp trong và trong các giải thuật mà chúng ta đề cập từ trước tới nay, chúng ta đã giả sử rằng số lượng các dữ liệu vào là khá nhỏ để có thể chứa hết ở bộ nhớ trong (main memory). Nhưng điều gì sẽ xảy ra nếu ta muốn xử lí phiếu điều tra dân số toàn quốc hay thông tin về quản lí đất đai cả nước chẳng hạn? Trong các bài toán như vậy số lượng dữ liệu vượt quá khả năng lưu trữ của bộ nhớ trong. Để có thể giải quyết các bài toán đó chúng ta phải dùng bộ nhớ ngoài để lưu trữ và xử lí.