Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 53
}
else
{ Temp[J2] = M[I1]
J2 ;
}
Head = 0-Head;
K1 = K2 = 0;
break;
}
}
}
return;
}
//========================================================
void StraightMergeSortModify(T M[], int N)
{ int L = 1 ;
T * Temp = new T[N];
if (Temp == NULL)
return;
while (L < N)
{ MergeDistribute(M, N, Temp, L);
L = 2*L;
if (L >= N)
{ for (int I = 0; I < N; I++)
M[I] = Temp[I];
break;
}
MergeDistribute(Temp, N, M, L);
L = 2*L;

a
n
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!

c
k
.
c
o
m
Giáo trình hướng dẫn sử dụng thuật tốn hiệu chỉnh
trong phân phối các cặp đường chạy lập trình
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 54
chạy có thể có chiều dài lớn hơn. Điều này sẽ giảm bớt số lần phân phối và trộn
các cặp đường chạy cho chúng ta. Thuật giải trộn tự nhiên được trình bày sau đây
sẽ loại bỏ được nhược điểm này của thuật giải trộn thẳng.
b. Thuật toán sắp xếp trộn tự nhiên (Natural Merge Sort):
- Tư tưởng:
Tận dụng các đường chạy tự nhiên có sẵn trên dãy, tiến hành trộn tương ứng các
cặp đường chạy tự nhiên nằm hai đầu dãy M thành một đường chạy mới và phân
phối luân phiên các đường chạy mới này về hai đầu dãy phụ Temp. Sau đó lại tiếp
tục trộn tương ứng từng cặp run ở hai đầu dãy phụ Temp thành một run mới và phân
phối luân phiên run mới này về hai đầu dãy M. Cứ tiếp tục như vậy cho đến khi trên
M hoặc trên Temp chỉ còn lại 01 run thì kết thúc.
- Thuật toán Trộn – Phân phối các cặp đường chạy tự nhiên:
B1: I1 = 1 // Chỉ số từ đầu dãy M
B2: I2 = N // Chỉ số từ cuối dãy M
B3: J1 = 1 // Chỉ số từ đầu dãy Temp
B4: J2 = N // Chỉ số từ cuối dãy Temp
B5: Head = True // Cờ báo phía đặt run mới trong quá trình trộn - phân phối
B6: IF (I1 > I2) // Đã trộn và phân phối hết các run
Thực hiện Bkt
B7: IF (M[I1] ≤ M[I2]) // M[I1] đứng trước M[I2] trên Temp

h
a
n
g
e

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

a
c
k
.
c
o
m
.
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 55
B8.5: If (M[I2] < M[I2+1]) //Đã duyệt hết 1 run phía sau trong M
Thực hiện B15
B8.6: Lặp lại B7
//Chép phần run còn lại ở phía sau trong M về Temp
B9: IF (M[I2] < M[I2+1]) //Đã chép hết phần run còn lại ở phía sau trong M về Temp
B9.1: Head = Not(Head)
B9.2: Lặp lại B6
B10: IF (Head = True)
B10.1: Temp[J1] = M[I2]
B10.2: J1++
B11: ELSE
B11.1: Temp[J2] = M[I2]
B11.2: J2
B12: I2
B13: IF (I1> I2)
Thực hiện Bkt
B14: Lặp lại B9
//Chép phần run còn lại ở phía trước trong M về Temp
B15: IF (M[I1]< M[I1-1]) //Đã chép hết phần run còn lại phía trước trong M về Temp
B15.1: Head = Not(Head)

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
.
c

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: 56
// Chép các phần tử từ Temp về M
B6.1: I = 1
B6.2: If (I > N)
Thực hiện Bkt
B6.3: M[I] = Temp[I]
B6.4: I++
B6.5: Lặp lại B6.2
B7: Trộn_Phân_Phối(Temp, N, M, L)
B8: Lặp lại B4
Bkt: Kết thúc
- Cài đặt thuật toán trộn tự nhiên:
Hàm NaturalMergeSort có prototype như sau:
void NaturalMergeSort(T M[], int N);
Hàm thực hiện việc sắp xếp N phần tử có kiểu dữ liệu T trên mảng M theo thứ tự
tăng dựa trên thuật toán sắp trộn trực tự nhiên. Hàm sử dụng hàm
NaturalMergeDistribute có prototype và ý nghóa như sau:
void NaturalMergeDistribute(T M[], int N, T Temp[], int &L);
Hàm thực hiện việc trộn các cặp run ở hai đầu dãy M mà run đầu tiên có chiều dài L

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
k

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: 57
I2 ;
}
if (Head == 1)
{ Temp[J1] = M[I2];
J1++;
If (FirstPair == 1)
L++;
}
else
{ Temp[J2] = M[I2];
J2 ;
}
I2 ;
FirstPair = 0;
if (I1 > I2)
return;

J2 ;
}
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
-

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