Đề tài Nghiên cứu sắp xếp ngoài

Nội dung 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í. II. Phát biểu bài toán Các phương pháp như Bubble-Sort, QuickSort,…là sắp xếp trong làm việc với dữ liệu nhỏ. Nhiều ứng dụng sắp xếp quan trọng liên quan đến việc xử lí các tập tin có kích thước lớn, nên không có đủ bộ nhớ cho những tập tin quá lớn như vậy. Các phương pháp thích hợp cho những ứng dụng như vậy gọi là phương pháp sắp xếp ngoài, vì chúng liên quan đến xử lí dữ liệu bên ngoài đơn vị xử lí trung ương. Do đó chúng ta sử dụng sắp xếp ngoài để sắp xếp khi đối tượng cần sắp xếp lớn không thể lưu trữ trên bộ nhớ trong mà phải lưu trữ trên bộ nhớ ngoài. III. Phương pháp nghiên cứu Phương pháp Kiểu dữ liệu tập tin là kiểu thích hợp nhất cho việc biểu diễn dữ liệu được lư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. Bộ nhớ trong Bộ nhớ đệm Bộ nhớ ngoài 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 . 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 Trộn F1 và F2 vào F Cho tới khi số đoạn trong F chỉ còn một. 1.2.a Giải thuật phân đoạn Phân file F thành 2 file F1 và F2. Bước 1: Mở file F để đọc, mở file F1 và F2 để ghi, khởi gán giá trị đầu số đoạn con = 0 { sodoancon:=0 }; Bước 2: Thực hiện cho tới khi đọc hết file F - Nếu chưa hết file F thực hiện việc đọc phần tử (PT) của F và ghi nó vào F1 cho đến khi gặp PT nhỏ hơn PT trước nó hoặc hết file F, tăng số đoạn con lên 1, {inc(sodoancon)}; - Nếu chưa hết file F thực hiện việc đọc PT để của F và ghi nó vào F2 cho đến khi gặp PT nhỏ hơn PT trước nó hoặc hết file F; tăng số đoạn con lên 1, {inc(sodoancon)}; Bước 3: Đóng file F1, F2, F. Ví dụ: Cho file F gồm 21 mẫu tin với khóa là các số nguyên như sau: 3 65 6 15 29 20 25 5 31 40 12 50 67 45 9 18 34 17 11 98 8 3 65 6 15 29 20 25 5 31 40 12 50 67 45 9 18 34 17 11 98 8 Phân file F thành 2 file F1 và F2 Lần 1: 3 65 F1 F2 6 15 29 Lần 2: F1 3 65 20 25 F2 6 15 29 5 31 40 Lần 3: F1 3 65 20 25 12 50 67 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; 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 i1. 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. i2. 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, ngược lại nếu file F2 chưa kết thúc thì ghi các phần tử còn lại của nó sang F; Bước 4: Đóng file F1, F2, F; Ví dụ: Cho file F gồm 21 mẫu tin với khóa là các số nguyên như sau: 3 65 6 15 29 20 25 5 31 40 12 50 67 45 9 18 34 17 11 98 8 Qua thủ tục phân đoạn ở ví dụ trong 2.2.1 ta có: F1 3 65 20 25 12 50 67 9 18 34 11 98 F2 6 15 29 5 31 40 45 17 8 Thực hiện trộn: 3 6 15 29 65 5 20 25 31 40 12 45 50 67 9 17 18 34 8 11 98 Giải thuật sắp xếp trộn thực hiện luân phiên 2 thủ tục phân đoạn và trộn. Sắp xếp bằng trộn tự nhiên file F : 3 65 6 15 29 20 25 5 31 40 12 50 67 45 9 18 34 17 11 98 8 Lần 1: - Phân đoạn: F1 3 65 20 25 12 50 67 9 18 34 11 98 F2 6 15 29 5 31 40 45 17 8 - Trộn: 3 6 15 29 65 5 20 25 31 40 12 45 50 67 9 17 18 34 8 11 98 Lần 2: - Phân đoạn: F1 3 6 15 29 65 12 45 50 67 8 11 98 F2 5 20 25 31 40 9 17 18 34 - Trộn: 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 3 5 6 15 20 25 29 31 40 65 8 11 98 F2 9 12 17 18 34 45 50 67 - 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; Begin Assign(F,'chinh'); Reset(F); Assign(F1,'phu1'); Rewrite(F1); Assign(F2,'phu2'); Rewrite(F2); Numsub:=0; while not eof(F) do begin saodoancon(F,F1,kt); inc(numsub); if not eof(F) then begin saodoancon(F,F2,kt); inc(Numsub); end; end; close(F); close(F1); close(F2); End; Thủ tục sao 1 đoạn con từ file F vào file T Procedure SaoDoancon(var F,T:FileType; var kt:boolean); {Sao 1 doan con co thu tu F vao T} Begin kt:=false; while not kt do SaoBg(F,T,kt); End; {________________________________________________________} Procedure SaoBg(var F,T: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 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); if v1<v2 then SaoBg(F1,F,kt1) else SaoBg(F2,F,kt2); end; while not eof(F1) do begin Saodoancon(F1,F,kt1); end; while not eof(F2) do begin Saodoancon(F2,F,kt2); end; close(F); close(F1); close(F2); End; 1.4 Đánh giá giải thuật Trong GT phân đoạn hoặc trộn ta có thể dùng mảng hoặc DSLK để thay thế cho các file F1 và F2 nếu không gian bộ nhớ trong cho phép. Độ phức tạp của GT này là O(nlogn). 2. sắp xếp ngoài bằng phương pháp trộn khác ( phương pháp 2) 2.1 Tư tưởng: Sắp xếp tập tin F dùng 4 tập tin F1, F2 ,G1, G2 + Tách tập tin F thành 2 tập tin F1, F2 + Trộn các tập tin con trong hai tập tin F1, F2 thành tập tin lớn có thứ tự rồi ghi luân phiên vào trong G1, G2. 2.2 Giải thuật: Để sắp xếp tập tin F có n mẩu tin ta sử dụng 4 tập tin F1, F2, G1, G2. Khởi đầu ta phân phối các mẩu tin của tập tin F đã cho luân phiên vào hai tập tin F1, F2. Như vậy hai tập tin này được xem như được tổ chức thành các đường có độ dài 1. Bước 1: Đọc 2 đường mỗi đường có độ dài 1 từ 2 tập tin F1, F2 và trộn đường này thành đường độ dài 2 và ghi luân phiên vào trong hai tập tin G1, G2. Đổi vai trò của F1 cho G1, F2 cho G2. Bước 2: Đọc 2 đường, mỗi đường độ dài 2 từ hai tập tin F1, F2 và trộn hai đường này thành đường có độ dài 4 và ghi luân phiên vào trong G1, G2. Đổi vai trò của F1 cho G1, F2 cho G2. Quá trình trên cứ tiếp tục và sau i bước thì độ dài của một đường là 2i. Nếu 2i = n thì giải thuật kết thúc, lúc đó tập tin G2 sẽ rỗng và tập tin G1 sẽ chứa các mẩu tin đã được sắp xếp. Ví dụ: Cho tập tin F gồm có 21 mẩu tin với khóa là các số nguyên như sau: 3 65 6 15 29 20 25 5 31 40 12 50 67 45 9 18 34 17 11 98 8 Để bắt đầu ta phân phối các mẩu tin của F luân phiên vào hai tập tin F1, F2 được tổ chức thành các đường có độ dài 1. 3 6 29 25 31 12 67 9 34 11 8 F1 65 15 20 5 40 50 45 18 17 98 F2 Bước 1: Trộn các đường có độ dài 1 của F1 và F2 được các đường có độ dài 2 và ghi luân phiên vào trong hai tập tin G1 và G2: G1 3 65 20 29 31 40 45 67 17 34 8 F1 G2 6 15 5 25 12 50 9 18 11 98 F2 Bước 2: Đổi vai trò F1 và G1, F2 và G2 cho nhau. Trộn các đường độ dài 2 trong tập tin F1 và F2 đựợc các đường có độ dài 4 rồi ghi luân phiên vào trong hai tập tin G1 và G2: G1 3 6 15 65 12 31 40 50 11 17 34 98 F1 G2 5 20 25 29 9 18 45 67 8 F2 Bước 3: Đổi vai trò của F1 vaf G1, F2 và G2 cho nhau. Trộn các đường có độ dài 4 trong hai tập tin F1 và F2 được các đường có độ dài 8 rồi ghi luân phiên vào trong hai tập tin G1 và G2: G1: 3 5 6 15 20 25 29 65 8 11 17 34 98 F1 G2 9 12 18 31 40 45 50 67 F2 Bước 4: Đổi vai trò của F1 và G1, F2 và G2 cho nhau. Trộn các đường có độ dài 8 trong hai tập tin F1 và F2 được các đường có độ dài 16 rồi ghi luân phiên vào trong hai tập tin G1 và G2: G1 3 5 6 9 12 15 18 20 25 29 31 40 45 50 65 67 F1 G2 8 11 17 34 98 F2 Bước 5: Đổi vai trò của F1 và G1, F2 và G2 cho nhau. Trộn các đường có độ dài 16 trong tập tin F1 và F2 được một đường có độ dài 21 rồi ghi vào trong tập tin G1: G1 3 5 6 8 9 11 12 15 17 18 20 25 29 31 34 40 45 50 65 67 98 Tập tin G1 chứa các mẩu tin đã được sắp xếp còn tập tin G2 rỗng 2.3 Cài đặt chương trình: Procedure merge(k:interger; f1,f2,g1,g2: file of RecordType); Var Ok: boolean; x: interger; Used: array[1..2] of interger; Fin: array[1..2] of boolean; Current: array[1..2] of RecordType; Procedure GetRecord(i:interger); Begin Used[i] := used[i] + 1; If (used[i] =k+1) or (i =1) and ( eof(f1) ) or (i = 2 and ( eof(f2) ) then fin[i] := TRUE else if i=1 then Read( f1,current[1] ) else read( f2, current[2]); End; Begin ok:= TRUE; Reset(f1); Reset(f2); Rewrite(g1); Rewrite(g2); While ( not eof(f1) ) or ( not eof(f2)) do begin Used[1] := 0 ; Used[2] := 0 ; Fin[1] := FALSE ; Fin[2] := FALSE ; GetRecord(1) ; GetRecord(2) ; While (not fin[1]) or (not fin[2]) do begin if Fin[1] then x := 2 else if Fin[2] then x := 1 else if current[1].key < current[2].key then x :=1 else x :=2; if ok then Write( g1, current[x] ) else Write( g2, currenrt[x] ); GetRecord(x) ; end; ok := not ok ; End ; End ; 2.4 Đánh giá giải thuật: a. Độ phức tạp: Ta thấy giải thuật kết thúc khi i>=logn. Mỗi bước phải đọc từ 2 tập tin và ghi vào 2 tập tin, mỗi tập tin có trung bình n/2 mẩu tin. Giả sử mỗi một khối lưu trữ được b mẫu tin thì mỗi bước cần đọc và ghi 2*2*n/2*b =2n/b khối mà chúng ta cần logn bước vậy tổng cộng chúng ta cần (2n/b)logn phép truy xuất khối. vậy độ phức tạp của giải thuật này là: O(nlogn). b. Ưu điểm và nhược điểm của giải thuật: Qua quá trình phân tích ta thấy giải thuật này có khả năng sắp xếp rất nhanh vì chỉ sắp xếp từng khối nhỏ và độ phức tạp của nó O(nlogn) nhỏ hơn nhiều so với các phương pháp sắp xếp trong như sắp xếp chọn (Selection), sắp xếp xen (Insertion sort), sắp xếp nổi bọt (Bubble sort) có độ phức tạp là O(n). Tuy nhiên bên cạnh đó ta cũng thấy khả năng truy xuất khối của nó phải nhiều nên mất thời gian. 3. Cải tiến sắp xếp trộn (phương pháp 3) 3.1 Tư tưởng Cũng giống như tư tưởng của sắp xếp trộn đầu tiên để sắp xếp tập tin F có n mẩu tin ta cũng sử dụng 4 tập tin F1,F2,G1,G2. Sau đó ta phân phối các mẩu tin đã cho F luân phiên vào trong 2 tập tin F1,F2. Nhưng cải tiến hơn sắp xếp trộn là ta không chọn đường độ dài là 1 mà ta chọn một số k thích hợp sao cho k mẩu tin có thể đủ nhớ trong bộ nhớ trong. 3.2 Giải thuật Để sắp xếp tập tin F có n mẩu tin ta cũng sử dụng 4 tập tin F1,F2,G1,G2. Khởi đầu: Ta phân phối các mẫu tin của tập tin đã cho F luân phiên vào trong 2 tập tin F1,F2. Ta giả sử bộ nhớ trong có thể chứa được k mẩu tin. Như vậy 2 tập tin này được xem như được tổ chức thành các đương độ dài k. Bước 1: Đọc 2 đường, mỗi đường độ dài k từ 2 tập tin F1,F2 và trộn 2 đường này thành đường độ dài 2k và ghi luân phiên vào 2 tập tin G1,G2. Đổi vai trò của F1 cho G1 và F2 cho G2. Bước 2:Đọc 2 đường,mỗi đường độ dài 2k từ hai tập tin F1,F2 và trộn 2 đường này thành đường độ dài 4k và ghi luân phiên vào trong 2 tập tin G1,G2. Đổi vai trò của F1 cho G1,F2 cho G2. Quá trình trên cứ tiếp tục và sau i bước thì độ dài của 1 đường là k*2i. Nếu k*2i> n thì giải thuật kết thúc,lúc đó tập tin G2 sẽ rỗng và tập tin G1 chứa các mẩu tin được sắp. Ví dụ minh họa: Lấy tập tin F có 21 mẫu tin với khóa là các số nguyên : 3 65 6 15 29 20 25 5 31 40 12 50 67 45 9 18 34 17 11 98 8 Ta giả sử bộ nhớ trong có thể chứa đươc 3 mẩu tin, ta đọc lần lượt 3 mẩu tin của F vào bộ nhớ trong,dùng một sắp xếp trong để sắp xếp chúng và ghi phiên vào 2 tập tin F1 và F2. 3 6 65 5 25 31 9 45 67 8 11 98 F1 15 20 29 12 40 50 17 18 34 F2 Bước 1: Trộn các đường độ dài 3 của F1 và F2 được các đường độ dài 6 và ghi luân phiên vào trong 2 tập tin G1 và G2: 3 6 15 20 29 65 9 17 18 34 45 67 G1 5 12 25 31 40 50 8 11 98 G2 Bước 2:Đổi vai trò của F1 và G1,F2 và G2 cho nhau. Trộn các đường độ dài 6 trong 2 tập tin F1 và F2 được các đường độ dài 1 rồi ghi luân phiên vào trong 2 tập tin G1 và G2: 3 5 6 12 15 20 25 29 31 40 50 65 8 9 11 17 18 34 45 67 98 Bước 3: Đổi vai trò của F1 và G1,F2 và G2 cho nhau. Trộn các đường độ dài 12 trong 2 tập tin F1 và F2 được 1 đường ghi vào trong tập tin G1,còn G2 rỗng : 3 5 6 8 9 11 12 15 17 18 20 25 29 31 34 40 45 50 65 67 98 Tập tin G1 chứa các mẩu tin đã được sắp còn tập tin G2 rỗng. 3.3 Đánh giá giải thuật a. Độ phức tạp: Ta thấy quá trình sắp xếp trộn nói trên bắt đầu từ các độ dài 1 cho nên phải sau logn bước giải thuật mới kết thúc. Chúng ta có thể tiết kiệm thời gian bằng cách chọn một số k thích hợp sao cho k mẩu tin có thể đủ chứa trong bộ nhớ trong. Mỗi lần đọc vào bộ nhớ trong k mẩu tin,dùng sắp xếp trong(chẳng hạn dùng Quick sort) để sắp xếp k mẩu tin này và ghi luân phiên vào hai tập tin F1 và F2. Như vậy chúng ta bắt đầu sắp xếp trộn với các tập tin dược tổ chức thành các đường độ dài k . Sau i bước thì độ dài mỗi đường là k*2i . Giải thuật sẽ kết thúc khi k*2i ≥ n hay i ≥ log n/k. Do đó số phép truy xuất khối sẽ là 2*n/b log(n/k). Dễ thấy 2*n/b log(n/k) < 2*n/b logn tức là ta tăng được tốc độ sắp xếp trộn. Vậy độ phức tạp của giải thuật này là: O(nlog(n/k)) b. Ưu điểm, nhược điểm: ♣ Ưu điểm: ♦Chúng ta đã giảm được số lần truy xuất khối tức là tăng được tốc độ sắp xếp trộn. ♦Chương trình ngắn gọn hơn,không phải đọc và ghi nhiều lần. ♣ Nhược điểm: ♦ Tốn thời gian sắp xếp ở bộ nhớ trong. 4. Trộn nhiều đường (phương pháp 4) 4.1 Tư tưởng Sắp xếp tập tin F ta dùng m tập tin F1, F2 ,F3…..Fm( m là số chẵn, m>4) + Tách tập tin F thành h tập tin F[1], F[2], F[3],…… F[h] với h=m/2 + Trộn các tập tin con trong h tập tin F[1], F[2], F[3],…… F[h] thành tập tin lớn có thứ tự rồi ghi luân phiên vào trong F[h+1], F[h+2], F[h+3],… F[m]. 4.2 Giải thuật Để sắp xếp tập tin F có n mẫu tin ta sử dụng m tập tin (m là số chẵn). Ta gọi h=m/2. Giả sử bộ nhớ trong có thể chứa k mẫu tin. Khởi đầu: Mỗi lần đọc từ tập tin F vào bộ nhớ trong k mẫu tin, sử dụng một sắp xếp trong để sắp xếp k mẫu tin này thành một đường rồi ghi luân phiên vào các tập tin F[1], F[2], F[3],…… F[h]. Bước 1: _ Trộn các đường độ dài k của h tập tin F[1], F[2], F[3],…… F[h] thành một đường độ dài k*h. _ Ghi luân phiên vào trong h tập tin F[h+1], F[h+2], F[h+3],.. F[m]. _ Đổi vai trò của F[i] và F[h+i] cho nhau. Bước 2: _ Trộn các đường độ dài k*h của h tập tin F[1], F[2], F[3],…… F[h] thành một đường độ dài k*h2. _ Ghi luân phiên vào trong h tập tin F[h+1], F[h+2], F[h+3],… F[m]. _ Đổi vai trò của F[i] và F[h+i] cho nhau. Sau i bước thì ta được độ dài mỗi đường là k*hi và giải thuật kết thúc khi k*hi>=n và khi đó ta được tập tin đã sắp xếp chính là 1 đường ghi trong F[h+1]. Ví dụ: Lấy tập tin F có 21 mẫu tin với khóa là các số nguyên như ví dụ ban đầu. Ta sử dụng 6 tập tin để sắp xếp tập tin F. Cho k=3. Ta lầ lượt đọc 3 mẫu tin của F vào bộ nhớ trong, dùng sắp xếp trong để sắp xếp và ghi luân phiên vào 3 tập tin F[1], F[2], F[3] : 3 65 6 15 29 20 25 5 31 40 12 50 67 45 9 18 34 17 11 98 8 3 6 65 12 40 50 8 11 98 F[1] 15 20 29 9 45 67 F[2] 2 25 31 17 18 34 F[3] Bước 1: Trộn các đường độ dài 3 trong các tập tin F[1], F[2], F[3] thành các đường độ dài 9 và ghi vào trong các tập tin F[4], F[5], F[6] 3 5 6 15 20 25 29 31 65 F[4]  9 12 17 18 34 40 45 50 67 F[5] 8 11 98 F[6] Đổi vai trò của F[1] cho F[4], F[2] cho F[5], F[3] cho F[6] Bước 2: Trộn các đường độ dài 9 trong các tập tin F[1], F[2], F[3] thành 1 đường độ dài 23 và ghi vào trong tập tin F[4] 3 5 6 8 9 11 12 15 17 18 20 25 29 31 34 40 45 50 65 67 98 F[4] Tập tin F[4] chứa 21 mẫu tin đã được sắp xếp còn F[5], F[6] rỗng. 4.3. Cài đặt chương trình:( tham khảo chương trình chạy bằng C++) #include #include #include #include #include #define N 10 // dùng 10 tập tin typedef int elem; typedef struct { FILE *f; elem buffer;//so phan tu cua file }tape; void taofile(char *fn, int n)//tao file co ten fn co n pt { int i; FILE *f=fopen (fn, "wb"); randomize(); for(i=0; i<n;i++) { int x=random(50); fwrite(&x,2,1,f); } fclose(f); } void infile(char *fn)//in file vua tao { FILE *f=fopen (fn, "rb"); int x; fread(&x,2,1,f); while(!feof(f)) { printf("%8d", x); fread(&x,2,1,f); } fclose(f); } void opentape(tape &X,char *fn) //mo tape ra de doc { X.f=fopen(fn,"rb"); //doc tu file ra buffer fread(&X.buffer,sizeof(elem),1,X.f); } void readtape(tape &X,elem &x) //doc ra cho pt x { memcpy(&x,&X.buffer,sizeof(elem)); //gan buffer cho x fread(&X.buffer,sizeof(elem),1,X.f); //luc nay X^ chinh la buffer } void copyitem(tape &X,tape &Y,int &EOR) //copy 1pt tu tape X vao Y co ktra EOR { elem x; readtape(X, x); //doc pt tu tape X vao x fwrite(&x,sizeof(elem), 1, Y.f); //ghi truc tiep vao file Y EOR=feof(X.f) || x>X.buffer; //(x>X.buffer)tra ve eof(ss dung compaid) } //chep 1 run void copyrun(tape &X,tape &Y) { int EOR; do { copyitem(X,Y,EOR); }while(!EOR); //copy den khi nao het run } //int n=10; void hoanvi(int &a, int &b) { int t; t=a; a=b; b=t; } void multiway (char *fn) { int q, k1, k2, j, mx, ta[N], t[N], EOR; tape f[N], F; char s[N][20],s1[20]; //N chuoi, moi chuoi co 19 ki tu int k=N/2; opentape (F,fn ); for(int i=0; i<N; i++) { strcpy(s[i], "TMP."); itoa(i, s1, 10); strcat(s[i], s1); } for(i=0; i<k; i++) f[i].f = fopen(s[i], "wb"); i = 0; q = 0; do { copyrun(F,f[i]); q = q+1; i = (i<k-1? i+1:0); } while (!feof(F.f)); fclose(F.f); for(i=0; i<k; i++) fclose(f[i].f); for(i=0; i<N; i++) t[i] = i; do{ k1= (q<k ? q : k); j = k; q = 0; for(i=0; i<k; i++) { opentape (f[t[i]], s[t[i]] ); f[t[i+k]].f = fopen(s[t[i+k]], "wb"); } for (i=0; i<k1; i++) ta[i]=t[i]; do { k2 = k1; do{ mx = 0; for (i=1; i<k2; i++) if (f[ta[mx]].buffer>f[ta[i]].buffer) mx = i; copyitem(f[ta[mx]], f[t[j]], EOR); if(feof(f[ta[mx]].f)) { k2--; k1--; ta[mx]=ta[k2]; ta[k2]=ta[k1]; } else if (EOR) { k2--; hoanvi(ta[mx], ta[k2]); } } while (k2>0); q = q+1; j = (j==N-1? k+1 : j+1); } while (k1>0); for(i=0; i<N; i++) fclose(f[i].f); for(i=0; i<k; i++) hoanvi(t[i], t[i+k]); } while(q>1); opentape (f[t[0]], s[t[0]] ); F.f = fopen(fn, "wb"); copyrun(f[t[0]], F); fclose(F.f); fclose(f[t[0]].f); } void main() { clrscr(); printf("tao file\n"); taofile("text.txt",100); infile("text.txt"); printf("\nsau khi tron:\n"); multiway("text.txt"); infile("text.txt"); getch(); } 4.4. Đánh giá giải thuật: a. Độ phức tạp: Ta thấy giải thuật kết thúc khi k.hi>=n hay i>=logh(n/k). Mỗi bước ta phải đọc từ h tập tin và ghi vào h tập tin, mỗi tập tin có trung bình n/h mẩu tin. Giả sử mỗi một khối lưu trữ được b mẫu tin thì mỗi bước cần đọc và ghi 2*h*n/h*b =2n/b khối mà chúng ta cần log(n/k) bước. Vậy tổng cộng chúng ta cần (2n/b)logh(n/k) phép truy xuất khối. Vậy độ phức tạp của giải thuật này là: O(nlogh(n/k)). b. Ưu điểm và nhược điểm của giải thuật: Ưu điểm: Với bài toán dữ liệu lớn thì giải thuật này giúp: Chúng ta giảm được số lần truy xuất khối đi rất nhiều tức là tăng được tốc độ sắp xếp trộn. Chương trình ngắn gọn hơn, không phải đọc và ghi nhiều lần.