BỘ MÔN KHOA HỌC MÁY TÍNH
…………………………………………………………
Đồ án Nhập Môn Phân Tích Độ Phức Tạp
Thuật Toán
Đề tài: Đánh giá các thuật toán Sort
Giảng viên hướng dẫn lý thuyết
TS. Trần Đan Thư
Giảng viên hướng dẫn thực hành
Dương Chí Nhân
Nhóm thực hiện
0712002 – Nguyễn Thanh Đồng
0712228 – Trần Trung Kiên
0712394 – Bành Trí Thành
0712474 – Nguyễn Trọng Nhật Trung
0712476 – Phan Thanh Trí
TP.HCM, tháng 05 năm 2010
MỞ ĐẦU
Đề tài nhóm chúng tôi là đánh giá độ phức tạp của các giải thuật sắp xếp. Nói đến
các giải thuật sắp xếp thì có lẽ đây là một chủ đề đã quá quen thuộc và kinh điển.
Tuy nhiên, vì chúng ta xem nó quá quen thuộc nên chúng ta thường hay quên nó
đi. Mục tiêu của đề tài này là để chúng ta cùng nhau nắm lại tư tưởng của các thuật
toán sắp xếp, độ phức tạp về mặt lý thuyết, và hơn nữa, bằng thực nghiệm đánh
giá, kiểm chứng lại các độ phức tạp này.
Nội dung của phần báo cáo được chia làm 2 phần lớn:
 Nền tảng lý thuyết: Giới thiệu tổng quan về tư tưởng, độ phức tạp của các
thuật toán sắp xếp.
 Thực nghiệm: Nêu lên cách tiến hành thực nghiệm, kết quả và nhận xét.
Các thuật toán Sort
Page
2
MỤC LỤC

Các thuật toán Sort
Page
3
1.7.2 Ví dụ minh họa 18
1.7.3 Độ phức tạp 20
1.8 MERGE SORT 21
1.8.1 Ý tưởng thuật toán 21
1.8.2 Ví dụ minh họa 21
1.8.3 Độ phức tạp 22
1.9 BINARY TREE 23
1.9.1 Ý tưởng thuật toán 23
1.9.2 Ví dụ minh họa 23
1.9.3 Độ phức tạp 26
1.10 QUICK SORT 27
1.10.1 Ý tưởng thuật toán 27
1.10.2 Ví dụ minh họa 27
1.10.3 Độ phức tạp 28
1.11 SHELL SORT 29
1.11.1 Ý tưởng thuật toán 29
1.11.2 Ví dụ minh họa 29
1.11.3 Độ phức tạp 30
Chương 2 THỰC NGHIỆM 31
2.1 PHÂN TÍCH VÀ THIẾT KẾ CHƯƠNG TRÌNH THỰC NGHIỆM 31
2.2 KẾT QUẢ THỰC NGHIỆM 31
Chương 3 ĐÁNH GIÁ ĐỀ TÀI 31
TÀI LIỆU THAM KHẢO 31
Chương 1 NỀN TẢNG LÝ THUYẾT
Các thuật toán Sort
Page
4

D Dãy được sắp xếp
tăng
Mỗi lần duyệt, ta luôn phải hoán vị 1 lần (1 hoán vị tương đương với 3 phép gán),
nghĩa là thuật toán sẽ tốn 3(n-1) + 3(n-2) + … + 3 = 3n(n-1)/2 = O(n
2
) phép gán.
Tổng kết lại, ta luôn có độ phức tạp của thuật toán Selection Sort thuộc O(n
2
)
trong mọi trường hợp.
1.2 INTERCHANGE SORT
1.2.1 Ý tưởng thuật toán
 Ý tưởng chính của thuật toán này là ta tìm các cặp nghịch thế và triệt tiêu
chúng. Ta xuất phát từ phần tử đầu tiên của dãy, tìm tất các các cặp nghịch thế
chứa phần tử này, triệt tiêu chúng bằng các hoán vị phần tử này với phần tử
tương ứng trong cặp nghịch thế. Ta dễ nhận thấy sau lần duyệt đầu tiên, phần
tử đầu tiên chính là phần tử nhỏ nhất của dãy. Ta tiếp tục xử lý với phần tử thứ
hai, ta có được phần tử thứ hai chính là phần tử nhỏ thứ hai của dãy. Cứ như
vậy, sau khi xử lý với phần tử thứ N -1 của dãy, ta được một dãy sắp tăng.
 Các bước tiến hành như sau:
