Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 58
I1++;
}
if (Head == 1)
{ Temp[J1] = M[I1];
J1++;
}
else
{ Temp[J2] = M[I1];
J2 ;
}
I1++;
FirstPair = 0;
if (I1 > I2)
return;
Head = 0 – Head;
break;
}
}
if (I1 == I2)
{ Temp[J1] = M[I1];
if (I1 == N-1)
L = N;
return;
}
}
return;
}
//========================================================
void NaruralMergeSort1(T M[], int N)

e

V
i
e
w
e
r
w
w
w
.
d
o
c
u
-
t
r
a
c
k
.
c
o
m
Click to buy NOW!
P
D
F

c
o
m
.
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 59
}
- Ví dụ minh họa thuật toán:
Giả sử ta cần sắp xếp mảng M có 10 phần tử sau (N = 10):
M: 51 39 45 55 20 15 20 17 40 10
Ta thực hiện các lần trộn các cặp run tự nhiên ở hai đầu dãy này và kết hợp phân
phối các run mới trộn về hai đầu dãy kia như sau:
Lần 1: L = 1
Trộn các cặp run tự nhiên có chiều dài L1 = 1 và L2 = 2 trên M thành các run có
chiều dài L = 3 và kết hợp phân phối luân phiên các run này về hai đầu dãy Tmp:

M: 51 39 45 55 20 15 20 17 40 10 Tmp: 10 40 51 15 20 55 45 39 20 17

Đổi vai trò của M và Tmp cho nhau

M: 10 40 51 15 20 55 45 39 20 17
Lần 2: L = 3
Trộn các cặp run tự nhiên có chiều dài L1 = 3 và L2 = 5 trên M thành các run có
chiều dài L = 8 và kết hợp phân phối luân phiên các run này về hai đầu dãy Tmp:

M: 10 40 51 15 20 55 45 39 20 17


g
e

V
i
e
w
e
r
w
w
w
.
d
o
c
u
-
t
r
a
c
k
.
c
o
m
Click to buy NOW!
P
D

.
c
o
m
.
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 60
L = 10: Kết thúc thuật toán
- Phân tích thuật toán trộn tự nhiên:
+ Trong trường hợp tốt nhất, khi dãy có thứ tự tăng thì chúng ta không phải qua
bước phân phối và trộn nào hết:
Số phép gán: Gmin = 1
Số phép so sánh: Smin = 2(N-1) + 2 = 2N
Số phép hoán vò: Hmin = 0
+ Trong trường hợp xấu nhất, khi dãy có thứ tự giảm ở nửa đầu và có thứ tự tăng ở
nửa cuối và ở mỗi bước trộn phân phối thì độ dài đường chạy mới cũng chỉ tăng
gấp đôi. Trong trường hợp này sẽ giống như thuật toán trộn thẳng đã hiệu chỉnh:
Số phép gán: Gmax = N×Log
2
(N)+1
Số phép so sánh: Smax = 2N×Log
2
(N)+2
Số phép hoán vò: Hmin = 0
+ Trung bình:
Số phép gán: Gavg = N×Log
2
(N)/2+1
Số phép so sánh: Savg = N×Log
2

-
X
C
h
a
n
g
e

V
i
e
w
e
r
w
w
w
.
d
o
c
u
-
t
r
a
c
k
.

-
t
r
a
c
k
.
c
o
m
.
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 61
Các thuật toán sắp xếp bằng phương pháp trộn trên tập tin bao gồm:
- Thuật toán sắp xếp trộn thẳng hay trộn trực tiếp (straight merge sort),
- Thuật toán sắp xếp trộn tự nhiên (natural merge sort),
- Thuật toán trộn đa lối cân bằng (multiways merge sort),
- Thuật toán trộn đa pha (multiphases merge sort).
Ở đây chúng ta chỉ nghiên cứu hai thuật toán trộn đầu tiên.
a. Thuật toán sắp xếp trộn trực tiếp (Straight Merge Sort):
- Tư tưởng:
Tương tự như thuật toán trộn trực tiếp trên mảng, ban đầu tập tin Fd có N run(s) với
chiều dài mỗi run: L = 1, ta tiến hành phân phối luân phiên N run(s) của tập tin Fd
về K tập tin phụ Ft1, Ft2, …, FtK (Mỗi tập tin phụ có N/K run(s)). Sau đó trộn tương
ứng từng bộ K run(s) ở K tập tin phụ Ft1, Ft2, …, FtK thành một run mới có chiều
dài L = K để đưa về tập tin Fd và tập tin Fd trở thành tập tin có N/K run(s) với chiều
dài mỗi run: L = K.
Như vậy, sau mỗi lần phân phối và trộn các run trên tập tin Fd thì số run trên tập tin
Fd sẽ giảm đi K lần, đồng thời chiều dài mỗi run trên Fd sẽ tăng lên K lần. Do đó,
sau Log

D
F
-
X
C
h
a
n
g
e

V
i
e
w
e
r
w
w
w
.
d
o
c
u
-
t
r
a
c

c
u
-
t
r
a
c
k
.
c
o
m
.
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 62
B13: IF (K > L)
Thực hiện B19
B14: fread(&a, sizeof(T), 1, Fd) //Đọc 1 phần tử của run trên Fd ra biến tạm a
B15: fwrite(&a, sizeof(T), 1, Ft2) //Ghi giá trò biến tạm a vào tập tin Ft2
B16: K++
B17: IF (feof(Fd)) //Đã phân phối hết
Thực hiện Bkt
B18: Lặp lại B13
B19: Lặp lại B4
Bkt: Kết thúc
- Thuật toán trộn:
B1: Ft1 = fopen(DataTemp1, “r”) //Mở tập tin trung gian thứ nhất để đọc dữ liệu
B2: Ft2 = fopen(DataTemp2, “r”) //Mở tập tin trung gian thứ hai để đọc dữ liệu
B3: Fd = fopen(DataFile, “w”) //Mở tập tin dữ liệu để ghi dữ liệu
B4: fread(&a1, sizeof(T), 1, Ft1) //Đọc 1 phần tử của run trên Ft1 ra biến tạm a1

B16: Lặp lại B11
Click to buy NOW!
P
D
F
-
X
C
h
a
n
g
e

V
i
e
w
e
r
w
w
w
.
d
o
c
u
-
t

.
d
o
c
u
-
t
r
a
c
k
.
c
o
m
.