Đồ án Cấu trúc dữ liệu và Giải thuật

LỜI MỞ ĐẦU
Ngày nay với sự phát triển nhảy vọt của khoa học vông nghệ nói chung của
ngành tin học nói riêng,với những tính năng ưu việt, sự tiện dụng và ứng dụng rộng
rãi, tin học ngày nay là một phần không thể thiếu được của nhiều ngành trong công
cuộc xây dựng và phát triển xã hội. Hơn thế nữa nó còn đi sâu đời sống của con người.
Tin học đã thâm nhập khá mạnh mẽ vào Việt Nam, nhiều lĩnh vực hoạt động từ lĩnh
vực quản lý hành chính, quản lý kinh tế, tự động hóa công nghiệp …đến các lĩnh vực
giáo dục và đào tạo đều có thay đổi đáng kể nhờ ứng dụng tin học. Máy tính là công cụ
cần thiết đối với con người trong thời đại ngày nay.
Trong các môn học Toán – Tin, đặc biệt là ngành Công nghệ thông tin, thuật toán
đóng vai trò vô cùng quan trọng. Việc nắm vững thuật toán giúp ta tìm ra hướng giải
quyết vấn đề nhanh hơn, viết code mạch lạc hơn. Nắm vững thuật toán, cấu trúc dữ
liệu, ta sẽ ước tính được độ phức tạp của code, đánh giá code chạy nhanh hay chậm, có
bền vững hay không.
Đây là những kĩ năng vô cùng cần thiết để trở thành một kĩ sư giỏi. Vì vậy khoa
Tin rất tập trung trong việc giảng dạy môn Phân tích và Thiết kế giải thuật. Bên cạnh
đó, sinh viên em còn được thực hành và kiểm tra trình độ của mình qua việc làm Đồ án
Giải thuật & Lập trình với các đề tài cụ thể và thiết thực.
Mặc dù em đã rất cố gắng và nổ lực để làm đồ án này do kinh nghiệm còn hạn
chế và kiến thức em nắm chưa sâu nên em biết sẽ không tránh khỏi những thiếu sót.
Em rất mong nhận được sự thông cảm và đóng góp của các Thầy, Cô để lần sau làm
đồ án được tốt hơn.
Hoàn thành đồ án Giải thuật & Lập trình này là niềm vui của em, em rất là biết
ơn Thầy Hồ Ngọc Tú đã hướng dẫn chúng em tận tình trong suốt thời gian chúng em
làm đồ án. Một lần nữa nhóm chúng em xin gửi lời cám ơn chân thành nhất đến Thầy.

Trang 2



Giải thuâ ̣t chia để tri ̣(Devide and Conquer) ............................................. 7

TỔ CHỨC CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN ................................ 7
3.1.

Phát biểu bài toán ...................................................................................... 7

3.2.

Cấu trúc dữ liệu ......................................................................................... 8

3.3.

Thuật toán ................................................................................................. 8

3.3.1. Sắ p xế p cho ̣n (Selection Sort) ............................................................. 8
3.3.2. Sắ p xế p chèn (Insertion Sort) ............................................................ 11
3.3.3. Sắ p xế p nổ i bo ̣t (Bubble Sort) ........................................................... 14
3.3.4. Sắ p xế p trô ̣n (Merge Sort) ................................................................. 17
3.3.5. Sắ p xế p nhanh (Quick Sort) .............................................................. 21
4.

CHƯƠNG TRÌNH VÀ KẾT QUẢ ............................................................... 24
4.1.

Tổ chức chương trình .............................................................................. 24

4.2.

Ngôn ngữ cài đặt ..................................................................................... 27


Đồ án Cấu trúc dữ liệu và Giải thuật

