TỔNG LIÊN ĐOÀN LAO ĐỘNG VIỆT NAM
TRƯỜNG ĐẠI HỌC TÔN ĐỨC THẮNG
KHOA CÔNG NGHỆ THÔNG TIN

PHÂN TÍCH VÀ THIẾT KẾ GIẢI THUẬT

BÀI TẬP LỚN 1

Người hướng dẫn: Thầy NGUYỄN CHÍ THIỆN
Người thực hiện: NGUYỄN DUY HÀN LÂM (MSSV: 51403229)
Lớp

: 14050301
Khoá

THÀNH PHỐ HỒ CHÍ MINH, NĂM 2014
TỔNG LIÊN ĐOÀN LAO ĐỘNG VIỆT NAM

: 18


TRƯỜNG ĐẠI HỌC TÔN ĐỨC THẮNG
KHOA CÔNG NGHỆ THÔNG TIN

PHÂN TÍCH VÀ THIẾT KẾ GIẢI THUẬT

BÀI TẬP LỚN 1

Người hướng dẫn: Thầy NGUYỄN CHÍ THIỆN
Người thực hiện: NGUYỄN DUY HÀN LÂM (MSSV: 51403229)
Lớp

:

14050301

Khoá

THÀNH PHỐ HỒ CHÍ MINH, NĂM 2014

: 18


3

BÀI TẬP LỚN ĐƯỢC HOÀN THÀNH
TẠI TRƯỜNG ĐẠI HỌC TÔN ĐỨC THẮNG
Tôi xin cam đoan đây là sản phẩm bài tập lớn của riêng tôi và được sự hướng
dẫn của Thầy Nguyễn Chí Thiện. Các nội dung nghiên cứu, kết quả trong đề tài này
là trung thực và chưa công bố dưới bất kỳ hình thức nào trước đây. Những số liệu
trong các bảng biểu phục vụ cho việc phân tích, nhận xét, đánh giá được chính tác
giả thu thập từ các nguồn khác nhau có ghi rõ trong phần tài liệu tham khảo.
Ngoài ra, trong bài tập lớn còn sử dụng một số nhận xét, đánh giá cũng như
số liệu của các tác giả khác, cơ quan tổ chức khác đều có trích dẫn và chú thích
nguồn gốc.
Nếu phát hiện có bất kỳ sự gian lận nào tôi xin hoàn toàn chịu trách
nhiệm về nội dung bài tập lớn của mình. Trường đại học Tôn Đức Thắng không
liên quan đến những vi phạm tác quyền, bản quyền do tôi gây ra trong quá trình
thực hiện (nếu có).
TP. Hồ Chí Minh, ngày 18 tháng 4 năm 2016
Tác giả

(ký tên và ghi rõ họ tên)

Nguyễn Duy Hàn Lâm


4

PHẦN XÁC NHẬN VÀ ĐÁNH GIÁ CỦA GIẢNG VIÊN
Phần xác nhận của GV hướng dẫn

______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
_____________________
Tp. Hồ Chí Minh, ngày tháng năm
(kí và ghi họ tên)

Phần đánh giá của GV chấm bài

______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________

_____________________
Tp. Hồ Chí Minh, ngày tháng năm
(kí và ghi họ tên)


5

MỤC LỤC


6

DANH MỤC CÁC BẢNG BIỂU, HÌNH VẼ, ĐỒ THỊ
DANH MỤC HÌNH, BẢNG BIỂU


7

CHƯƠNG 1: BÀI TOÁN SẮP XẾP
Sắp xếp là bài toán cơ bản của lĩnh vực khoa học máy tính và toán học. Được
sử dụng cho các thuật toán phức tạp hơn như các bài toán sắp xếp lịch trình, tìm
đường đi,... theo giải thuật tham lam. Ngoài ra bài toán sắp xếp cũng là một yếu tố
quan trong để phục vụ cho các bài toán thực tế đơn giản hơn như sắp xếp dữ liệu
của các tổ chức, công ty,... Vì giới hạn của đề tài nên tài liệu chỉ xin đề cập 5 giải
thuật sắp xếp cơ bản theo từng mục cụ thể sau đây.
Bài toán sắp xếp thật chất là việc so sánh các phần tử của một tập dữ liệu
theo một quy tắc nhất định (tăng dần, giảm dần, theo thứ tự trong bảng chữ cái,...)
sau đó hoán đổi vị trí của các phần tử của tập dữ liệu sao cho các phần tử của tập dữ
liệu từ không quy tắc trở thành tập dữ liệu theo một quy tắc đã được đề ra.


