Bài giảng Cấu trúc dữ liệu nâng cao - Chương 1: Sắp xếp ngoại

bo luan phien cac Run tu nhien tu F0 vao
F1 va F2*/
{
do
{
CopyRun(F0,F1);
if( !feof(F0) ) CopyRun(F0,F2);
}while( !feof(F0) );
}
Trương Hải Bằng - Cấu trúc dữ liệu 2 30
2. Phương pháp trộn tự nhiên (tt)
void CopyRun(FILE *Fi,FILE *Fj)
/*Chep 1 Run tu Fi vao Fj */
{
do
Copy(Fi,Fj);
while ( !Eor);
}
Trương Hải Bằng - Cấu trúc dữ liệu 2 31
2. Phương pháp trộn tự nhiên (tt)
void MergeRun()
/* Tron 1 Run cua F1 va F2 vao F0 */
{
do
{
fscanf(F1,"%3d",&X1);
long curpos = ftell(F1)-2;
fseek(F1, curpos, SEEK_SET);
fscanf(F2,"%3d",&X2);
curpos = ftell(F2)-2;
fseek(F2, curpos, SEEK_SET);
}
Trương Hải Bằng - Cấu trúc dữ liệu 2 32
2. Phương pháp trộn tự nhiên (tt)
if( X1 <= X2 )
{
Copy(F1,F0);
if (Eor) CopyRun(F2,F0);
}
else
{
Copy(F2,F0);
if ( Eor ) CopyRun(F1,F0);
}
} while ( !Eor );
Trương Hải Bằng - Cấu trúc dữ liệu 2 33
2. Phương pháp trộn tự nhiên (tt)
void Merge()
/* Tron cac run tu F1 va F2 vao F0 */
{
while( (!feof(F1)) && (!feof(F2)) )
{
MergeRun();
M++;
}
while( !feof(F1) )
{
CopyRun(F1,F0);
M++;
}
while( !feof(F2) )
{
CopyRun(F2,F0);
M++;
}
}
Trương Hải Bằng - Cấu trúc dữ liệu 2 34
3. Trộn n-đường cân bằng
Thuật toán sắp xếp ngoài thực hiện qua 2 giai
đoạn:Phân phối và trộn
•Giai đoạn nào góp phần làm thay đổi thứ tự ?
•Chi phí cho giai đoạn phân phối ?
Rút ra kết luận
• Thay vì thực hiện 2 giai đoạn, ta chỉ thực hiện
1 giai đoạn “Trộn”
• Tiết kiệm được khoảng ½ chi phí copy
• Cần số lượng file trung gian gấp đôi
Trương Hải Bằng - Cấu trúc dữ liệu 2 35
3. Trộn n-đường cân bằng (tt)
Chi phí sắp xếp ngoài tỉ lệ với số bước thực hiện
Nếu mỗi bước cần N thao tác copy, và dùng 2 
file trung gian: cần log2N bước . cần N*log2N 
thao tác copy
Để giảm số bước : phân bố các run lên nhiều
hơn 2 file trung gian
Như vậy:
Dùng nhiều file trung gian để giảm số bước
Tiết kiệm chi phí copy bằng cách thực hiện 1 
giai đoạn
Sử dụng 2*n file trung gian
Trương Hải Bằng - Cấu trúc dữ liệu 2 36
3. Trộn n-đường cân bằng (tt)
Thuật toán tổng quát (tinh chế 0)
[BƯỚC 1] Gọi tập nguồn là S = {f1, f2, … , fn}
Gọi tập đích là D = {g1, g2, … , gn}
Chia xoay vòng dữ liệu của file fInput cho các file thuộc
tập nguồn S, mỗi lần 1 run cho đến khi file fInput hết
[BƯỚC 2] Trộn từng bộ run của các file thuộc tập nguồn
S, tạo thành run mới, lần lượt ghi lên các file thuộc tập đích
D
[BƯỚC 3] Nếu (số run trên các file thuộc D > 1) thì
- Hoán vị vai trò của tập nguồn (S) và tập đích (D)
- Quay lại [B2]
Ngược lại Kết thúc thuật toán
Trương Hải Bằng - Cấu trúc dữ liệu 2 37
3. Trộn n-đường cân bằng (tt)
VD. fInput: U Q N M K I H F D C B, N=3
// Phân phối (lần 1)
f1: U M H C
f2: Q K F B
f3: N I D
// Trộn (lần 1)
g1: N Q U B C
g2: I K M
g3: D F H
Trương Hải Bằng - Cấu trúc dữ liệu 2 38
3. Trộn n-đường cân bằng (tt)
„ // Trộn (lần 2)
„ f1: D F H I K M N Q U
„ f2: B C
„ f3: NULL
„ // Trộn (lần 3)
„ g1: B C D F H I K M N Q U
„ g2: NULL
„ g3: NULL
Trương Hải Bằng - Cấu trúc dữ liệu 2 39
3. Trộn n-đường cân bằng (tt)
Các ký hiệu:
fInput: file dữ liệu gốc cần sắp xếp
N: số phần tử trên file fInput
n: số file trung gian trên mỗi tập nguồn/đích
S: tập các file nguồn
D: tập các file đích
Sdd: tập các file nguồn đang còn run dở dang
Str: tập các file nguồn chưa hết (!EOF), còn có
thể tham gia vào quá trình trộn
Trương Hải Bằng - Cấu trúc dữ liệu 2 40
3. Trộn n-đường cân bằng (tt)
“Lượt”: là 1 quá trình trộn run từ nguồn . đích, một
“luợt” kết thúc khi mỗi file
đích (trong tập D) nhận được 1 run
Drun: tập các file đích đã nhận được run trong “lượt”
hiện hành
Suy diễn:
S – Str: tập các file nguồn đã hết (EOF)
Str – Sdd: tập các file nguồn chưa hết (!EOF), nhưng đã
kết thúc run hiện tại
D – Drun: tập các file đích chưa nhận được run trong
“lượt” hiện hành
Trương Hải Bằng - Cấu trúc dữ liệu 2 41
3. Trộn n-đường cân bằng (tt)
[BƯỚC 1]
S = {f1, f2, … , fn}
D = {g1, g2, … , gn}
// Chia xoay vòng dữ liệu của file fInput cho các file thuộc tập
nguồn S
i = 1;
while (!feof(fInput)) {
Copy_1_Run(fInput, fi);
i = (i % n) + 1;
}S
tr = S;
Drun = {};
nDemRun = 0;
Trương Hải Bằng - Cấu trúc dữ liệu 2 42
3. Trộn n-đường cân bằng (tt)
[BƯỚC 2]
a. Sdd = Str
b. Gọi dhh Ỵ D – Drun là file đích hiện hành
(sẽ được nhận run)
c. Đọc các phần tử xfi, fi Ỵ Sdd
d. Gọi xf0 = MIN { xfi, fi Ỵ Sdd}
e. Copy xf0 lên dhh
Trương Hải Bằng - Cấu trúc dữ liệu 2 43
3. Trộn n-đường cân bằng (tt)
f. Nếu (file f0 hết) thì {
Str = Str – {f0}
Sdd = Sdd – {f0}
Nếu (Str == {}) thì { // Xong quá trình trộn N . D
nDemRun++;
Goto [B3]
}
ngược lại Nếu (Sdd {}) thì Goto [B2.d]
ngược lại { // Sdd=={}: hết bộ run hiện hành
nDemRun++;
Drun = Drun + {dhh};
Nếu (Drun==D) thì Drun= {}; // Xong 1 “lượt”
Goto [B2.a]
Trương Hải Bằng - Cấu trúc dữ liệu 2 44
3. Trộn n-đường cân bằng (tt)
ngược lại { // File f0 chưa hết
Nếu (!EOR(f0)) thì {
Đọc phần tử kế xf0 từ file f0;
Goto [B2.d]
}
ngược lại { // Hết run hiện hành trên f0
Sdd = Sdd – {f0}
Nếu (Sdd {}) thì Goto [B2.d]
ngược lại { // Sdd=={}: hết bộ run hiện hành
nDemRun++;
Drun = Drun + {dhh};
Nếu (Drun==D) thì Drun= {}; // Xong 1 “lượt”
Goto [B2.a]
Trương Hải Bằng - Cấu trúc dữ liệu 2 45
3. Trộn n-đường cân bằng (tt)
} // end of file f0 chưa hết
Thuật toán chi tiết…(tt):
[BƯỚC 3] Nếu (nDemRun == 1) thì Kết thúc thuật toán
ngược lại {
Nếu (nDemRun < n) thì Str = Drun; // Không đủ n run
ngược lại Str = D;
Drun = {};
nDemRun = 0;
“Hoán vị tập S, D”
Goto [B2]
}
Trương Hải Bằng - Cấu trúc dữ liệu 2 46
4. Phương pháp trôn đa pha
Phương pháp trộn đa lối cân bằng đã loại bỏ các
phép sao chép thuần túy thông qua việc gộp quá
trình phân phối và qúa trình trộn trong cùng một giai
đoạn. Tuy nhiên các tập tin các tập tin chưa được sử
dụng một cách có hiệu quả bởi vì trong cùng một lần
duyệt thì phân nửa số tập tin luôn luôn giữ vai trò
trộn (nguồn) và phân nửa số tập tin luôn luôn giử
vai trò phân phối (đích). Ta có thể cải tiến phương
pháp trên bằng cách giải quyết thay đổi vai trò của
các tập tin trong cùng một lần duyệt phương pháp
này gọi là phương pháp trộn đa pha.
Trương Hải Bằng - Cấu trúc dữ liệu 2 47
4. Phương pháp trôn đa pha (tt)
Phương pháp sắp xếp kiểu này do R.L. Gilstar
nêu ra năm 1960 và được gọi là trộn đa pha. Có
thể thấy ngay là để cho quá trình trộn đa pha
thực hiện được thì dữ liệu ban đầu phải được
phân bổ một cách thích hợp trên các băng
nguồn. Ví dụ nếu ta có 2 băng nguồn là T1, T2 
và một băng đích là T3. Nếu số run trong T1 và
trong T2 là các số Fibonacci liên tiếp thì ta có
thể áp dụng phuơng pháp trộn đa pha như sau:
Trương Hải Bằng - Cấu trúc dữ liệu 2 48
4. Phương pháp trôn đa pha (tt)
T1 T2 T3
Fn (= Fn-1+Fn-2) Fn-1
Fn-2 Fn-1 (= Fn-2+Fn-3)
Fn-2 (= Fn-3+Fn-4) Fn-3
Fn-3 (= Fn-4+Fn-5) Fn-4
... ... ...
Ví dụ với n = 7 ta có F7 = 13, F6 = 8.
Quá trình trộn được mô tả trong bảng sau:
Trương Hải Bằng - Cấu trúc dữ liệu 2 49
4. Phương pháp trôn đa pha (tt)
T1 T2 T3 Giải thích
13 8 Lúc đầu có 13 run trong T1 và 8 run trong T2
5 8 Trộn 8 run trong mỗi run vào T3, T1 còn 5 run
5 3 Trộn 5 run vào T2, trong T3 còn 3 run...
3 2
1 2
1 1 Trộn 1 run trong T1 với 1 run trong T3 ở bước trước vào
T2, T3 còn lại 1 run.
1 Trộn 1 run trong T2 với 1 run trong T3 ở bước trước vào
T1, chỉ còn lại một run, quá trình kết thúc.
Trương Hải Bằng - Cấu trúc dữ liệu 2 50
4. Phương pháp trôn đa pha (tt)
Böôùùc 1: Phaânâ phoáái luaânâ phieânâ caùùc run ban ñaààu
cuûûa f1 vaøøo f2 vaøø f3
Böôùùc 2: Troään caùùc run cuûûa f1, f2 vaøøo f3 . Giaûûi
thuaäät keáát thuùùc neááu f3 chæ coùù moäät run
Böôùùc 3: Cheùùp nöûûa run cuûûa f3 vaøøo f1
Böôùùc 4: Troään caùùc run cuûûa f1 vaøø f3 vaøøo f2. Giaûûi
thuaäät keáát thuùùc neááu f2 chæ coùù moäät run.
Böôùùc 5: Cheùùp nöûûa soáá run cuûûa f2 vaøøo f1. Laëëp laïïi
böôùùc 2.
Trương Hải Bằng - Cấu trúc dữ liệu 2 51
4. Phương pháp trôn đa pha (tt)
„ Ví duïï 1: Tröôøøng hôïïp n=7, toåång soáá run ban ñaààu laøø
13+8=21 run
Phase F 1 F2 F3
0 1, 1, 1, 1, 1, 1, 1, 1 1, 1, 1, 1, 1 Sort
1 1, 1, 1, 2, 2, 2, 2, 2 Merge 1
2 3, 3, 3 2, 2 Merge 2
3 5, 5 3 Merge 3
4 5 8 Merge4
5 13 Merge 5
6 21 Merge 6
Trương Hải Bằng - Cấu trúc dữ liệu 2 52
4. Phương pháp trôn đa pha (tt)
„ Phase 0: Phaânâ phoáái caùùc run ban ñaààu
„ Phase 1: Troään 8 run cuûûa f1 vaøø f2 vaøøo f3
„ Phase 2: Troään 5 run cuûûa f1 vaøø f3 vaøøo f2
„ Phase 3: Troään 3 run cuûûa f2 vaøø f3 vaøøo f1
„ Phase 4: Troään 2 run cuûûa f1 vaøø f2 vaøøo f3
„ Phase 5: Troään 1 run cuûûa f1 vaøø f3 vaøøo f2
„ Phase 6: Troään 1 run cuûûa f2 vaøø f3 vaøøo f1
Trương Hải Bằng - Cấu trúc dữ liệu 2 53
4. Phương pháp trôn đa pha (tt)
Phase T6 T5 T4 T3 T2 T1 Toåång soáá runs ñöôïïc xöõõ lyùù
Phase 0 131 130 128 124 116 - 129
Phase 1 115 114 112 18 - 516 80
Phase 2 17 16 14 - 98 58 72
Phase 3 13 12 - 174 94 54 68
Phase 4 11 - 332 172 92 52 66
Phase 5 - 651 331 171 91 51 65
Phase 6 1291 - - - - - 129
Trương Hải Bằng - Cấu trúc dữ liệu 2 54
4. Phương pháp trôn đa pha (tt)
„ Phase 0: Phaânâ phoáái caùùc run ban ñaààu
„ Phase 1: Troään 16 run töøø T2 ñeáán T6 vaøøo T1
„ Phase 2: Troään 8 run cuûûa T1, T3, T4, T5, T6 vaøøo T2
„ Phase 3: Troään 4 run cuûûa T1, T2, T4, T5, T6 vaøøo T3
„ Phase 4: Troään 2 run cuûûa T6, T5, T3, T1, T6 vaøøo T4
„ Phase 5: Troään 1 run cuûûa T1, T2, T3, T4, T6 vaøøo T5
„ Phase 6: Troään 1 run töøø T1 ñeáán T5 vaøøo T6.
Trương Hải Bằng - Cấu trúc dữ liệu 2 55
4. Phương pháp trôn đa pha (tt)
„ Trong ví duïï 1, soáá run phan phoáái ban ñaààu cho caùùc taääp
tin laøø 2 soáá Fibonacci keáá tieááp nhau cuûûa daõyõ Fibonacci 
baääc 1:
0, 1, 1, 2, 3, 5, 8 . . . 
„ Trong ví duïï 2 soáá run ban ñaààu phaânâ boáá cho caùùc taääp
tin theo daõyõ Fibonacci baääc 4:
0, 0, 0, 0, 1, 1, 2, 4, 8, 16 . . .
„ Daõyõ Fibonacci baääc P toåång quaùùt ñöôïïc ñònh nghóa nhö
sau:
F(p)n = F(p)n-1 + ... + F(p)n-2 + ... + F(p)n-p
vôùùi n>=p , F(p)n = 0, vôùùi 0 <= n <= p-2; F(p)p-1 = 1