TRƯỜNG ĐẠI HỌC ĐỒNG THÁP
KHOA KỸ THUẬT - CÔNG NGHỆ

0018413051 - DƯƠNG TẤN THÀNH

ĐỒ ÁN MÔN HỌC 1

CÀI ĐẶT BỐN GIẢI THUẬT SẮP XẾP VÀ ĐÁNH GIÁ HIỆU NĂ
Mã số quyển báo cáo:

NGÀNH: KHOA HỌC MÁY TÍNH
LỚP: DHCNTT18


TRƯỜNG ĐẠI HỌC ĐỒNG THÁP
KHOA KỸ THUẬT - CÔNG NGHỆ

0018413051 - DƯƠNG TẤN THÀNH

ĐỒ ÁN MÔN HỌC 1

CÀI ĐẶT BỐN GIẢI THUẬT SẮP XẾP VÀ ĐÁNH GIÁ HIỆU NĂ
Mã số quyển báo cáo:

NGÀNH: KHOA HỌC MÁY TÍNH
LỚP: DHCNTT18

Giảng viên hướng dẫn: Thạc sĩ Nguyễn Thị Mỹ Dung

Đồng Tháp, tháng …
năm ….

LỜI DẪN
Trong hầu hết các hệ lưu trữ, quản lý dữ liệu hiện nay, thao tác tìm kiếm và sắp xếp
thường được sử dụng rất nhiều để khai thác thông tin một cách nhanh chống và hiệu quả.
(Ví dụ: Quản lý điểm học sinh, tra cứu sách thư viện…) và muốn quá trình tìm kiếm được
diễn ra nhanh chống thì dữ liệu cần phải được sắp xếp gọn gàng theo một trật tự nhất
định. Để làm được việc đó, ta cần phải cân nhắc sử dụng đến các thuật toán sắp xếp để
quá trình đó được thực hiện hiệu quả và nhanh chống nhất.
Hiện nay, đã có nhiều giải thuật tìm kiếm và sắp xếp được xây dựng, mức độ hiệu quả
của từng giải thuật còn phụ thuộc và tính chất của cấu trúc dữ liệu cụ thể mà nó tác động
đến. Cho nên, ta nên lựa chọn các phương pháp sắp xếp sao cho phù hợp. Trong khoa học
máy tính và trong toán học, một thuật toán sắp xếp là một thuật toán sắp xếp các phần tử
cần sắp xếp là các số. Hầu hết các bài toán đều có nhiều cách khác nhau để giải quyết
chúng.
Nội dung được trình bài trong đồ án này là những thuật toán sắp xếp thông dụng nhất
mức độ phức tạp ở mức tương đối và dễ dàng cài đặt. Đó là các thuật toán sắp xếp như:
Thuật toán sắp xếp nổi bọt (Bubble Sort), thuật toán đổi chổ trực tiếp (Interchange Sort),
thuật toán chọn trực tiếp (Selection Sort), thuật toán chèn trực tiếp (Insertion Sort). Ngoài
ra, còn trên dưới hơn một chục thuật toán khác nữa, nhưng trong chủ đề này chỉ tìm hiểu,
cài đặt và đánh giá hiệu năng bốn thuật toán trên.


DANH MỤC HÌNH ẢNH

DANH MỤC BẢNG

MỤC LỤC



PHẦN I: MỞ ĐẦU
---oOo---