1.1 Selection Sort
1.1.1 Ý tưởng
Ý tưởng của việc sắp xếp chọn (Selection Sort) là việc ở mỗi phần tử của tập
dữ liệu ta tìm tiếp xem phần tử nhỏ nhất và nhỏ hơn nó trong mảng là phần tử nào ta
sẽ lưu lại vị trí của phần tử đặc biệt này và hoán đổi vị trí của phần tử được duyệt
tuần tự với phần tử tìm được.


8

1.1.2 Giải thuật
Algorithm SelectionSort(array A[0..n-1])
1. Integer min = 0
2. For (integer i = 0 to n -1) do
1) min = i
2) for (integer j = i + 1 to n – 1) do
a) if(A[min]>A[j])
min = j
b) end if
3) end for
4) if(A[min] != A[i])
a) swap(A[min], A[j]) // hoán đổi 2 phần tử A[min] và A[j]
5) end if
3. end for
4. end Algorithm

1.1.3 Cài đặt thuật toán
Xem ở file code đi chung với tập tài liệu này.

1.1.4 Độ phức tạp

Giải thuật phải tốn chi phí rất lớn do công đoạn chính nằm ở vòng lặp thứ 2
(bước 2.2)a) ) nên ta có như sau:
Đối với i =
1. Thì vòng lặp phải chạy (n – 1) – 1 + 1 = n – 1 lần công đoạn chính.
2. Thì vòng lặp phải chạy (n – 1) – 2 + 1 = n – 2 lần công đoạn chính.
3. Thì vòng lặp phải chạy (n – 1) – 3 + 1 = n – 3 lần công đoạn chính.
...
(n – 1). Thì vòng lặp phải chạy (n – 1) – (n – 1) + 1 = 1 lần công đoạn chính


9

Do đó ta có:

Vậy thuật toán có độ phức tạp là

1.1.5 Nhận xét
So với Insertion Sort và Bubble Sort sẽ trình bày bên dưới thì Selection Sort
sẽ có thời gian chạy thực tế nhanh hơn (mặc dù Insertion Sort và Bubble Sort có
cùng độ phức tạp là (trình bày lí do ở các mục phía dưới)) vì Selection Sort phải
tốn ít thời gian cho số lần hoán đổi ít hơn Insertion Sort và Bubble Sort.

1.2 Bubble Sort
1.2.1 Ý tưởng
Ý tưởng của phương đó là hoán đổi vị trí của 2 phần tử trong mảng cho đến
khi nào các phần tử trong mảng có vị trí đúng thứ tự theo yêu cầu.

1.2.2 Giải thuật
Algorithm BubbleSort(array A[0..n-1])
1. For (integer i = 0 to n – 1) do

1) For (integer j = n – 1 to i + 1) do
a) If(A[i]>A[j])
• Swap(A[i], A[j])
b) End if
2) End for
2. End for
3. End Algorithm

1.2.3 Cài đặt giải thuật
Xem ở file code đi chung với tập tài liệu này.

1.2.4 Độ phức tạp
Ta có thể dễ dàng thấy được thao tác căn bản là ở bước 1.1)a) do đó ta được:
Khi i =


10

1. Thì vòng lặp phải chạy n – 1 - 1 + 1 = (n – 1) thao tác căn bản.
2. Thì vòng lặp phải chạy n – 1 – 2 + 1 = (n – 2) thao tác căn bản
3. Thì vòng lặp phải chạy n – 1 – 3 + 1 = (n – 3) thao tác căn bản
...
(n – 1). Thì vòng lặp phải chạy (n – 1) – (n – 1) + 1 = 1 thao tác căn bản.
Do đó ta có:

Vậy thuật toán có độ phức tạp là

1.2.5 Nhận xét
Về phương diện lý thuyết, ta thấy bubble sort cũng có độ phức tạp là tuy
nhiên công đoạn swap của bubble sort phải thực hiện gọi hàm nhiều lần mà một

công đoạn hoán vị 2 phần tử tốn ít nhất 2 dòng lệnh còn selection sort chỉ tốn 1
dòng để lưu vị trí và số hoán đổi ít hơn bubble sort nên Bubble sort sẽ có thời gian
chạy thực tế lâu hơn Selection Sort và Insertion Sort.