1. GIỚI THIỆU ĐỀ TÀI
Hiê ̣n nay, có rấ t nhiều vấn đề phổ biến trong các lĩnh vực thực tiễn về khoa học
máy tính, ứng dụng cơ sở dữ liệu, mạng và trí tuệ nhân tạo. Một trong những vấn đề cơ
bản nhấ t đó là thuật toán sắp xếp, mô ̣t vấn đề đã thu hút rất nhiều nghiên cứu.
Quá triǹ h sắp xếp là quá trình bố trí lại các phầ n tử theo mô ̣t trâ ̣t tự nhấ t định để
cho viê ̣c xử lý trở nên dễ dàng và hiê ̣u quả hơn so với xử lý các phần tử ngẫu nhiên.
Sắp xếp là một trong những giải thuâ ̣t lập trình phổ biến nhất, ví dụ khi lấy cơ sở dữ
liệu ứng dụng, nếu chúng ta muốn quản lý thông tin để thuâ ̣n tiê ̣n cho viê ̣c tìm kiế m,
chúng ta phải giữ thông tin theo thứ tự hợp lý, ví dụ: thứ tự chữ cái theo tên, thứ tự
tăng dần hoă ̣c giảm dần theo mã ID, lương, ngày nhâ ̣n vào làm viê ̣c,...
Sự tăng trưởng thông tin mô ̣t cách nhanh chóng đã kéo theo sự phát triển của các
thuật toán sắp xếp. Các thuâ ̣t toán này đươ ̣c phát triể n nhằ m nâng cao hiê ̣u suấ t và
giảm thiể u đô ̣ phức ta ̣p. Dữ liê ̣u có thể xuấ t hiê ̣n dưới nhiề u dạng khác nhau và thường
phải được lưu trữ mô ̣t khố i lươ ̣ng đáng kể , nên viê ̣c xây dựng các thuâ ̣t toán sắ p xế p
cho phép tìm kiếm nhanh đem lại ý nghiã rấ t lớn. Hiê ̣n nay, có rấ t nhiề u thuâ ̣t toán sắ p
xế p được ra đời như sắp xếp chọn, sắ p xế p nổ i bọt, sắ p xế p chèn, sắ p xế p trô ̣n, sắ p xế p
nhanh,... mỗi thuâ ̣t toán đề u có một cơ chế khác nhau nhằ m làm tăng hiệu suất và hiệu
quả của các ứng dụng thực tế và giảm độ phức tạp thời gian của từng ứng dụng.
Khi so sánh giữa các thuật toán sắp xếp khác nhau, có ba yếu tố cầ n đươ ̣c xem
xét: độ phức tạp thời gian, sự ổn định và không gian bộ nhớ. Qua viê ̣c so sánh, chúng
ta có thể hiểu rõ hơn về ưu điể m, khuyế t điểm của các thuâ ̣t toán sắp xế p, từ đó vâ ̣n
du ̣ng đúng thuâ ̣t toán theo yêu cầ u của bài toán đă ̣t ra mô ̣t cách hiê ̣u quả và đó cũng là
mu ̣c đích của đề tài này.

2. CƠ SỞ LÝ THUYẾT
2.1. Thuâ ̣t toán
Thuật toán , còn gọi là giải thuật, là một tập hợp hữu hạn hay một dãy các quy tắc

nói “g(n) là O của f(n)” và viết là: g(n) = O(f(n)) nếu tồn tại các hằng số dương C và
n0 sao cho g(n) <= C * f(n) với mọi n >= n0.
Việc xác định độ phức tạp tính toán của giải thuật trong thực tế có thể tính bằng
một số quy tắc đơn giản sau:
-

Quy tắc bỏ hằng số:
T(n) = O(c.f(n)) = O(f(n)) với c là một hằng số dương
Quy tắc lấy max:
T(n) = O(f(n)+ g(n)) = O(max(f(n), g(n)))
Quy tắ c cô ̣ng:
O(f(n)+g(n))=max{O(f(n)),O(g(n))}
Quy tắ c nhân:
O(f(n).g(n))=O(f(n)).O(g(n))

2.3. Thuâ ̣t toán sắ p xế p
Sắp xếp là quá trình biế n đổ i mô ̣t danh sách các phầ n từ thành mô ̣t danh sách
thỏa mañ mô ̣t thứ tự xác đinh
̣ nào đó, nhằ m có lợi cho việc quản lý và đinh
̣ vi ̣ thông
tin. Sắ p xế p đóng vai trò vô cùng quan tro ̣ng tim
̀ kiế m dữ liê ̣u. Chẳ ng ha ̣n, khi đã có
một danh sách được sắ p xế p theo thứ tự tăng dầ n (hoă ̣c giảm dầ n), ta có thể sử du ̣ng
thuật toán tìm kiế m nhi ̣phân, hiê ̣u quả hơn nhiề u so với tìm kiế m tuầ n tự. Trên thực tế ,
nhiề u thuật toán đươ ̣c đưa ra dựa trên ý tưởng xử lý các đố i tươ ̣ng theo mô ̣t thứ tự xác
đinh
̣ nên sắ p xế p là mô ̣t giải thuâ ̣t rấ t quan trọng và cầ n thiế t.
Các thuâ ̣t toán sắ p xế p đươ ̣c chia làm 2 loa ̣i: internal sorting và external sorting.
Với internal sorting, toàn bộ dữ liệu cần sắp xếp được đưa vào bộ nhớ trong, do vậy
kích thước dữ liệu cần sắp xếp nhỏ và thời gian sắp xếp được thực hiện rất nhanh. Với