1. Đặt vấn đề
Một trong những vấn đề cơ bản của việc xây dựng cơ sở dữ liệu là sắp xếp một tập
hợp các phần tử theo một thứ tự nào đó. Đây là một công việc quan trọng vì dữ liệu trong
hệ thống thường không được sắp xếp theo một trật tự nhất định, gây ra vấn đề khó khăn
khi ta cần truy cập vào dữ liệu nào đó trong hệ thống. Nhất là trong việc lưu trữ dữ liệu
lớn (Big data) thì vấn đề tốc độ truy cập dữ liệu luôn được đặt lên hàng đầu.
Và giải pháp là ta sẽ ứng dụng các thuật toán sắp xếp một cách hiệu quả nhất. Có khá
nhiều thuật toán sắp xếp, mỗi một thuật toán đều có ưu và nhược điểm nhất định, việc
quan trọng là ta phải hiểu biết chuyên sâu từng thuật toán và biết cách áp dụng vào thực tế
khi xây dựng bất kì một hệ quản trị cơ sở dữ liệu nào.
Qua đó, em đã chọn đề tài : Cài đặt bốn giải thuật sắp xếp và đánh giá hiệu năng để
tìm hiểu rõ hơn về những thuật toán sắp xếp như thuật toán sắp xếp nổi bọt (Bubble Sort),
thuật toán đổi chổ trực tiếp (Interchange Sort), thuật toán chọn trực tiếp (Selection Sort),
thuật toán chèn trực tiếp (Insertion Sort).

2. Mục tiêu
Tìm hiểu, cài đặt và đánh giá hiệu năng bốn thuật toán sắp xếp: Thuật toán sắp xếp
nổi bọt (Bubble Sort), thuật toán đổi chổ trực tiếp (Interchange Sort), thuật toán chọn trực
tiếp (Selection Sort), thuật toán chèn trực tiếp (Insertion Sort) trên ngôn ngữ lập trình C++
với trình biên dịch Visual Studio 2019. Nhằm thực hiện việc sắp xếp các số nguyên hoặc
các số thực theo thứ tự tăng dần hoặc giảm dần và xuất ra và đồng thời so sánh thời gian
thực hiện của từng thuật toán, có thể nhập và xuất ra file để lưu lại kết quả thực hiện. Áp
dụng linh hoạt các kiểu lập trình như lập trình hướng cấu trúc và lập trình hướng đối
tượng.

3. Phạm vi nghiên cứu
Tìm hiểu và vận dụng xây dựng chương trình dựa trên các lý thuyết cơ bản về các

thuật toán sắp xếp như: thuật toán sắp xếp nổi bọt (Bubble Sort), thuật toán đổi chổ trực
tiếp (Interchange Sort), thuật toán chọn trực tiếp (Selection Sort), thuật toán chèn trực tiếp
(Insertion Sort).
5


4. Phương pháp nghiên cứu
+ Nghiên cứu tài liệu
+ Phân tích giải thuật
+ Tìm hiểu giải thuật
+ Phân tích độ phức tạp của thuật toán
+ Nghiên cứu thực nghiệm
+ Tổng hợp tài liệu

5. Kế hoạch thực hiện đề tài
Bảng 1. Kế hoạch thực hiện đề tài
Thời gian
(từ ngày …
Đến ngày …)

Công việc thực
hiện
Nhận đề tài

Người thực hiện

Dương Tấn Thành

Liên hệ giảng
Dương Tấn Thành

viên hướng dẫn
Tìm hiểu và
sưu tập tài liệu

Dương Tấn Thành

Tiến hành viết
chương trình

Dương Tấn Thành

Hoàn thành
chương trình

Dương Tấn Thành

Hoàn thành
viết báo cáo

Dương Tấn Thành

6

Đánh giá
công việc

Ghi chú


PHẦN II: NỘI DUNG