1.3 Insertion Sort
1.3.1 Ý tưởng
Dùng một cái mốc và sẽ duyệt các phần tử phía mốc trở về trước các phần tử
sẽ dồn lên sao cho đúng trật tự mà tập dữ liệu được đề ra. Và phần tử bị đè sẽ được
chèn vào vị trí thích hợp sao cho đúng trật tự.


11

1.3.2 Giải thuật
Algorithm InsertionSort(array A[0..n – 1])
1. For (integer i = 1 to n – 1) do
1) Integer value = A[i]
2) Integer j = i - 1
3) While (j ≥ 0 and A[j] > value) do
a) A[j + 1] = A[j]
b) j = j – 1
4) end while
5) A[j + 1] = value
2. End for
3. End Algorithm

1.3.3 Cài đặt giải thuật
Xem ở file code đi chung với tập tài liệu này.

1.3.4 Độ phức tạp

Trong trường hợp xấu nhất thì vòng while phải dồn phần tử liên tục. Trong
trường hợp đó ta có:
Vậy thuật toán có độ phức tạp là

1.3.5 Nhận xét
Tuy nhiên giải thuật này thường không hoán vị nhiều như bubble sort và có
trường hợp chạy nhanh hoặc gần bằng selection sort.
Tóm lại trong cùng một đơn vị phức tạp là ta nên chọn theo thứ tự là
selection sort, insertion sort, bubble sort vì đó là thời gian thực thi thực tế giảm dần
(càng chậm dần) của các giải thuật.

1.4 Merge Sort
1.4.1 Ý tưởng


12

Giải thuật này có điểm độc đáo ở chỗ ta sẽ chia nhỏ tập dữ liệu ban đầu
thành nhiều tập dữ liệu mà mỗi tập dữ liệu con chỉ có 2 phần tử sau đó hoán vị
(hoặc không) 2 phần tử này sao cho đúng trật tự đã được yêu cầu. Sau đó trộn (gộp)
tất cả các tập dữ liệu con này thành tập dữ liệu mới  tập dữ liệu được tạo nên sẽ
có đúng trật tự yêu cầu do chúng được gộp từ tất cả tập dữ liệu con đúng trật tự.

1.4.2 Giải thuật
Procedure Merge(array left[0..x – 1], array right[0..y – 1], array A[0..n – 1])
1. Integer i, j, k
2. i = j = k = 0
3. while (i < (x – 1) and j < (y – 1))
1) if(left[i]<=right[j])
a) A[k] = left[i]

b) i = i + 1
2) end if
3) if(left[i] > right[j])


13

a) A[k] = right[j]
b) j = j + 1
4) end if
5) k = k + 1
4. end while
5. while(i < x – 1)
1) A[k] = left[i]
2) i = i + 1
3) k = k + 1
6. end while
7. while(j < y – 1)
1) A[k] = right[j]
2) j = j + 1
3) k = k + 1
8. end while
9. End Producer
Algorithm MergeSort(array A[0..n – 1])
1. Integer s = size of A
2. If (s > 1)
1) Integer mid = s/2;
2) Array left, Array right



14

3) For (integer i = 0 to mid - 1) do
a) Left[i] = A[i]
4) End for
5) For (integer i = mid to s – 1) do
b) Right[i] = A[i]
6) End for
7) MergeSort(left)
8) MergeSort(right)
9) Merge(left, right, A)
3. End if
4. End Algorithm

1.4.3 Cài đặt giải thuật
Xem ở file code đi chung với tập tài liệu này.

1.4.4 Độ phức tạp
Ta sẽ dễ dàng thấy được khi tập dữ liệu chỉ có 1 phần tử thì giải thuật sẽ
không làm gì cả. Còn có nhiều hơn 1 thì tập dữ liệu sẽ chia thành 2 tập dữ liệu con
và 1 hàm gộp (có độ phức tạp là n do chạy từ 0 cho đến phần tử cuối cùng của tập
dữ liệu gốc) từ đó ta thu được hệ thức truy hồi sau:
Ta có: a = 2; b = 2 và f(n) = n
Theo định lý Master ta thu được giải thuật có độ phức tạp là

1.4.5 Nhận xét
Trong trường hợp xấu nhất thì merge sort vẫn duy trì được trạng thái so với
Quick sort là tuy nhiên Merge Sort lại tốn rất nhiều không gian lưu trữ và chậm
hơn do phải tốn chi phí gọi hàm và thao tác gộp.



