Đề tài: Nghiên cứu sắp xếp ngoài GVHD: PGS-TSKH Trần Quốc Chiến
Nội dung
Nội dung.......................................................................................................................................1
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:................................................................................................................................11
2.3 Cài đặt chương trình:.............................................................................................................14
2.4 Đánh giá giải thuật:.................................................................................................................15
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
Nhóm sinh viên thực hiện: 10 Trang 1
Đề tài: Nghiên cứu sắp xếp ngoài GVHD: PGS-TSKH Trần Quốc Chiến
I. Mở đầu

trong bộ nhớ ngoài.
Có thể xem một tập tin bao gồm nhiều mẫu tin được lưu trong các khối. Mỗi
khối lưu một số nguyên vẹn các mẫu tin, không có mẫu tin nào bị chia cắt để lưu trên
hai khối khác nhau.
Ghi Ghi
Đọc
Đọc
Mỗi lần đọc 1 mẫu tin Mỗi lần đọc 1 khối
2. Đánh giá các giải thuật xử lí ngoài
Đối với bộ nhớ ngoài thì thời gian tìm một khối để đọc vào bộ nhớ trong là rất
lớn so với thời gian thao tác trên dữ liệu khối đó. Vì vậy khi đánh giá các giải thuật
thao tác trên bộ nhớ ngoài, chúng ta tập trung vào việc xét số lần đọc khối vào bộ nhớ
trong và số lần ghi khối ra bộ nhớ ngoài ta gọi chung là phép truy xuất khối(block
access). Vì kích thước các khối là cố định nên ta không thể tìm cách tăng kích thước
một khối mà chúng ta phải tìm các giảm số lần truy xuất khối .
Nhóm sinh viên thực hiện: 10 Trang 3
Bộ nhớ trong
Bộ nhớ đệm
Bộ nhớ ngoài
Đề tài: Nghiên cứu sắp xếp ngoài GVHD: PGS-TSKH Trần Quốc Chiến
IV. Thiết kế cấu trúc dữ liệu và giải thuật
1. sắp xếp bằng phương pháp trộn tự nhiên (Phương pháp 1)
1.1 Tư tưởng
Sắp xếp tập tin F, sử dụng 2 tập tin phụ F1 và F2.
Thực hiện luân phiên 2 công việc:
- Tách tập tin lớn thành 2 tập tin con có thứ tự.
- Trộn 2 tập tin con thành tập tin lớn có thứ tự.
1.2 Giải thuật
Lặp lại các bước sau:
Phân đoạn F thành F1 và F2


F2 6 15 29 5 31 40 45
Lần 4:
F1 3 65 20 25 12 50 67 9 18 34
F2 6 15 29 5 31 40 45 17
Lần 5:
F1 3 65 20 25 12 50 67 9 18 34 11 98
F2 6 15 29 5 31 40 45 17 8
 Số đoạn con: 10

1.2.b Giải thuật trộn
Trộn các đoạn con có thứ tự trong file F1 và file F2 vào file F, biến numsubfile
là số đoạn con có trong F.
Bước 1: Mở file F1, F2 để đọc, mở file F để ghi;
Nhóm sinh viên thực hiện: 10 Trang 5
3 65
Đề tài: Nghiên cứu sắp xếp ngoài GVHD: PGS-TSKH Trần Quốc Chiến
Bước 2: Đọc PT đầu tiên của file F1 vào biến x và phần tử đầu tiên của F2 vào
biến y.
Thực hiện cho tới khi đọc hết file F1 và F2
(i) Thực hiện cho tới khi hết đoạn con trong F1 hoặc hết đoạn con trong F2
i
1.
Nếu phần tử x của F1 < phần tử y của F2 thì di chuyển x vào F và
đọc phần tử tiếp theo của F1.
i
2.
Nếu phần tử x của F1 > phần tử y của F2 thì di chuyển y vào F và
đọc phần tử tiếp theo của F2.
Bước 3: Nếu file F1 chưa kết thúc thì ghi các phần tử còn lại của nó sang F,

3 5 6 15 20 25 29 31 40 65 9 12 17 18 34 45 50 67 8 11 98
Lần 3:
- Phân đoạn:
F1
8 11 98
F2

Nhóm sinh viên thực hiện: 10 Trang 7
12 45 50 67
9 17 18 34
3 5 6 15 20 25 29 31 40 65
9 12 17 18 34 45 50 67
Đề tài: Nghiên cứu sắp xếp ngoài GVHD: PGS-TSKH Trần Quốc Chiến
- Trộn:
3 5 6 9 12 15 17 18 20 25 29 31 34 40 45 50 65 67 8 11 98
Lần 4:
- Phân đoạn:
F1
3 5 6 9 12 15 17 18 20 25 29 31 34 40 45 50 65 67
F2
8 11 98
- Trộn:
3 5 6 8 9 11 12 15 17 18 20 25 29 31 34 40 45 50 65 67 98
z(F2);
1.3 Cài đặt chương trình
a. Cài đặt chương trình phân đoạn
Thủ tục phân đoạn
Phân file F thành 2 file F1 và F2.
Procedure phandoan(var F,F1,F2:fileType);
Var kt:boolean;

Var V,S:infotype;
Begin
if not eof(F) then
begin
read(F,V);
write(T,V);
if eof(F) then kt:=true
Nhóm sinh viên thực hiện: 10 Trang 9
Đề tài: Nghiên cứu sắp xếp ngoài GVHD: PGS-TSKH Trần Quốc Chiến
else
begin
read(F,S);
kt:=(S<V);
seek(F,filepos(F)-1);
end;
end;
End;
b. Cài đặt chương trình trộn
Giải thuật trộn các đoạn con có thứ tự trong file F1 và file F2 vào file F
Procedure Tron(var F,F1,F2:fileType);
Var kt1,kt2:boolean; v1,v2:infotype;
Begin
Assign(F,'chinh'); Rewrite(F);
Assign(F1,'phu1'); Reset(F1);
Assign(F2,'phu2'); Reset(F2);
while not(eof(F1) or eof(F2)) do
begin
read(F1,v1); read(F2,v2);
Seek(F1,filepos(F1)-1);
Seek(F2,filepos(F2)-1);