CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

NHÓM 2


CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

NHÓM 2

MỤC LỤC
CHƯƠNG 1: GIỚI THIỆU...........................................................................................2
1.1

Ý tưởng...............................................................................................................2

1.2

Hiện thực............................................................................................................2

1.3

Đánh giá.............................................................................................................. 3

CHƯƠNG 2: SO SÁNH CÁC PHƯƠNG PHÁP SẮP XẾP…………...............4
1. Tại sao cần phải có sắp xếp?...................................................................................4
2. Đâu mới là thuật toán sắp xếp tốt nhất?..................................................................5

CHƯƠNG 3: PHÂN TÍCH VÀ CÀI ĐẶT VÀ MINH HOẠ PHƯƠNG PHÁP SẮP
XẾP SHAKER...........................................................................................................9
3.1 Thiết kế thuật toán...............................................................................................9
3.2 Ý tưởng thiết kế....................................................................................................9

3.3 Ví dụ.................................................................................................................... 10

CHƯƠNG 4: BÀI TỐN ÁP DỤNG..................................................................12

iii


CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

NHĨM 2

Phân cơng thực hiện
Nội dung thực hiện

Người thực hiện

Thu thập dữ liệu

Hữu Lợi

Phân tích dữ liệu

Mỹ Hạnh

Xây dựng code
Soạn Word

Thanh Tín – Hồng Thi
Ngọc Hà


Ghi chú


CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

NHÓM 2

LỜI CẢM ƠN
Đầu tiên, chúng em xin gửi lời cảm ơn chân thành đến Trường Đại học Đồng Tháp và Khoa
Sư phạm Toán Tin đã đưa môn học Cấu trúc dữ liệu và Giải thuật vào chương trình giảng dạy. Đặc
biệt, chúng em xin gửi lời cảm ơn sâu sắc đến giảng viên bộ môn – Thầy Vũ Long Vân đã dạy dỗ,
truyền đạt những kiến thức quý báu cho em trong suốt thời gian học tập vừa qua. Trong thời gian
tham gia lớp học của thầy, chúng em đã có thêm cho mình nhiều kiến thức bổ ích, tinh thần học tập
hiệu quả, nghiêm túc. Đây chắc chắn sẽ là những kiến thức quý báu, là hành trang để em có thể
vững bước sau này.
Bộ môn Cấu trúc dữ liệu và Giải thuật là mơn học thú vị, vơ cùng bổ ích và có tính thực tế
cao. Đảm bảo cung cấp đủ kiến thức, gắn liền với nhu cầu thực tiễn của học viên. Tuy nhiên, do vốn
kiến thức còn nhiều hạn chế và khả năng tiếp thu thực tế còn nhiều bỡ ngỡ. Mặc dù chúng em đã cố
gắng hết sức nhưng chắc chắn trong bài tập lớn khó có thể tránh khỏi những thiếu sót và nhiều chỗ
cịn chưa chính xác, kính mong thầy xem xét và góp ý để bài tập của chúng em được hoàn thiện hơn.
Chúng em xin chân thành cảm ơn!

1


CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

NHÓM 2

CHƯƠNG 1:

GIỚI THIỆU PHƯƠNG PHÁP SẮP XẾP SHAKER
1.1.

Ý tưởng

Shaker Sort là một cải tiến của Bubble Sort.
Sau khi đưa phần tử nhỏ nhất về đầu mảng sẽ đưa phần tử lớn nhất về cuối dãy. Do đưa các phần tử
về đúng vị trí ở cả hai đầu nên Shaker Sort sẽ giúp cải thiện thời gian sắp xếp dãy số do giảm được
độ lớn của mảng đang xét ở lần so sánh kế tiếp.

Hình 1.1. Shaker Sort
1.2.

Hiện thực

void shakerSort(int a[], int n)
{
int Left = 0;
int Right = n - 1;
int k = 0;
while (Left < Right)
{
for (int i = Left; i < Right; i++)
{
if (a[i] > a[i + 1])
{
swap(a[i], a[i + 1]);
k = i;
}
}

Right = k;
for (i = Right; i > Left; i--)
{
if (a[i] < a[i - 1])
{
swap(a[i], a[i - 1]);

2


CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

NHÓM 2

k = i;
}
}
Left = k;
}
}
1.3.

Đánh giá

Shaker Sort là một dạng nâng cao của Bubble Sort, độ phức tạp cho trường hợp:


Tốt nhất là O(n).




Xấu nhất là O(n2).



Trung bình là O(n2).

Thuật tốn nhận diện được mảng đã sắp xếp.

3


CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

NHÓM 2