bài toán con nên là một phần của bài toán ban đầu. Nói chung, bước này sử
dụng phương pháp đệ qui để chia nhỏ các bài toán cho đến khi không thể chia
thêm nữa. Khi đó, các bài toán con được gọi là "atomic – nguyên tử", nhưng
chúng vẫn biểu diễn một phần nào đó của bài toán ban đầu.
Giải bài toán con:
Trong bước này, các bài toán con được giải.
Kế t hơ ̣p lời giải:
Sau khi các bài toán con đã được giải, trong bước này chúng ta sẽ kết hợp
chúng một cách đệ qui để tìm ra giải pháp cho bài toán ban đầu [3].

3. TỔ CHỨC CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
3.1. Phát biểu bài toán
Đầ u vào (Input): tệp chứa mảng các phần tử số nguyên
Phương pháp (Method): sắp xếp chọn, sắ p xế p chèn, sắp xế p nổ i bọt, sắ p xế p
trô ̣n, sắ p xế p nhanh
Đầu ra (Output): tê ̣p chứa mảng các phầ n tử số nguyên đã đươ ̣c sắ p xế p theo thứ
tự tăng dầ n

Trang 7


Đồ án Cấu trúc dữ liệu và Giải thuật
3.2. Cấu trúc dữ liệu
-

Sử du ̣ng mảng để triể n khai giải thuâ ̣t

-

int array[];

A[n-1];
 Bước 3: Hoán vị A[min] với A[i];
 Bước 4: i=i+1. Nếu i < n-1, quay lại bước 2; Ngược lại: kết thúc.

Trang 8


Đồ án Cấu trúc dữ liệu và Giải thuật

3.3.1.3 Minh ho ̣a thuâ ̣t toán
j = 19
i=0

15

22

A[min]
13

27

20

12

23

24



23

24

25

15

A[min] j = 39
i=2

10

22

13

27

j = 49
i=3

10

12

13

27


15

20

22

Tiếp tục thực hiện như vậy trong khi i < n-1.

Trang 9


Đồ án Cấu trúc dữ liệu và Giải thuật
3.3.1.4 . Sơ đồ khố i
Bắt đầu

Mảng A, n phần tử

i0

F

i++

i < n-1
?
T
min  i

J  i+1

Trường hơ ̣p trung bình: tương tự trường hơ ̣p xấ u nhấ t, đô ̣ phức ta ̣p là O(n2)
Trường hơ ̣p tố t nhấ t: đô ̣ phức ta ̣p là O(n2)

3.3.2. Sắp xế p chèn (Insertion Sort)
3.3.2.1 . Ý tưởng
Phương pháp sắp xếp chèn thực hiện bằng cách chèn phần tử đang xét vào vị trí
thích hợp trong mảng đã được sắp xếp phía trước nó.
Cụ thể, ban đầu, xem phần tử A[0] là mảng đã có thứ tự.
Sau đó chèn phần tử A[1] vào đúng vị trí trong mảng gồm A[0] trên sao cho
mảng A[0], A[1] được sắp xếp theo thứ tự.
Tiếp tục chèn phần tử A[2] vào đúng vị trí trong mảng gồm A[0], A[1] trên sao
cho mảng A[0], A[1], A[2] được sắp xếp theo thứ tự.
Tổng quát, ta thực hiện chèn phần tử A[i] vào mảng gồm A[0], A[1], …, A[i-1]
sao cho mảng A[0], A[1], …, A[i] (i = 1  n-1) được sắp xếp theo thứ tự.
Cuối cùng ta sẽ thu được mảng đã được sắp xếp theo thứ tự.
3.3.2.2 . Thuâ ̣t toán
Input: Mảng A[] gồm n phần tử
Output: Mảng A[] gồm n phần tử đã được sắp xếp
 Bước 1: i = 1;
 Bước 2: Gán key = A[i];
 Bước 3: Tìm vị trí thích hợp trong mảng A[0], …, A[i-1] để chèn A[i] vào;
 Bước 4: Chèn key vào vị trí vừa tìm được;
 Bước 5: i=i+1. Nếu i < n, quay lại bước 2; Ngược lại: kết thúc.

Trang 11


Đồ án Cấu trúc dữ liệu và Giải thuật
3.3.2.3 Minh ho ̣a thuâ ̣t toán



23

24

25

10

27

20

12

23

24

25

10

j=1
i=2

15

22



10

12

23

24

25

10

j=4
i=5

13

15

20

22

27