15

Tuy hơn quick sort trong trường hợp xấu nhất nhưng Quick sort lại tốt hơn
so với trường hợp trung bình do đó việc chọn lựa Quick Sort hay Merge Sort phải
tùy vào trạng thái dữ liệu đầu vào và kiến trúc máy tính xử lý thao tác.

1.5 Quick Sort
1.5.1 Ý tưởng
Ý tưởng của giải thuật sắp xếp nhanh (Quick Sort) đó là chọn một phần tử
trong mảng làm phần tử chốt (phần tử gốc) để đem đi so sánh với các phần tử khác
trong mảng. Sau đó những phần tử nào nhỏ hơn sẽ nằm bên trái và những phần tử
nào lớn hơn phần tử chốt thì nằm bên phải (đối với trường hợp cụ thể là sắp xếp tập
phần tử tăng dần).

1.5.2 Giải thuật
Procedure

Quick(array

A[0..n-1],

integer

left_position,

integer

right_position)
1. Integer x = A[0]

2. Integer i = left_position + 1
3. Integer j = right_position
4. Do{
1) While(i≤j and A[i]≤x)
a) i = i + 1
2) end while
3) while(i≤j and A[j]>x)
a) j = j – 1
4) end while
5) if(i≤j)
a. swap(A[i],A[j]) //hoán đổi 2 phần tử ở vị trí thứ i và j cho
nhau
b) i = i + 1
c) j = j – 1


16

6) end if
5. }while(i≤j);
6. Swap(A[left_position],A[j]) //hoán đổi phần tử cuối cùng đang dừng
lại ở vòng do...while với phần tử chốt
7. return j;
8. end Procedure
Algorithm

QuickSort(array

A[0..n-1],


integer

left_position,

integer

right_position)
1. If(left_position ≤ right_postion)
1) Integer vt = Quick(A, left_position, right_position)
2) QuickSort(A, left_position, vt – 1)
3) QuickSort(A, vt + 1, right_position)
2. End if
3. End Algorithm

1.5.3 Cài đặt thuật toán.
Xem ở file code đi chung với tập tài liệu này.

1.5.4 Độ phức tạp
Ở bước 1.1) ở phần mã giả ở trên có độ phức tạp là n và ở bước 2. và 3. bài
toán được gọi đệ quy nhưng chỉ lấy một nửa phần tử của mảng truyền vào để thực
thi nên ta được 2T(n/2). Từ đó ta thiết lập được hệ thức hồi quy sau:
Ta có: a = 2; b = 2 và f(n) = n
Theo định lý Master ta thu được giải thuật có độ phức tạp là

1.5.5 Nhận xét
Tuy bất lợi so với Merge Sort trong trường hợp xấu nhất nhưng bù lại quick
sort lại có lợi thế về bộ nhớ và độ chính xác cao so với merge sort nên việc chọn lựa


17


giữa quick sort và merge sort phải tùy theo trường hợp đầu vào mà quyết định thuật
toán.

1.6 Nhận xét chung
Đối với Selection Sort, Bubble Sort và Insertion Sort ta chỉ nên áp dụng cho
dữ liệu đầu vào nhỏ đủ để xử lý mặc dù các giải thuật này dễ hiểu và viết chương
trình.
Tuy nhiên để nâng cao tốc độ của chương trình với tập dữ liệu đầu vào lớn ta
nên dùng Quick Sort và Merge Sort do chúng có độ phức tạp thấp hơn rất nhiều (đã
chứng minh trên). Việc sử dụng Merge Sort hay Quick Sort còn phải phụ thuộc vào
nhiều yếu tố như tập dữ liệu đầu vào, kiến trúc của máy tính,...

CHƯƠNG 2: BÀI TOÁN TÌM KIẾM
2.1 Tìm kiếm tuần tự (Sequential Search)
2.1.1 Ý tưởng
Đơn giản là so sánh từng phần tử trong tập dữ liệu xem phần tử nào giống
với phần tử cần tìm thì trả ra kết quả vị trí của phần tử đó trong mảng nếu không
thấy thì trả ra kết quả -1 tương ứng dữ liệu cần tìm không có trong mảng.