---oOo--CHƯƠNG 1. CƠ SỞ LÝ THUYẾT
1 Một số lý thuyết ứng dụng trong việc xây dựng demo
a) Giới thiệu thuật toán sắp xếp
Sắp xếp là một quá trình biến đổi một danh sách các đối tượng thành một danh sách
thoải mãn một thứ tự xác định nào đó. Sắp xếp đóng vai trò quan trọng trong tìm kiếm dữ
liệu. Chẵng hạn, nếu 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ử dụng kỹ thuật tìm kiếm nhị phân hiệu quả hơn nhiều tìm kiếm tuần tự… Trong
thiết kế thuật toán, ta cũng thường xuyên cần đến sắp xếp, nhiều thuật toán được thiết kế
dựa trên ý tưởng xử lý các đối tượng theo một trật tự xác định.
Các thuật toán sắp xếp được chia thành hai loại: sắp xếp trong và sắp xếp ngoài. Sắp
xếp trong được thực hiện khi mà các đối tượng cần sắp xếp được lưu ở bộ nhớ trong của
máy tính dưới dạng mảng, do đó sắp xếp trong còn được gọi là sắp xếp mảng. Khi các đối
tượng cần sắp xếp quá lớn ta cần lưu ở bộ nhớ dưới dạng file, ta cần sử dụng các phương
pháp sắp xếp ngoài, hay còn gọi là sắp xếp file. Trong chương trình này ta sẽ trình bày các
thuật toán sắp xếp đơn giản, các thuật toán này đòi hỏi thời gian O (n2) để sắp xếp mảng
n đối tượng.
Mảng cần được sắp xếp có thể là mảng số nguyên, mảng số thực, hoặc mảng các xâu
ký tự. Trong trường hợp tổng quát, các đối tượng cần được sắp xếp có chứa một số thành
phần dữ liệu nào đó. Thành phần dữ liệu đó còn được gọi là các khóa sắp xếp. Chẳng hạn,
ta có một mảng các đối tượng sinh viên, mỗi sinh viên gồm các thành phần dữ liệu: tên,
tuổi, chiều cao và ta muốn sắp xếp cho các sinh viên theo thứ tự chiều cao tăng. Khi đó,
chiều cao là khóa sắp xếp.
Từ đây về sau, ta giả thuyết rằng, mảng cần được sắp xếp là mảng các dữ liệu người
dùng tự định nghĩa có tên KieuThuatToan với cấu trúc như sau:
typedef struct {
float ThoiGianThucThi;
float Temp;
7



float TBC;
}KieuThuatToan;

b) Dev C++
Dev C++ là một chương trình phát triển thích hợp tự do (IDE) được phân phối dưới
hình thức giấy phép công cộng GNU hỗ trợ việc lập trình bằng c++. Nó cũng nằm trong
bộ trình dịch mã nguồn mở MinGW. Chương trình IDE này được viết bằng ngôn ngữ
Delphi.
Dự án phát triển Dev C++ được lưu trữ trên SourceForge. Dev C++ nguyên bản đầu
tiên phát triển bởi một lập trình viên có tên Colin Laplace và chỉ chạy trên hệ điều hành
Windows.
Bloodshed Dev C++ là một môi trường phát triển tích hợp IDE có hỗ trợ đầy đủ tính năng
cho ngôn ngữ lập trình C++. Nó sử dụng trình MinGW của GCC (Bộ trình dịch GNU)
làm trình biên dịch. Dev C++ cũng có thể được dùng kết hợp với Cygwin hay bất kỳ trình
dịch nền nảng GCC nào khác.
Chương trình cho người dùng có cảm nhận hơi giống với hình thức của chương trình
Microsoft Visual Studio vốn được sử dụng rộng rãi hơn. Dev có một đặc điểm phụ đó là
sử dụng DevPaks, là một phần gồm các gói mở rộng so với môi trường tiêu chuẩn, bao
gồm các thư viện, mẫu và các tiện ích chưa được thêm vào. DevPaks thường có, nhưng
không nhất định, tiện ích GUI (giao diện người dùng đồ họa), bao gồm các công cụ phổ
biến như GTK+, wxWidgets và FLTK. Có những DevPaks có chứa các thư viện với thậm
chí nhiều hàm chức năng cao hơn.
Dev C++ nói chung là một chương trình chỉ chạy trên windows. Tuy nhiên, cũng có
một phiên bản cho Linux, nhưng vẫn trong giai đoạn alpha và chưa được cập nhật trong
hơn 6 năm qua.

8


Hình 1. Giao diện Dev C++


Hướng dẫn sử dụng Dev C++
Bước 1: Downloand phiên bản mới nhất của Bloodshed Dev C++ tại đường dẫn
/>
9


Hình 2. Đường dẫn tải Dev C++
Bước 2: Sau khi cài đặt ứng dụng, khởi động phần mềm lên bằng cách click chuột vào
biểu tượng icon của Bloodshed Dev C++ ngoài Desktop (Khi cài đặt chọn Desktop).
Bước 3: Để tạo một file mới bạn nhấn Ctrl + N hoặc File / New / Source File