Tiếp tục thực hiện như vậy trong khi i < n.

Trang 12


Kết thúc

Trang 13


Đồ án Cấu trúc dữ liệu và Giải thuật
3.3.2.5 . Đô ̣ phức ta ̣p
Trường hơ ̣p xấ u nhấ t: với mỗi i thì số lần so sánh tối đa là i.
𝒏(𝒏−𝟏)
 Độ phức tạp thuật toán là: 𝐓(𝐧) = ∑𝒏−𝟏
= O(n2)
𝒊=𝟏 𝐢 =
-

𝟐

-

Trường hơ ̣p trung bình: tương tự trường hơ ̣p xấ u nhấ t, đô ̣ phức ta ̣p là O(n2)
Trường hơ ̣p tố t nhấ t: đô ̣ phức ta ̣p là O(n)

3.3.3. Sắp xế p nổ i bo ̣t (Bubble Sort)
3.3.3.1 . Ý tưởng
Phương pháp sắp xếp nổi bọt thực hiện đúng như tên gọi của nó bằng cách cho
“nổi bọt” những phần tử nhỏ hơn lên đầu mảng.
Cụ thể, duyệt từ cuối về đầu mảng, lần lượt xét 2 phần tử kề nhau, nếu phần tử
phía sau nhỏ hơn thì sẽ cho “nổi bọt lên”, đổi chỗ với phần tử kề trước nó. Kết thúc lần
xét duyệt đầu tiên, ta sẽ thu được A[0] là phần tử nhỏ nhất của mảng, loại ra khỏi
mảng đang xét.
Tiếp tục duyệt từ cuối về đầu mảng hiện hành, sau quá trình “nổi bọt” ta tiếp


27

10

15

22

13

12

20

10

27

15

22

13

12

10

20


15

10

22

13

12

20

27

10

15

22

13

12

20

27

j=8

10

15

12

22

13

20

27

10

12

15

22

13

20

27

Tiếp tục thực hiện như vậy trong khi i < n-1.



Trang 16


Đồ án Cấu trúc dữ liệu và Giải thuật
3.3.3.5 Độ phức ta ̣p
Trường hơ ̣p xấ u nhấ t: với mỗi i thì số lần so sánh tối đa là n – i - 1.
𝒏−𝟐
𝒏(𝒏−𝟏)
 Độ phức tạp là: 𝐓(𝐧) = ∑𝒊=𝟎 (𝐧 − 𝐢 − 𝟏) =
= O(n2)
-

𝟐

-

Trường hơ ̣p trung bình: tương tự trường hơ ̣p xấ u nhấ t, đô ̣ phức ta ̣p là O(n2)
Trường hơ ̣p tố t nhấ t: đô ̣ phức ta ̣p là O(n)