o Bước 1: Khởi động i = 1
o Bước 2: j = i+1
o Bước 3: Trong khi j <= N thực hiện:
 Nếu a[i]>a[j]: Hoán vị a[i] và a[j]
 j = j+1
o Bước 4: i = i+1
 Nếu i <= N-1: quay trở lại bước 2
 Ngược lại: STOP!
Các thuật toán Sort
Page

11
D Dãy được sắp xếp
tăng
1.3 BUBBLE SORT
1.3.1 Ý tưởng thuật toán
 Xét từ đáy và phần tử nhẹ nổi lên trên.
 Các bước thực hiện:
o Bước 1: Khởi động i = 1
o Bước 2: j = N //Duyệt từ cuối dãy về vị trí i
Trong khi j>i thực hiện:
 Nếu a[j]<a[j-1]: hoán vị a[j], a[j-1]
 j = j - 1
o Bước 3: i = i + 1
 Nếu i <= N-1: quay trở lại bước 2.
 Ngược lại: STOP!
1.3.2 Ví dụ minh họa
Cho dãy số như trên thuật toán SELECTION SORT
1 2 4 12 5 8 6 5
Hình minh họa quá trình sắp xếp của thuật toán:
Các thuật toán Sort
Page
12
1.3.3 Độ phức tạp
 Thấy ngay số phép so sánh là luôn không đổi, tức không phụ thuộc vào tình
trạng ban đầu của dãy. Với i bất kỳ, ta luôn phải so sánh V[j] với V[j-1], mà j
chạy từ n đến i+1, tức ta tốn n-i phép so sánh. Thêm nữa, i chạy từ 1 đến n-1.
Vậy ta tính được số phép so sánh tổng cộng: ∑(n-i) với i chạy từ 1 đến n-1 =
(n-1) + (n-2) + … + 1 = n(n-1)/2.
 Số phép hoán vị (tương đương 3 phép gán) lại phụ thuộc vào tình trạng ban đầu
của dãy. Cụ thể như sau:

).
1.5 INSERTION SORT
1.5.1 Ý tưởng thuật toán
 Giả sử ta có dãy a
1
, a
2
, …, an trong đó i phần tử đầu tiên a
1
, a
2
, …, a
i
đã có thứ
tự. Ý tưởng của thuật toán là tìm vị trị thích hợp và chèn phần tử a
i+1
vào dãy đã
có thứ tự trên để có được một dãy mới có thứ tự. Cứ thế, làm đến cuối dãy ta sẽ
được một dãy có thứ tự.
Các thuật toán Sort
Page
14
 Với dãy ban đầu a
1
, a
2
, …, a
n
ta có thể coi đoạn chỉ có một phần tử a
1

n-1
ta sẽ được dãy a
1
a
2
…a
n
có
thứ tự.
 Các bước thực hiện:
o Bước 1: Khởi động với i = 2 //Đoạn a[1] đã được sắp
o Bước 2: x = a[i]. Tìm vị trí thích hợp pos trong đoạn a[1]…a[i-1] để
chèn x vào
o Bước 3: Dời đoạn a[pos]…a[i-1] sang phải để có chỗ đưa x vào.
o Bước 4: a[pos] = x
o Bước 5: i = i + 1
 Nếu i<=n: quay lại bước 2.
 Ngược lại: STOP!
1.5.2 Ví dụ minh họa
Cho dãy số a:
12 2 8 5 1 6 4 15
Các thuật toán Sort
Page
15
1.5.3 Độ phức tạp
 Ta thấy các phép so sánh xảy ra trong vòng lặp nhằm tìm vị trí thích hợp pos để
chèn x. Mỗi lần so sánh mà thấy vị trí đang xét không thích hợp, ta dời phần tử
a[pos] sang phải.
 Ta cũng thấy số phép gán và số phép so sánh của thuật toán phụ thuộc vào tình
trạng của dãy ban đầu. Do đó ta chỉ có thể ước lượng như sau:

giảm đi chi phí so sánh trong lúc tìm kiếm, còn chi phí cho việc chèn vẫn
không thay đổi (vẫn phải dịch đúng k phần tử như Insertion Sort để chèn) nên
chi phí phép gán không có cải tiến.
 Tìm kiếm tốt nhất khi vừa tìm phần tử lần đầu là ra ngay, phần tử đó sẽ nằm ở