2.1.2 Giải thuật
Algorithm SequentialSearch(array A[0..n – 1], <variable> finding_info)
1. For (integer i = 0 to n – 1) do
1) If (A[i] = finding_info)
a) Return i
2) End if
2. End for
3. Return -1
4. End Algorithm


2.1.3 Cài đặt giải thuật
Xem ở file code đi chung với tập tài liệu này.

2.1.4 Độ phức tạp


18

Ta có thể dễ dàng thấy chỉ có 1 vòng lặp duyệt từ phần tử đầu tiên của tập dữ
liệu cho đến phần tử cuối cùng của tập dữ liệu. Do đó ta thu được giải thuật có độ
phức tạp là

2.2 Tìm kiếm nhị phân (Binary Search)
2.2.1 Ý tưởng
Giải thuật này có ý tưởng tìm kiếm trên một tập dữ liệu đầu vào ĐÃ được
SẮP XẾP có trật tự (tăng dần hoặc giảm dần) nhờ đó ta có thể bỏ qua phần duyệt
các phần tử không cần thiết trong mảng. Giúp làm giảm thời gian tìm kiếm. Không
tìm thấy phần tử thì trả kết quả là -1.

2.2.2 Giải thuật
Note: Array A has been sorted
Algorithm BinarySearch(array A[0.. n – 1], <variable> finding_info)
1. Integer mid = 0
2. Integer left = 0
3. Integer right = n – 1
4. While (left ≤ right) do
1) Mid = (left + right) / 2
2) If (A[mid] = finding_info)
a) Return mid
3) End if

4) If(finding_info < A[mid])
a) Right = mid – 1
5) End if
6) If(finding_info > A[mid])
a) Left = mid + 1
7) End if
5. End while
6. Return -1
7. End Algorithm


19

2.2.3 Cài đặt giải thuật
Xem ở file code đi chung với tập tài liệu này.

2.2.4 Độ phức tạp
Ta giả sử rằng tập dữ liệu đầu vào được sắp xếp nên không cần tính độ phức
tạp của phần mục sắp xếp.
Ta thấy ở bước 4.1) ta đã vô tình chia một cách vô hình tập dữ liệu thành 2
phần nếu phần tử giữa tập dữ liệu bằng đúng dữ liệu cần tìm thì trả ra vị trí (mid)
(trường hợp tốt nhất Ω(1)). Nếu không ở các bước sau đó 4.4)a) hoặc 4.6)a) ta dịch
chuyển left và right sang vị trí mới đây chính là việc ta đã vô tình chia tập thành 2
phần và cứ chia 2 cho đến khi tìm thấy dữ liệu hoặc dừng việc chia khi gặp điều
kiện dừng của vòng while.
Do đó, ta được:
và T(n) = 0 khi n = 1
Giải phương trình trên ta được:
(1)
Phương trình ngừng khi:

T(n) = 0 khi n = 1
Thế vào (1) ta được:
Vậy giải thuật có độ phức tạp là

2.3 Cây nhị phân tìm kiếm (Binary Search Tree)
2.3.1 Ý tưởng
Dùng cấu trúc dữ liệu cây nhị phân để lưu trữ và tìm kiếm tập dữ liệu

2.3.2 Giải thuật
Algorithm BinarySearchTree(<node> root, <variable> finding_info)
1. If (root = null)
• Return -1
2. End if


20

3. If(root.data = finding_info)
• Return root.place //vị trí của phần tử
4. End if
5. If (finding_info < root.data)
• Return BinarySearchTree(root.left, finding_info)
6. End if
7. If (finding_info > root.data)
• Return BinarySearchTree(root.right, finding_info)
8. End if
9. End Algorithm

2.3.3 Cài đặt giải thuật
Xem ở file code đi chung với tập tài liệu này.


2.3.4 Độ phức tạp
Ở đây dữ liệu đầu vào không cần sắp xếp vì chúng đã theo cấu trúc cây nhị
phân. Tìm kiếm ở đây đã theo quy luật của cây nên chỉ cần duyệt một nửa số phần
tử của cây (do nếu dữ liệu cần tìm nhỏ hơn dữ liệu ở nút gốc thì duyệt qua trái còn
nếu lớn hơn thì duyệt qua phải) do đó ta có:
và T(n) = 0 khi n = 1
Giải phương trình trên ta được:
(1)
Phương trình ngừng khi:
T(n) = 0 khi n = 1
Thế vào (1) ta được:
Vậy giải thuật có độ phức tạp là