CHƯƠNG 2:
SO SÁNH CÁC PHƯƠNG PHÁP SẮP XẾP
Sắp xếp là một trong những thuật tốn kinh điển và quan trọng trong lập trình. Vậy đâu là
thuật toán sắp xếp tốt nhất?
Các so sánh dưới đây dựa theo kết quả nghiên cứu của tác giả [1].
2.1. Tại sao cần phải sắp xếp?
Thử tượng tượng bạn cần tra cứu 1 từ trong từ điển, tuy nhiên cuốn từ điển đó lại khơng được
sắp xếp theo thứ tự alphabet, các từ trong từ điển được sắp xếp theo 1 quy luật ngẫu nhiên. Khi đó,
việc bạn phải làm là lật từng trang, với mỗi trang bạn lại phải cố tìm kiếm xem từ bạn cần tìm có
trong trang đó hay khơng. Và việc này khiến bạn phải bỏ ra khá nhiều thời gian và công sức. Tuy
nhiên, với 1 cuốn từ điển được sắp xếp theo thứ tự alphabet thì cơng việc tra cứu của bạn là khá dễ
dàng.
Hay thử lấy 1 ví dụ khác, nếu như bạn được cho một danh sách điểm của sinh viên tồn
trường, u cầu đặt ra là tìm sinh viên có điểm số cao nhất, khi đó việc bạn phải làm là duyệt qua

từng sinh viên và tìm ra sinh viên có điểm số cao nhất, cơng việc này khá dễ dàng và hồn tồn có
thể thực hiện được, thế nhưng câu chuyện khơng dừng lại ở đó. Bởi nếu công việc yêu cầu là lọc ra
top 10 sinh viên có điểm số cao nhất để phục vụ cơng tác khen thưởng, với 1 danh sách chưa được
sắp xếp bạn sẽ phải lần lượt tìm ra sinh viên có điểm số cao thứ nhất, thứ 2, thứ 3, ... việc này cũng
làm cho bạn tốn rất nhiều thời gian và công sức, đặc biệt khi số lượng sinh viên trong danh sách càng
tăng thì thời gian và cơng sức bạn bỏ ra cũng tỉ lệ thuận theo số lượng đó. Tuy nhiên với một danh
sách sinh viên với điểm số đã được sắp xếp(giả sử sắp xếp theo thứ tự giảm dần), thì cơng việc của
bạn đơn giản là lấy ra 10 sinh viên đầu tiên trong danh sách. Qua những ví dụ trên có thể thấy rằng,
sắp xếp khiến cho những thao tác tìm kiếm hay lọc của chúng ta trở nên dễ dàng hơn rất nhiều. Chính
vì vậy, sắp xếp là một trong những bài toán quan trọng trong lập trình. Trong lập trình hiện tại có
khơng dưới 20 thuật tốn phục vụ cho cơng việc sắp xếp.
Bảng 2.1. Bảng thống kê một số thông số của các thuật toán (Theo Wikipedia)

STT
Thuật toán
1
Bubble Sort
2
Shaker Sort
3
Selection Sort
4
Insertion Sort
5 Binary Insertion Sort

Tốt nhất
O(n)
O(n)
O(n²)
O(n)

O(n)

Độ phức tạp
Trung bình
O(n²)
O(n²)
O(n²)
O(n²)
O(n²)

Xấu nhất
O(n²)
O(n²)
O(n²)
O(n²)
O(n²)

Bộ nhớ
O(1)
O(1)
O(1)
O(1)
O(1)

Stable
Có
Có
Khơng
Có
Có



CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

6

Shell Sort

O(nlogn)

7
8
9
10
11
12

Heap Sort
Merge Sort
Quick Sort
Counting Sort
Radix Sort
Flash Sort

O(nlogn)
O(nlogn)
O(nlogn)
O(n+k)
O(kn)
O(n)


NHÓM 2

depends on gap
sequence
O(nlogn)
O(nlogn)
O(nlogn)
O(n + k)
O(nk)
O(n + r)

O(n2)
O(nlogn)
O(nlogn)
O(n²)
O(n + k)
O(nk)
O(n²)

O(1)

Khơng

O(1)
Khơng
O(n)
Có
O(logn) Có/Khơng
O(n + k)

Có
O(n + k)
Có
O(m)
Khơng

2.2. Đâu mới là thuật tốn sắp xếp tốt nhất?
Có lẽ đây cũng là câu hỏi của rất nhiều người khi mới học lập trình, trong bài viết này tác giả đã thực
hiện một thử nghiệm nhỏ với 12 thuật toán sắp xếp để tìm ra câu trả lời! Thử nghiệm được tiến hành
với kích thước dữ liệu đầu vào lần lượt là 3.000, 10.000, 100.000, 300.000, với các loại dữ liệu lần
lượt là mảng có thứ tự ngẫu nhiên, mảng có thứ tự tăng dần, mảng có thứ tự giảm dần, mảng gần như
đã có thứ tự tăng dần (sai ở 1 số vị trí), và mục đích là đưa về mảng có thứ tự tăng dần.
Bảng 2.2.1. Bảng thống kê với dữ liệu đầu vào ngẫu nhiên

Bảng 2.2.2. Bảng thống kê với dữ liệu đầu vào có thứ tự tăng dần


CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

NHÓM 2