3.3.4. Sắp xế p trô ̣n (Merge Sort)
3.3.4.1 . Ý tưởng
Sắp xếp trộn là một thuật toán được thiết kế bằng kĩ thuật chia để trị. Để sắp
xếp mảng ban đầu A gồm n phần tử A[0], A[1], …, A[n-1], ta sẽ chia mảng cần xếp
thành 2 mảng con phân cách nhau bởi phần tử chính giữa mảng. Sau khi thu được 2
mảng con, ta sẽ tiến hành sắp xếp từng mảng con theo thứ tự đúng rồi ghép 2 mảng
con lại với nhau, tạo thành mảng A gồm n phần tử ban đầu. Trong quá trình sắp xếp
từng mảng con, ta lại tiến hành chia đôi, sắp xếp rồi ghép lại. Quá trình đó cứ lần lượt
được lặp lại cho đến mảng con nhỏ nhất chỉ còn 1 phần tử. Sau đó ta so sánh 2 mảng
con trong cùng mảng cơ sở (khi chia đôi 1 mảng lớn thành 2 mảng con, mảng lớn đó

-

Bước 5.2: Đưa phần tử nhỏ hơn vào mảng cơ sở, rồi loại phần tử đó
ra khỏi 2 mảng con đang xét;

-

Bước 5.3: Kiểm tra 1 trong 2 mảng con đã rỗng chưa? Nếu sai, quay
lại bước 5.1; ngược lại, chuyển đến bước 5.4;

-

Bước 5.4: Gán tất cả phần tử còn lại của mảng con còn lại vào mảng
cơ sở;

3.3.4.3 Minh ho ̣a thuâ ̣t toán

15

15

15

22

22

13

13


27

12

20

22

23

12

24

23

24

23

12

12

23

24

24


23

24

24

27

Trang 18


Đồ án Cấu trúc dữ liệu và Giải thuật
3.3.4.4 Sơ đồ khố i
Đầu tiên ta xây dựng sơ đồ khối cho công việc ghép 2 mảng con thành mảng cơ
sở: Merge (A, l, m, r)
Bắt đầu

Mảng cơ sở A, vị trí bắt đầu l, vị
trí kết thúc r, vị trí giữa m

n1  m-l+1
n2  r-m
Mảng L  Mảng con bắt đầu từ vị trí l, có n1 phần tử
Mảng R  Mảng con bắt đầu từ vị trí m+1, có n2 phần tử

i  0; j  0; k  l

i < n1 && j



Đồ án Cấu trúc dữ liệu và Giải thuật
Sơ đồ khố i hàm MergeSort(A, l, r):

Bắt đầu

Mảng cơ sở A, vị trí bắt đầu l, vị
trí kết thúc r

F
l
𝒏

Mà: T(1) = 1  𝒊 = 1  n = 2i  log2 n = log2 2i  log2 n = i
𝟐

Từ đó suy ra: T(n) = n.T(1) + n. log2 n = n + n. log2 n
 Đô ̣ phức ta ̣p thuâ ̣t toán là O(n.log2 n) cho cả 3 trường hơ ̣p tố t nhấ t,
trung bình và xấ u nhấ t.
3.3.5. Sắp xế p nhanh (Quick Sort)
3.3.5.1 . Ý tưởng
Cũng giống như sắp xếp trộn, sắp xếp nhanh là 1 phương pháp được thiết kế
theo kĩ thuật chia để trị. Mảng trong phương pháp sắp xếp nhanh được chia thành 3
phần:
- Phần 1: Mảng con gồm tất cả các phần tử nhỏ hơn trục.
- Phần 2: Trục – 1 phần tử trong mảng được lựa chọn để làm cơ sở phân chia
mảng
- Phần 3: Mảng con gồm tất cả các phần tử lớn hơn hoặc bằng trục.
Phần trục trong sắp xếp nhanh có nhiều cách khác nhau để lựa chọn: có thể là
phần tử đầu mảng, phần tử cuối mảng, phần tử ở giữa mảng hoặc 1 phần tử bất kì
trong mảng. Để dễ hình dung, tính toán và quản lý, thông thường phần trục đó sẽ được
chọn từ phần tử ở chính giữa mảng.
Cụ thể, phương pháp sắp xếp nhanh sẽ tiến hành như sau: Mảng A ban đầu gồm
n phần tử sẽ được chia thành 2 mảng con 2 bên trục sao cho mảng các phần tử nhỏ hơn
trục nằm phía trước trục và các phần tử lớn hơn trục nằm phía sau trục. Các mảng con
đó lại tiếp tục được phân hoạch thành các mảng con và trục nhỏ hơn đáp ứng điều kiện
trên cho đến khi mảng con thu được chỉ gồm 1 phần tử.
Phần quan trọng nhất trong phương pháp này là chia mảng (phân hoạch). Ta sẽ
lần lượt tìm các cặp phần tử lớn hơn trục nằm bên trái trục và nhỏ hơn trục nằm bên
phải trục để đổi chỗ cho nhau.



20

13

15

12

13

20

15

13

27

27

12

22

22

23

24

Mảng cơ sở A, vị trí bắt đầu l, vị
trí kết thúc r

F

l
T(n) = n + T(n – 1) = 2n – 1 + T(n – 2) = 3n – 3 + T(n – 3) = 4n – 6 + T(n – 4)
𝒊−𝟏

= i.n + ∑𝒊=𝟎(−𝐢) + T(n – i)
𝒏

Mà T(1) = 1  T(n) = (n + 1).n + ∑𝒏=−𝟏(−𝐧 − 𝟏) + T(1)
 Đô ̣ phức ta ̣p là O(n2)
- Trưởng hơ ̣p tố t nhấ t: mỗi lầ n phân hoa ̣ch, dãy đươ ̣c chia thành 2 phầ n đề u
nhau, tương tự merge sort, sẽ cầ n log2 n lầ n phân hoa ̣ch sẽ sắ p xế p xong
 Đô ̣ phức ta ̣p là O(n.log2 n)
- Trường hơ ̣p trung bình: tương tự trường hơ ̣p tố t nhấ t
 Đô ̣ phức ta ̣p là O(n.log2 n)

4.

CHƯƠNG TRÌNH VÀ KẾT QUẢ

4.1. Tổ chức chương trình

Hàm swap

Trang 24


Đồ án Cấu trúc dữ liệu và Giải thuật

Sắ p xế p cho ̣n
Sắ p xế p chèn