Hình 3. Tạo File mới
Bước 5: Để tùy chỉnh trình soạn thảo vào Tools --> Editor Options...

Hình 4. Tùy chọn
10


Bước 6: Thực hiện viết đoạn code vào trình soạn thảo Bloodshed Dev C++

Hình 5. Viết Code vào trình soạn thảo
Bước 7: Để biên dịch nhấn F9, chương trình sẽ biên dịch nhanh chóng, nếu có lỗi sẽ được
hiển thị ở phía dưới cho bạn biết và sửa.

11


Hình 6. Biên dịch chương trình


Bước 8: Để thực thi, bạn nhấn F10. Khi đó xuất hiện cửa sổ chạy thực hiện tính toán trên
đoạn code bạn đã viết.

12


CHƯƠNG 2. XÂY DỰNG CHƯƠNG TRÌNH

1 Tổng quan về thuật toán
Một trong những vấn đề nền tảng của khoa học máy tính là sắp xếp một tập các phần
tử cho trước theo thứ tự nào đó. Có rất nhiều các giải pháp cho vấn đề này, được biết đến
như là các thuật toán sắp xếp. Bên cạnh các thuật toán sắp xếp đơn giản và rõ ràng thuật
toán sắp xếp nổi bọt (bubble sort). Một số khác, như phương pháp sắp xếp nhanh (quick
sort) thù lại rất phức tạp nhưng đổi lại có kết quả thực thi nhanh hơn một cách đáng kể.
Những thuật toán sắp xếp quen thuộc này có thể được chia thành hai nhóm dựa theo
độ phức tạp của chúng. Độ phức tạp của thuật toán (Alorithmic complexity) là một chủ đề
khá rắc rối đòi hỏi sự tưởng tượng mà sẽ tốn thời gian để giải thích, nhưng ở đây có thể
hiểu thông qua mối tương quan trực tiếp giữa độ phức tạp của thuật toán và hiệu quả của
nó. Độ phức tạp của thuật toán thường được ký hiệu bởi một hàm O, trong đó O biểu diễn
độ phức tạp của thuật toán đi kèm với một giá trị n biểu diễn kích thước của số lần chạy
tối đa mà thuật toán đó dựa vào để xử lý trên dữ liệu.
Ví dụ, O(n) có nghĩa là thuật toán có độ phức tạp tuyến tính. Cụ thể hơn, nó sẽ mất
thời gian gấp 10 lần cho việc xử lý trên tập dữ liệu có 100 phần tử so với tập chỉ có 10
phần tử (10 * 10 = 100). Nếu độ phức tạp là O(n2), thì nó sẽ phải tiêu tốn thời gian gấp
100 lần để xử lý trên tập 100 phần tử so với tập dữ liệu chỉ gồm 10 phần tử.
Bên cạnh độ phức tạp của thuật toán, tốc độ của các thuật toán sắp xếp có thể được so
sánh dựa vào kinh nghiệm có được từ việc thử trên các tập dữ liệu. Vì tốc độ sắp xếp có
thể thay đổi rất nhiều tùy theo đặc điểm của dữ liệu, nên để các kết quả thống kê chính
xác dựa trên kinh nghiệm đòi hỏi việc chạy các thuật toán nhiều lần trên các dữ liệu khác
nhau và tính trung bình. Thông thường tập dữ liệu kiểm tra được tạo ngẫu nhiên.

Trong các biểu đồ thể hiện mức độ hiệu quả của thuật toán dưới đây, đường thấp nhất
là “tốt nhất”. Ghi nhớ rằng tốt nhất ở đây là một khái niệm không tuyệt đối vì nó còn tùy
thuộc vào trường hợp sử dụng của bạn – nếu nhìn biểu đồ bạn sẽ thấy quick sort có lẽ là
thuật toán nhanh nhất, nhưng nếu sử dụng nó để sắp xếp các phần tử nhỏ lẻ khoảng 20 –
30 thì thật sự không hợp lý bởi độ phức tạp của nó, trong khi ta có thể sử dụng các thuật
toán đơn giản hơn và hiệu quả là như nhau.

