Cấu trúc dữ liệu và giải thuật lưu trữ ngoài – VOER

Sắp xếp dữ liệu được tổ chức như một tập tin hoặc tổng quát hơn, sắp xếp dữ liệu được lưu trên bộ nhớ ngoài gọi là sắp xếp ngoài.

Sắp xếp trộn (merge sorting)

Khái niệm về đường

Ðường độ dài k là một tập hợp k mẩu tin đã đựoc sắp thứ tự theo khoá tức là, nếu các mẩu tin r1,r2,…,rk có khoá lần lượt là k1,k2,…,kk tạo thành một đường thì k1≤ k2 ≤ … ≤ kk.

Cho tập tin chứa các mẩu tin r1,r2,…,rn, ta nói tập tin được tổ chức thành đường có độ dài k nếu ta chia tập tin thành các đoạn k mẩu tin liên tiếp và mỗi đoạn là một đường, đoạn cuối có thể không có đủ k mẩu tin, trong trường hợp này ta gọi đoạn ấy là đuôi (tail).

Ví dụ 4-1: Tập tin gồm 14 mẩu tin có khóa là các số nguyên được tổ chức thành 4 đường độ dài 3 và một đuôi có độ dài 2

5
6
9
13
26
27
1
5
8
12
14
17
23
25

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 và 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 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 độ dài 1.

Bước 1: Ðọc 2 đường, mỗi đường độ dài 1 từ hai tập tin F1, F2 và trộn hai đườ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 độ dài 4 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.

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 chứa các mẩu tin đã được sắp.

Ðánh giá giải thuật sắp xếp trộn

Ta thấy giải thuật kết thúc sau i bước với 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*n2*b=2nb size 12{ { {“2*2*n”} over {“2*b”} } = { {“2n”} over {b} } } {} khối mà chúng ta cần logn bước vậy tổng cộng chúng ta cần
2nblogn size 12{ { {“2n”} over {b} } “logn”} {} phép truy xuất khối.

Ví dụ 4-2: Cho tập tin F có 23 mẩu tin với khóa là các số nguyên như sau:

2 31 13 5 98 96 10 40 54 85 65 9 30 39 90 13 10 8 69 77 8 10 22.

Ðể 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 và F2 được tổ chức thành các đường có độ dài 1

2
13
98
10
54
65
30
90
10
69
8
22
F1

31
5
96
40
85
9
39
13
8
77
10

F2

Bước 1: Trộn các đường độ dài 1 của F1 và F2 được các đường độ dài 2 và ghi luân phiên vào trong hai tập tin G1, G2:

G1
2
31
96
98
54
85
30
39
8
10
8
10
F1

G2
5
13
10
40
9
65
13
90
69
77
22

F2

Bước 2: Ðổi vai trò của F1 và G1, F2 và G2 cho nhau. Trộn các đường độ dài 2 trong hai tập tin F1 và F2 được các đường độ dài 4 rồi ghi luân phiên vào trong hai tập tin G1 và G2:

G1
2
5
13
31
9
54
65
85
8
10
69
77
F1

G2
10
40
96
98
13
30
39
90
8
10
22

F2

Bước 3: Ðổi vai trò của F1 và G1, F2 và G2 cho nhau. Trộn các đường độ dài 4 trong hai tập tin F1 và F2 được các đường độ dài 8 rồi ghi luân phiên vào trong hai tập tin G1 và G2:

G1
2
5
10
13
31
40
96
98
8
8
10
10
22
69
77
F1

G2
9
13
30
39
54
65
85
90

F2

Bước 4: Ðổi vai trò của F1 và G1, F2 và G2 cho nhau. Trộn các đường độ dài 8 trong hai tập tin F1 và F2 được các đường độ dài 16 rồi ghi luân phiên vào trong 2 tập tin G1 và G2.

G1
2
5
9
10
13
13
30
31
39
40
54
65
85
90
96
98
F1

G2
8
8
10
10
22
69
77

F2

Bước 5: Ðổi vai trò của F1 và G1, F2 và G2 cho nhau. Trộn các đường độ dài 16 trong hai tập tin F1 và F2 được 1 đường độ dài 23 rồi ghi vào trong tập tin G1.

G1
2
5
8
8
9
10
10
10
13
13
22
30
31
39
40
54
65
69
77
85
90
96
98

Tập tin G1 chứa các mẩu tin đã được sắp còn tập tin G2 rỗng.

Chương trình

procedure Merge(k:integer; f1,f2,g1,g2: File of RecordType);

{Thủ tục này trộn các đường độ dài k và trong hai tập tin f1 và f2 thành các đường đọ dài 2k và ghi luân phiên vào trong hai tập tin g1 và g2}

var

OutSwithh : boolean; {Nếu OutSwitch = TRUE thì ghi vào tập tin g1, ngược lại ghi vào g2}

Winner: integer; {Ðể chỉ định mẩu tin hiện hành nào trong hai tập tin f1 và f2 sẽ được ghi ra tập tin g1 hoặc g2}

Used: array[1..2] of integer; { Used[ij] ghi số mẩu tin đã được đọc trong đường hiện tại của tập tin fj }

Fin : array[1..2] Of boolean; {Fin[j] sẽ có giá trị TRUE nếu đã đọc hết các mẩu tin trong đường hiện hành của fj họac đx dến cuối tập tin fj }

Current: array[1..2] Of RecordType; { Current[j] để lưu mẩu tin hiện hành của tập tin f[j]}

procedure GetRecord(i:integer);

{Nếu đã đọc hết các mẩu tin trong đường hiện hành của tập tin fi hoặc đã đến cuối tập tin fi thì đặt fin[i] = TRUE nếu không thì đọc một mẩu tin của tập tin fi vào trong current[i]}

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

{ Khởi tạo }

OutSwitch := TRUE;

ReSet(f1);

ReSet(f2);

ReWrite(g1);

ReWrite(g2);

while (not eof(f1)) or (not eof(f2)) do begin

{Bắt đầu đọc các mẩu tin từ trong hai đường hiện hành của hai tập tin f1,f2 }

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

{Trộn hai đường }

{ Chọn Winner }

if Fin[1] then Winner := 2

else if Fin[2] then Winner := 1

else if current[1].key < Current[2].key then

Winner := 1

else Winner := 2;

if OutSwitch then Write(g1, Current[winner] )

else Write(g2, current[winner] );

GetRecord(Winner);

end;

OutSwitch := Not OutSwitch;

end;

end;

We will be happy to hear your thoughts

Leave a reply

Đỉnh Review
Logo