Bảng 2.2.3. Bảng thống kê với dữ liệu đầu vào có thứ tự giảm dần

Bảng 2.2.4. Bảng thống kê với dữ liệu đầu vào gần như có thứ tự tăng dần


CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

NHĨM 2


Nhận xét:


Với kích thước dữ liệu đầu vào nhỏ (3000) nhìn chung tốc độ chênh lệch của các thuật tốn là
khơng rõ để nhận thấy.



Với mảng đã được sắp xếp, thì Bubble Sort và Shaker Sort cho tốc độ nhanh nhất do chi phí
để biết được đây là mảng có thứ tự của 2 thuật toán trên là O(n).



Với mảng gần như đã được sắp xếp thì Insertion Sort và Binary Insertion Sort là những sự lựa
chọn tốt nhất do số phép hoán đổi phải thực hiện ít.



Selection Sort cho tốc độ khá chậm trong đa số trường hợp do độ phức tạp ln là O(n2), do
đó Selection Sort chỉ nên dùng cho các trường hợp số lượng phần tử cần sắp xếp khơng q
nhiều.



Với mảng gần như đã được sắp xếp thì Shaker Sort cho tốc độ nhanh hơn đáng kể so với
Bubble Sort, do thu hẹp được khoảng phải duyệt tiếp theo sau khi duyệt.



Shell Sort, Heap Sort, Merge Sort và Quick Sort có tốc độ ổn định xuyên suốt cả 4 loại dữ

liệu đầu vào.



Flash Sort(được phát minh bởi Karl-Dietrich Neubert vào năm 1998) là một thuật toán cho
tốc độ nhanh(thậm chí nhanh hơn cả Quick Sort) và tiêu tốn rất ít bộ nhớ, tuy nhiên cách thức
xây dựng thuật toán trên khá phức tạp.



Counting Sort và Radix Sort là những thuật toán cho tốc độ nhanh, tuy nhiên cần đánh đổi
bằng cách sử dụng thêm bộ nhớ.
[1] Haiduc0147, CODELEARNING, ngày 13/12/2020 />

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

NHÓM 2

CHƯƠNG 3:


CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

NHÓM 2

CÀI ĐẶT VÀ MINH HOẠ PHƯƠNG PHÁP SẮP XẾP SHAKER
3.1. Thiết kế thuật tốn

Code chương trình con Shakersort
3.2. Ý tưởng thiết kế:

-Bước 1: Khai báo kiểu biến và giá trị cho biến cần sử dụng trong đoạn chương trình, cụ thể chương
trình ở đây sử dụng biến left, right, và k.
+ Do chúng ta đang có 1 mảng 1 chiều và nhiệm vụ trong thuật toán shakersort này ta cần
phải gán biến left = 0 (chính là biến ở đầu mảng), right = n-1 (biến ở cuối mảng), k=n-1 (định vị trí
bắt đầu lắc).
-Bước 2: Sau đó, ta dùng 1 vịng lặp while với điều kiện lặp là left < right. Trong vòng lặp while này
sẽ có 2 vịng lặp for nữa, ta cứ hiểu 2 vòng lặp for này là 1 lượt đi và 1 lượt về.
+ Lượt đi:


CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT



NHĨM 2

Ta duyệt vịng lặp for từ cuối mảng tới đầu mảng, nếu gặp cặp nghịch thế (số trước lớn
hơn số đầu) thì ta gọi hàm hoán vị (hoặc dùng swap(M[i-1], M[i]). Trong lần lặp này sẽ
đưa được giá trị nhỏ nhất trong mảng về vị trí đầu tiên.



Dùng biến k đánh dấu để bỏ qua đoạn đã được sắp xếp thứ tự.

+ Lượt về:


Lấy k = left. Ta duyệt từ đầu mảng đến cuối mảng bắt đầu từ vị trí k , nếu gặp cặp nghịch
thế( số trước lớn hơn số đầu) thì ta gọi hàm hoán vị (hoặc dùng swap(M[i] ,M[i+1]);).
Trong lần lặp này sẽ đưa được giá trị lớn nhất trong mảng về vị trí cuối cùng.




Dùng biến k đánh dấu để bỏ qua đoạn đã được sắp xếp thứ tự. Sau đó gán k = right

-Bước 3: Lặp lại bước 2


Kiểm tra chiều dài đoạn cần sắp xếp nếu = 1 thì ngưng, cịn nếu > 1 thì lặp lại bước 2.

3.3. Ví dụ:
Ta có mảng cần sắp xếp như hình 1.1

Hình 1.1. ShakerSort


CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

Kết quả chạy chương trình

NHĨM 2


CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

NHĨM 2

CHƯƠNG 4:
BÀI TỐN ÁP DỤNG
Sử dụng hàm random để tạo ra một dãy M có 1.000 số ngun. Vận

dụng thuật tốn sắp xếp shaker để sắp xếp các phần tử của mảng M
theo thứ tự tăng dần về mặt giá trị.


CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

NHÓM 2