13


Hình 7. Đồ thị so sánh tốc độ xử lý của các thuật toán sắp xếp đơn
Đồ thị thị trên đã thể hiện khá rõ, Bubble sort là giải pháp cực kì không hiệu quả, và
shell sort là sự cải tiến tạo ra cuộc bứt phá hết sức ngoạn mục. Chú ý rằng vào đường
ngang đầu tiên của khu vực đồ thị thể hiện thời gian 100 giây- bạn sẽ thấy rằng không có
thuật toán nào trong số này mà bạn muốn sử dụng cho tập dữ liệu lớn của một ứng dụng
tương tác. Ngay cả khi dùng shell sort, người sử dụng cũng có nguy cơ ngồi bấm móng
tay nếu bạn cố gắng sắp xếp nhiều hơn 10,000 phần tử.
Nhìn từ phương diện tươi sáng hơn, tất cả những thuật toán thuộc nhóm O(n2) đều
đơn giản một cách không ngờ (có thể shell sort là một ngoại lệ hơi phức tạp hơn). Với
những chương trình dùng kiểm tra nhanh, những mẩu thử nghiệm gấp, hay các phần mềm
dành cho người sử dụng nội bộ, chúng không phải là những lựa chọn tồi nếu bạn không
đặt quá nặng về hiệu năng.

14


Hình 8. Đồ thị so sánh tốc độ xử lý của các thuật toán sắp xếp phức tạp

Trong trường hợp tốc độ là ưu tiên hàng đầu, những giải thuật thuộc nhóm O(n log n)
nên được sử dụng. Chú ý rằng thời gian trong đồ thị ngay trên đây được đo theo từng

phần 10 của giây thay vì từng trăm giây như đồ thị của nhóm O(n2).
Tuy nhiên mọi thứ thì không thật sự dễ dàng với các ứng dụng thực tiễn, bạn phải
đứng trước sự lựa chọn cân bằng (trade-offs) giữa các yếu tố. Những thuật toán thuộc
nhóm O(n log n) thì rất nhanh, nhưng tốc độ đó có được do phải trả giá cho sự phức tạp
trong triển khai. Trong trường hợp đệ quy, các cấu trúc dữ liệu nâng cao, mảng đa chiều việc sử dụng những thuật toán này sẽ tạo ra nhiều vấn đề phát sinh rất khó chịu.

15


1 Các giải thuật
a Giải thuật sắp xếp nổi bọt Bubble Sort
Sắp xếp nổi bọt (bubble sort): là một thuật toán sắp xếp đơn giản, với thao tác cơ bản
là so sánh hai phần tử kề nhau, nếu chúng chưa đứng đúng thứ tự thì đổi chỗ (swap). Có
thể tiến hành từ trên xuống (bên trái sang) hoặc từ dưới lên (bên phải sang). Nó còn có tên
là sắp xếp bằng so sánh trực tiếp. Nó sử dụng phép so sánh các phần tử nên là một giải
thuật sắp xếp kiểu so sánh.
Đánh giá:
+ Số phép so sánh: O(n2)
+ Số lần hoán vị tối đa: O(n2)
+ Độ phức tạp: O(n2)
Ngôn ngữ mã giả:
Bước 1: xét các phần tử a[j] (j từ n-1 đến 1), nếu khóa của a[j] nhỏ hơn khóa của a[j-1] thì
hoán vị a[j] và a[j-1]. Sau bước này thì a[0] có khóa nhỏ nhất.
Bước 2: xét các phần tử a[j] (j từ n-1 đến 2) nếu khóa của a[j] nhỏ hơn khóa của a[j-1] thì
hoán vị a[j] và a[j-1]. Sau bước này thì a[1] có khóa nhỏ nhất thứ 2.
Sau n-1 bước thì dừng lại.
Code trong chương trình C++:
void BubbleSort() {
for (int i = 0; i < n - 1; i++) {
for (int j = n - 1; j > i; j--) {

if (a[j] < a[j - 1]) {
sawp(a[j], a[j - 1]);
}

16


}
}
}