vị trí middle của dãy đã có thứ tự, nhưng chi phí chèn lúc này sẽ là n/2, với chi
phí này còn cao so với trường hợp tốt nhất.
 Thuật toán chỉ tốt nhất khi chi phí chèn là 1, ứng với phần tử tìm phải nằm ở
cuối dãy có thứ tự, chi phí tìm lúc này là log
2
n, mà ta phải làm n lần cho n phần
tử nên là O(nlogn)
Các thuật toán Sort
Page
17
 Thuật toán xấu nhất khi phần tử tìm được nằm ở đầu dãy, chi phí chèn lúc này
là n (tìm kiếm là log
2
n, nhưng chi phí chèn mạnh hơn), mà có n phần tử nên là
O(n
2
).
 Ta thấy dường như độ phức tạp thuật toán phụ thuộc mạnh vào chi phí chèn
hơn là tìm kiếm, cho nên cách tốt hơn ta sẽ cài đặt bằng danh sách liên kết để
việc chèn được tốt hơn.
 Độ phức tạp thuật toán như sau:
o Trường hợp tốt nhất: O(nlogn)
o Trường hợp xấu nhất O(n
2
)
1.7 HEAP SORT

của heap là phần tử nhỏ nhất).
1.7.2 Ví dụ minh họa
Cho dãy số a:
12 2 8 5 1 6 4 15
Giai đoạn 1: hiệu chỉnh dãy ban đầu thành heap
Các thuật toán Sort
Page
18
Giai đoạn 2: Sắp xếp dãy số dựa trên heap:
Các thuật toán Sort
Page
19
Thực hiện tương tự cho r = 5, 4, 3, 2 ta được:
1.7.3 Độ phức tạp
 Ta thấy được chi phí cho xây dựng heap khi thêm vào heap một phần tử mới là
log
2
n (chính là chiều cao heap cho mỗi lần làm chìm phần tử xuống vị trí thích
hợp), mặt khác từ bước 2 đến bước 3 ứng với mỗi phần tử ta sẽ xây dựng lại
heap một lần, mà ta có n phần tử. Vậy ta có thể ước tính chi phí cho sắp xếp
HeapSort là O(nlogn) cho mọi trường hợp. (Từ thực nghiệm cài đặt cho kết quả
là ~ 4log
2
n)
Các thuật toán Sort
Page
20
1.8 MERGE SORT
1.8.1 Ý tưởng thuật toán
 Cho dãy ban đầu a

, …, a
k
, a
2k+1
, …, a
3k
, …
c = a
k+1
, …, a
2k
, a
3k+1
, …, a
4k
o Bước 3: Từ 2 dãy phụ b, c, ta trộn từng cặp dãy con và đưa vào dãy a.
o Bước 4: k = k*2
 Nếu k<n: quay lại bước 2.
 Ngược lại: STOP!
1.8.2 Ví dụ minh họa
Cho dãy số a:
12 2 8 5 1 6 4 15
Các thuật toán Sort
Page
21
k = 1:
k = 2:
k = 4:
1.8.3 Độ phức tạp
 Ta thấy ngay số lần lặp của bước 2(phân phối) và bước 3(trộn) bằng log

phân tìm kiếm. Các nút có thể được duyệt theo thứ tự bằng cách gọi đệ quy cây
con bên trái, in nút đang duyệt, rồi duyệt đệ qui cây con bên phải, tiếp tục làm
như vây với mỗi nút của cây trong quá trình đệ qui (theo thứ tự LNR).
if node == NULL
return
traverse_binary_tree(node->leftChild, callback);
callback(node->value);
traverse_binary_tree(node->rightChild, callback);
1.9.2 Ví dụ minh họa
Duyệt cây theo thứ tự LNR : Cho một cây như sau :
Các thuật toán Sort
Page
23
Thứ tự của phép duyệt LNR : CBEDFAKHL
Ví dụ cụ thể :
Cho dãy sau : 44 55 12 42 94 18 6 67
Khi insert vào cây ta sẽ được như sau :
+ Bước 1 :
+ Bước 2 :
+ Bước 3 :
Các thuật toán Sort
Page
24
+ Bước 4 :
+ Bước 5 :
+ Bước 6 :
+ Bước 7 :
Các thuật toán Sort
Page
25