HỌC VIỆN KỸ THUẬT QUÂN SỰ
KHOA CÔNG NGHỆ THÔNG TIN
******
*****

BÁO CÁO
PHÂN TÍCH & THIẾT KẾ GIẢI
THUẬT
ĐỀ TÀI:”Thiết kế bài toán sắp xếp dãy số
theo giá trị”

Giáo viên hướng dẫn: Hà Đại Dương
Sinh viên thực hiện:

Lê Văn Nhật

Lớp : HTTT 14

1


Hà Nội, Tháng 1 Năm 2018

Mục Lục
1. Nêu bài toán...........................................................................3
2. Mô tả chi tiết thuật toán.........................................................3
3. Thực hiện với 5 bộ dữ liệu với n>=10.....................................4
4. Viết chương trình....................................................................7
5. Đánh giá độ phức tạp thuật toán theo lý thuyết và bằng thực
nghiệm, so sánh kết quả.............................................................9

2


Đề bài: ( Đề 2) Thiết kế thuật toán sắp xếp theo phương pháp
chia để trị, thuật toán MergeSort, với các công việc sau:
1. Nêu bài bài toán;
2. Mô tả chi tiết thuật toán;
3. Tự xác định 5 bộ dữ liệu ( với số phần tử của mảng
>=10), vỡi mỗi bộ dữ liệu hãy thực hiện từng bước
thuật toán đã mô tả ở mục 2 và ghi ra kết quả mỗi
bước;
4. Viết chương trình sử dụng C, C++
5. Đánh giá độ phức tạp thuật toán theo lý thuyết và bằng
thực nghiệm, so sánh kết quả;
6. Viết bào cáo ( trình bày các nội dung từ 1-5).
Bài làm :
1. Nêu bài toán
Cho mảng gồm n phần tử A[1…n], sắp xếp mảng A theo
thứ tự tăng dần.
2. Mô tả chi tiết thuật toán
 Mảng có 1 phần tử là mảng đã sắp xếp
 Nếu có hai mảng a và b đã được sắp xếp, tiến hành
trộn hai dãy này thành dãy c đã được sắp xếp.
 Nếu chia nhỏ mảng cần sắp xếp thành các đoạn 1
phần tử thì nó là đoạn được sắp xếp.
 Tiến hành ghép các đoạn nhỏ thành các đoạn lớn hơn
đã được sắp xếp.
a) Ý tưởng thao tác trộn
 Ý tưởng thuật toán:
3



- Chúng ta sẽ chia mảng lớn thành những mảng con
nhỏ hơn bằng cách chia đôi mảng lớn và chúng ta
tiếp tục chia đôi các mảng con cho tới khi mảng
con nhỏ nhất chỉ còn 1 phần tử. Sau đó chúng ta
sẽ tiếng hành so sánh 2 mảng con có cùng mảng
cơ sở (khi chúng ta chia đôi mảng lớn thành 2
mảng con thì mảng lớn đó chúng ta gọi là mảng cơ
sở của 2 mảng con đó) khi so sánh chúng sẽ vừa
sắp xếp vừa ghép 2 mảng con đó lại thành mảng
cơ sở, chúng ta tiếp tục so sánh và ghép các mảng
con lại đến khi còn lại mảng duy nhất thì đó là
mảng đã được sắp xếp
- Cách thức thực hiện ý tưởng :
 Duyệt trên dãy a tại vị trí i ( i là vị trí bắt đầu
của dãy a )
 Duyệt trên dãy b tại ví trí j ( j là vị trí bắt đầu
của dãy b )
 Nếu a[i]>b[j] thì thêmb[j] vào trong dãy c tăng
biến j ngược lại thêm a[i] vào dãy và tang biến i
 Nếu một trong 2 dãy hết trước thỳ tiến hành đưa
toàn bộ dãy còn lại vào trong dãy c
 Áp dụng trong trường hợp a, b là 2 đoạn của
mảng
- a ( left, mid ), b ( mid +1, right )
- array( left , right )
 Để thuận tiện xử lý thỳ ta sẽ trả lại toàn bộ giá
trị vào mảng ban đầu .
Giải mã:

o Input: a ( left , mid ) , a ( mid , right )
o Output: array(left , right ) được sắp xếp không
giảm.
4


1. i =left
2. j = mid +1
3. k = left
4. while( i < mid && j < right )
if ( a[i] < a[j] )
array[k] = a[i]
i++
else
array[k] = a[j]
j++
k++
5. while ( i<= mid )
array[k] =a[i]
i++
k++
6. while ( j <=right )
array[ k ]= a[j]
j++
k++
7. for( int i=1;i<=right;i++)
array[i] = a[i]

b. Thuật toán sắp xếp trộn ( MergeSort)
 Thuật toán sắp xếp trộn mergesort

 Input: a[left…right]
5


 Output: a[left…right] đã được sắp xếp
1. if( left>= right) return;
2. mid= ( left+right) / 2
3. mergesort( left , mid);
4. mergesort( mid+1, right );
5. merge ( a[left…mid ], a[ mid +1, right ];
3. Thực hiện với 5 bộ dữ liệu với n>=10.
a. Với mảng a= { 4, 15, 3, 17, 9, 12, 1, 4, 20, 11}, n=10
4, 15, 3, 17, 9, 12, 1, 4,
20, 11
4, 15, 3, 17, 9
4 , 15 , 3

17,
9

4,
15

3

17

4

15


4,
15
3, 4, 15

12, 1, 4 , 20 , 11
12, 1 ,4

20,
11

9

12,
1

4

3

9,
17

12

1

4

11,

20

3

9,17

1,
12

4

11,
20

1, 4, 12

11,
20

9,
17

3, 4, 9, 15, 17

20

11

1, 2, 11, 12, 20


1, 2, 3, 4, 9, 11, 12, 15,
17, 20
b. Với mảng a={ 2, 30, 11, 10, 3, 1, 22, 12, 19, 4, 1, 9 },
n=12
2, 30, 11, 10, 3, 1, 22, 12, 19,
6


4, 1, 9
2, 30, 11, 10, 3, 1

22, 12, 19, 4, 1, 9

2, 30, 11

10, 3, 1

22, 12,
19

4, 1, 9

2,3
0

11

10,
3


1

22,1
2

19

4,1

9

2

30

10

3

12

19

1

9

2,3
0


11

3,10

1

12,2
2

19

1,4

9

11

2,11,30

1

22

1,3,10

4

12,19,22

1,2,3,10,11,30


1,4,9

1,4,9,12,19,22

1,1,3,4,,9,10,11,12,19,22,30
c. Với mảng a= { 67, 34, 12, 2, 4, 11, 23, 1, 9, 3 }
67, 34, 12, 2, 4, 11, 23,
1, 9, 3
67, 34, 12, 2, 4
67, 34, 12
67,3
4

12

67

34

34,6
7
12,34,67

11, 23, 1, 9, 3

2,4
2

11, 23, 1


9,3

4

11,2
3

1

12

2,4

11

23

1

3,9

12

2,4

11,2
3

1


3,9

1,11,23

3,9

2,4

2, 4, 12, 34, 67

9

3

1, 3, 9, 11, 23
7


1, 2, 3, 4, 9, 11, 12, 23,
34, 67
d.Với mảng a= { 45, 88, 12, 3, 17, 36, 21, 1, 6, 45}, n=10
45, 88, 12, 3, 17, 36,
21, 1, 6, 45
45, 88, 12, 3, 17
45, 88, 12

45,
88


3,
17

12

45

88

45,88

36, 21, 1, 6, 45

3

36, 21, 1

17

12

3,17

12

3,17

12, 45, 88

36,

21
36

1

6

21

3, 12, 17, 45, 88

45

1

6,45

1

6,45

1,21,36

6,45

36, 21

3,17

6,

45

1, 6, 21, 36, 45

1, 3, 6, 12, 17, 21, 36, 45, 45, 88
e.Với mảng a= { 4, 3, 1, 56, 23, 99, 11, 12, 96, 19}, n=10
4, 3, 1, 56, 23, 99, 11,
12, 96, 19
4, 3, 1, 56, 23

4, 3, 1

4, 3

1

4

3

99, 11, 12, 96,
19

56,
23
56

1

99, 11, 12


23

99,
11

12

23,5

99

11

96,
19
96

12

19

19,9
8


6
3,4

1


1,3,4

23,5
6
23,5
6

1, 3, 4, 23, 56

6
11,9
9

12

19,9
6

11,12,99

19,9
6

11, 12, 19, 96,
99

1, 3, 4, 11, 12, 19, 23, 56, 96, 99
4. Viết chương trình
#include<iostream>

using namespace std;
void Merge(int array[], int left, int mid, int right);
// left, right la bien trai va bien phai cua mang
void MergeSort(int array[], int left, int right)
{
if (right > left)
{
int mid; // Phan tu o giua
mid = (left + right) / 2;
MergeSort(array, left, mid); // Goi de quy mang con ben trai
MergeSort(array, mid + 1, right); // Goi de quy mang con ben phai
Merge(array, left, mid, right); // Goi ham so sanh hai mang con
}
}
void Merge(int array[], int left, int mid, int right)
{
int *temp; // Khoi tao mang tam de sap xep
int i = left; // Vi tri phan tu dau tien cua mang con ben trai
int j = mid + 1; // Vi tri phan tu dau tien cua mang con ben phai
temp = new int[right - left + 1]; // Khoi tao so luong phan tu cua mang tam
for (int k = 0; k <= right - left; k++)
{
// Kiem phan tu cua mang con ben trai va ben phai
if (array[i] < array[j])
{
// Neu a[i] < a[j] thi copy phan tu ben trai vao mang tam
temp[k] = array[i];
i++; // Vi tri phan tu tiep theo cua mang
}
else // Nguoc lai copy phan tu cua mang con ben phai vao mang tam

{
temp[k] = array[j];
j++; // Vi tri phan tu tiep theo cua mang

9


}
// Kiem tra mang con ben trai con phan tu nao khong
if (i == mid + 1)
{
// Nguoc lai dua cac phan tu con lai cua mang con ben phai vao mang

tam

}

while (j <= right)
{
k++;
temp[k] = array[j];
j++;
}
break;

// Kiem tra mang con ben phai con phan tu nao khong
if (j == right + 1)
{
// Nguoc lai dua cac phan tu con lai cua mang con ben phai vao mang


tam

}

while (i <= mid)
{
k++;
temp[k] = array[i];
i++;
}
break;

}

}

for (int k = 0; k <= right - left; k++) // Chep mang tam vao mang chinh
array[left + k] = temp[k];
delete temp;

int main()
{
int array[] = { 9,8,7,1,2,3,4,5,6 };
int length = sizeof(array) / sizeof(array[0]);
cout << " Day so ban dau : ";
for (int i = 0; i < length; i++)
cout << array[i] << " ";
cout << endl;
MergeSort(array, 0, length - 1);
cout << " Day sau khi da sap xep la : ";

for (int i = 0; i < length; i++)
cout << array[i] << " ";
cout << endl;
system("pause");
return 0;
}

Kết quả :

10


5. Đánh giá độ phức tạp thuật toán theo lý thuyết và
bằng thực nghiệm, so sánh kết quả.
a. Theo lý thuyết
C( n)
với n =
n0
T( n) =
T( k) + T( n- k) + Cn
với n>k>n0
 T( k) : thời gian sắp xếp mảng với k phần
tử
 T( n- k) : thời gian sắp xếp mảng với n- k
phần tử
 Cn : tổng thời gian sắp xếp lại mảng a.
Ta sẽ sắp xếp 2 mảng:
 Mảng 1: có n/2 phần tử
 Mảng 2: có n/ 2 phần tử
 T( n) = 2 T( n/ 2) + Cn


(1)

= 2[ 2T( n/ 4) + Cn/ 2] + Cn = 4T( n / 4) + 2Cn
= 8T( n / 8 ) + 3Cn
………………….
= T( n/ ) + kCn
(1)
Dừng lại khi đạt được T( 1)

 n=

 k=
11


 T( n) = nT( 1) + )Cn
Độ phức tạp của thuật toán là : O(nlog n )

12