c) Giải thuật đổi chỗ trực tiếp Interchange Sort
Như đã biết, để sắp xếp một dãy số, ta có thể xét các nghịch thế có trong dãy và triệt
tiêu dần chúng đi. Ý tưởng chính của giải thuật là xuất phát từ đầu dãy, tìm tất cả nghịch
thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chổ phần tử này với phần tử tương
ứng trong cặp nghịch thế. Lặp lại xử lý trên với các phần tử kế tiếp theo trong dãy.
Ngôn ngữ mã giả:
Bước 1: i=0;
/ Bắt đầu từ đầu dãy
Bước 2: j = i+1; // Tìm tất cả các phần tử a[j]<a[i], với j>i
Bước 3: Trong khi j < N thực hiện
Nếu a[j]//xét cặp a[i], a[j]
Swap(a[i],a[j]);
j=j+1;
Bước 4:
i = i+1;
Nếu iNgược lại: Dừng.
Code trong chương trình C++:

void InterchangeSort() {
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] > a[j]) {
float tg = a[j];
a[j] = a[i];
a[i] = tg;
}
17


}
}
}

d) Giải thuật sắp sếp lựa chọn Selection Sort
Giải thuật sắp xếp chọn (Selection Sort) là một giải thuật đơn giản. Giải thuật sắp xếp
này là một giải thuật dựa trên việc so sánh in-place, trong đó danh sách được chia thành
hai phần, phần được sắp xếp (sorted list) ở bên trái và phần chưa được sắp xếp (unsorted
list) ở bên phải. Ban đầu, phần được sắp xếp là trống và phần chưa được sắp xếp là toàn
bộ danh sách ban đầu. Phần tử nhỏ nhất được lựa chọn từ mảng chưa được sắp xếp và
được tráo đổi với phần bên trái nhất và phần tử đó trở thành phần tử của mảng được sắp
xếp. Tiến trình này tiếp tục cho tới khi toàn bộ từng phần tử trong mảng chưa được sắp
xếp đều được di chuyển sang mảng đã được sắp xếp.
Giải thuật này không phù hợp với tập dữ liệu lớn khi mà độ phức tạp trường hợp xấu
nhất và trường hợp trung bình là O(n2) với n là số phần tử.
Ngôn ngữ mã giả:
Bước 1: Chọn phần tử có khóa nhỏ nhất trong n phần tử a[0],…, a[n-1] và hoán vị với
a[0]
Bước 2: Chọn phần tử có khóa nhỏ nhất trong n phần tử a[1],…, a[n-1] và hoán vị với

a[1]
Bước i: Chọn phần tử có khóa nhỏ nhất trong n phần tử a[i],…a[n-1] và hoán vị với a[i]
…
Sau n-1 bước này thì mảng đã được sắp xếp
Code trong chương trình C++:
void SelectionSort() {
int i, j, min_idx;
for (i = 0; i < n - 1; i++)
{
min_idx = i;
for (j = i + 1; j < n; j++)
if (a[j] < a[min_idx])
18


min_idx = j;
sawp(a[min_idx], a[i]);
}
}

e) Giải thuật sắp xếp chèn Insertion Sort
Thuật toán sắp xếp chèn thực hiện sắp xếp dãy số theo cách duyệt từng phần tử và
chèn từng phần tử đó vào đúng vị trí trong mảng con (dãy số từ đầu đến phần tử phía
trước nó) đã sắp xếp sao cho dãy số trong mảng sắp đã xếp đó vẫn đảm bảo tính chất của
một dãy số tăng dần.
Giải thuật này coi như được chia làm hai phần. Phần đầu là các phần tử đã được sắp
xếp. Từ phần tử tiếp theo, chèn nó vào vị trí thích hợp tại nữa đã sắp sao cho nó vẫn được
sắp xếp.
Ngôn ngữ mã giả:
Xem phần tử a[0] là một dãy đã có thứ tự

Bước 1: xen a[1] vào danh sách đã có thứ tự a[0] sao cho a[0], a[1] là danh sách đã có thứ
tự
Bước 2: xen a[2] vào danh sách đã có thứ tự a[0], a[1] sao cho a[0], a[1], a[2] là danh
sách đã có thứ tự
Tổng quát bước 1, xen a[i] vào danh sách đã có thứ tự a[0], a[1],…a[i-1] sao cho a[0],
a[1],…a[i] là danh sách đã có thứ tự. Sau n-1 bước thì kết thúc.
Code trong chương trình C++:
void InsertionSort() {
int pos, i;
float key;
for (i = 1; i < n; i++)
{
key = a[i];
pos = i - 1;

//tim vi tri chen key

while ((pos >= 0) && (a[pos] > key {
19


a[pos + 1] = a[pos];
pos--;
}
a[pos + 1] = key;

// chèn key vào dãy

}
}

6. Xây dựng chương trình Demo trên ngôn ngữ C++
a Các chức năng chính của chương trình
Cài đặt bốn giải thuật sắp xếp: sắp xếp nổi bọt Bubble Sort, đổi chỗ trực tiếp
Interchange Sort, sắp xếp chọn Selection Sort, sắp xếp chèn Insertion Sort.
Cài đặt chức năng và thiết kế Menu:
+ Lựa chọn giải thuật, lựa chọn cách nhập dãy số từ bàn phím, nhập từ file hay là sử dụng
cấp phát động.
+ Xuất kết quả ra màn hình, nếu sử dụng File thì xuất kết quả ra File
+ So sánh hiệu năng của các thuật toán với nhau
+ Thoát chương trình

f)

Các hàm cơ bản được sử dụng trong chương trình

void PhongChu(){ … }

// Tùy chỉnh kích thước và Form trên màn hình Console

void SetColor(){ … }

// Tùy chỉnh màu

void Nhap(){ … }

// Thủ tục nhập cơ bản

void Random(){ … }

// Thủ tục cấp phát động

void Xuat(float t, bool SoSanh, bool XuatBT){ … }

// Thủ tục xuất kết quả

void sawp(float& xp, float& yp){ … }

// Thủ tục đổi chỗ hai phần tử

void XuatFile(float T){ … }

// Xuất dữ liệu ra file
20


void TiengViet(){ … }// Sử dụng bảng mã UTF-8 để xuất chữ cái tiếng Việt
void BubbleSort(){ … }

// Hàm sắp xếp Bubble Sort

void InterchangeSort(){ … }

// Hàm sắp xếp Interchange Sort

void SelectionSort(){ … }

// Hàm sắp xếp Selection Sort

void InsertionSort(){ … }

// Hàm sắp xếp Insertion Sort

void TraVeKhong(){ … }

// Trả về giá trị tất cả các biến về “0”

void ThuatToanNhanhNhat(){ … }

// Tìm thuật toán nhanh nhất

void SoSanh(float a[], int n){ … }// Thủ tục so sánh tốc độ xử lý các thuật toán
void Menu(){ … }

// Xuất Menu bắt đầu

void Menu2(){ … }

// Xuất Menu lựa chọn dữ liệu xử lý

void XuLyMenu(){ … }
int main(int argc, char* argv[]){ … }

// Thủ tục xử lý menu
// Hàm Main

21


CHƯƠNG 3. PHÂN TÍCH DEMO

1 Giới thiệu Demo
Chương trình Demo chạy trên ngôn ngữ lập trình C++. Với giao diện trên màn hình
Console hiển thị như sau:

Hình 9. Giao diện chương trình

1 Thực nghiệm với thuật toán sắp xếp nổi bọt Bubble Sort
Chọn thuật toán sắp xếp nổi bọt Bubble Sort và chọn cách nhập dãy số tự chọn.

22


Hình 10. Lựa chọn dữ liệu cần sắp xếp
Ta nhập vào dãy số gồm 10 chữ số, kết quả hiển thị như sau:

Hình 11. Kết quả từ dãy số nhập vào

23


Tương tự với cấp phát động và lấy dữ liệu từ File:

Hình 12. Kết quả từ dãy số cấp phát động

Hình 13. Kết quả từ File bên ngoài

24

Đọc dữ liệu từ File Text:

Hình 14. Mở File Text

25