Bài giảng Cấu trúc dữ liệu 1 - Chương 2: Tìm kiếm và sắp xếp

Only one subarray
162
2 4 5 6 8 12 151
2 3 4 5 6 7 81
Merge sort – Ví dụ
163
Merge Sort – Cài đặt
• Dữ liệu hỗ trợ: 2 mảng b, c:
int b[MAX], c[MAX], nb, nc;
• Các hàm cần cài đặt:
– MergeSort: Sắp xếp mảng (a, N) tăng dần
void MergeSort(int a[], int N);
– Distribute: Phân phối đều luân phiên các dãy con độ dài k từ
mảng a vào hai mảng b và c
void Distribute(int a[], int N, 
int &nb, int &nc, int k);
– Merge: Trộn mảng b và mảng c vào mảng a
void Merge(int a[], int nb, int nc, int k);
– MergeSubarr: Trộn 1 cặp dãy con từ b và c vào a
void MergeSubarr(int a[], int nb, int nc, 
int &pa, int &pb, int &pc, int k);
164
Merge sort – Cài đặt
//khai báo 2 mảng phụ
int b[MAX], c[MAX], nb, nc;
void MergeSort(int a[], int N)
{ 
int k;
for (k = 1; k < N; k *= 2) 
{
Distribute(a, N, nb, nc, k);
Merge(a, nb, nc, k);
}
}
165
Merge sort – Cài đặt
void Distribute(int a[], int N,
int &nb, int &nc, int k)
{ 
int i, pa, pb, pc;
pa = pb = pc = 0;
while (pa < N)
{
for (i=0; (pa<N) && (i<k); i++, pa++, pb++)
b[pb] = a[pa];
for (i=0; (pa<N) && (i<k); i++, pa++, pc++)
c[pc] = a[pa];
}
nb = pb; nc = pc;
}
166
Merge sort – Cài đặt
void Merge(int a[], int nb, int nc, int k)
{ 
int pa, pb, pc;
pa = pb = pc = 0;
while ((pb < nb) && (pc < nc))
MergeSubarr(a, nb, nc, pa, pb, pc, k);
while (pb < nb)
a[pa ++] = b[pb ++];
while (pc < nc)
a[pa ++] = c[pc ++];
}
167
Merge sort – Cài đặt
void MergeSubarr(int a[], int nb, int nc,
int &pa, int &pb, int &pc, int k)
{ 
int rb, rc;
rb = min(nb, pb+k); rc = min(nc, pb+k);
while ((pb < rb) && (pc < rc))
if (b[pb] < c[pc])
a[pa ++] = b[pb ++];
else a[pa ++] = c[pc ++];
while (pb < rb)
a[pa ++] = b[pb ++];
while (pc < rc)
a[pa ++] = c[pc ++];
}
168
Merge Sort – Đánh giá giải thuật
Giải thuật trộn trực tiếp là phương pháp trộn đơn giản 
nhất:
• Việc phân hoạch thành các dãy con chỉ là tách dãy thành 
các dãy con không giảm độ dài k.
• Độ dài của dãy con là 1, 2, 4, 8, … đảm bảo dãy con luôn là
dãy con không giảm sau mỗi bước tách - trộn. 
• Không sử dụng thông tin về thứ tự của dãy ban đầu 
 2 hệ quả:
– Độ phức tạp thuật toán không phụ thuộc vào dãy ban đầu.
– Một dãy con không giảm đang có sẵn bị chia nhỏ thành các dãy 
không cần thiết  cải tiến thành thuật toán: Trộn tự nhiên 
(Natural Merge sort).
169
• Số lần thực hiện việc chia luân phiên và trộn: 
Sau mỗi lần tách – trộn, độ dài K của dãy con 
tăng gấp đôi  Số lần tách – trộn trong 
thuật toán: log2n . 
• Chi phí thực hiện tách - trộn tỉ lệ thuận với n. 
 Chi phí thực hiện của giải thuật MergeSort 
là O(nlog2n). 
Merge Sort – Đánh giá giải thuật
170
• Một nhược điểm lớn nữa của các thuật toán 
trộn là khi cài đặt thuật toán đòi hỏi thêm 
không gian bộ nhớ để lưu các dãy phụ b, c. 
• Hạn chế này khó chấp nhận trong thực tế vì
các dãy cần sắp xếp thường có kích thước lớn. 
• Vì vậy thuật toán trộn thường được dùng để
sắp xếp các cấu trúc dữ liệu khác phù hợp 
hơn như danh sách liên kết hoặc file. 
Merge Sort – Đánh giá giải thuật
171
Sắp xếp theo phương pháp trộn trực tiếp Thuật 
toán trộn tự nhiên Natural Merge sort
• Một đường chạy của dãy số a là một dãy con không 
giảm của cực đại của a. Nghĩa là, đường chạy 
r = (ai, ai+1, …, aj) phải thỏa điều kiện:
• Ví dụ dãy 12, 2, 8, 5, 1, 6, 4, 15 có thể coi như gồm 5 
đường chạy (12); (2, 8); (5); (1, 6); (4, 15).
⎪⎩
⎪⎨
⎧
>
<
∈∀≤
+
−
+
1
1
1 ),[
jj
ii
kk
aa
aa
jikaa
172
Sắp xếp theo phương pháp trộn trực tiếp Thuật 
toán trộn tự nhiên Natural Merge sort
• Thuật toán trộn tự nhiên khác thuật toán 
trộn trực tiếp ở chỗ thay vì luôn cứng nhắc 
phân hoạch theo dãy con có chiều dài k, việc 
phân hoạch sẽ theo đơn vị là đường chạy. ta 
chỉ cần biết số đường chạy của a sau lần phân 
hoạch cuối cùng là có thể biết thời điểm dừng 
của thuật toán vì dãy đã có thứ tự là dãy chi 
có một đường chạy. 
173
Sắp xếp theo phương pháp trộn trực tiếp Thuật 
toán trộn tự nhiên Natural Merge sort
• Bước 1 : // Chuẩn bị
– r = 0; // r dùng để đếm số dường chạy
• Bước 2 : Tách dãy a1, a2, …, an thành 2 dãy b, c theo nguyên 
tắc luân phiên từng đường chạy:
– Bước 2.1 : 
• Phân phối cho b một đường chạy; r = r+1;
• Nếu a còn phần tử chưa phân phối
– Phân phối cho c một đường chạy; r = r+1;
– Bước 2.2 : 
• Nếu a còn phần tử: quay lại bước 2.1;
• Bước 3 : 
– Trộn từng cặp đường chạy của 2 dãy b, c vào a. 
• Bước 4 : 
– Nếu r <= 2 thì trở lại bước 2; Ngược lại: Dừng.
Sắp xếp theo phương pháp Cơ số
Radix Sort 
175
Sắp xếp theo phương pháp cơ số Radix Sort 
• Radix Sort là một thuật toán tiếp cận theo một 
hướng hoàn toàn khác. 
• Nếu như trong các thuật toán khác, cơ sở để sắp 
xếp luôn là việc so sánh giá trị của 2 phần tử thì
Radix Sort lại dựa trên nguyên tắc phân loại thư
của bưu điện. Vì lý do đó Radix Sort còn có tên là
Postman’s sort. 
• Radix Sort không hề quan tâm đến việc so sánh giá
trị của phần tử mà bản thân việc phân loại và trình 
tự phân loại sẽ tạo ra thứ tự cho các phần tử. 
176
Sắp xếp theo phương pháp cơ số Radix Sort 
• Để chuyển một khối lượng thư lớn đến tay người nhận 
ở nhiều địa phương khác nhau, bưu điện thường tổ
chức một hệ thống phân loại thư phân cấp. 
• Trước tiên, các thư đến cùng một tỉnh, thành phố sẽ 
được sắp chung vào một lô để gửi đến tỉnh thành tương 
ứng. 
• Bưu điện các tỉnh thành này lại thực hiện công việc 
tương tự. Các thư đến cùng một quận, huyện sẽ được 
xếp vào chung một lô và gửi đến quận, huyện tương 
ứng. 
• Cứ như vậy, các bức thư sẽ được trao đến tay người 
nhận một cách có hệ thống mà công việc sắp xếp thư
không quá nặng nhọc. 
177
Sắp xếp theo phương pháp cơ số Radix Sort 
• Mô phỏng lại qui trình trên, để sắp xếp dãy 
a1, a2, ..., an, giải thuật Radix Sort thực hiện 
như sau:
– Trước tiên, ta có thể giả sử mỗi phần tử ai trong 
dãy a1, a2, ..., an là một số nguyên có tối đa m chữ 
số.
– Ta phân loại các phần tử lần lượt theo các chữ số
hàng đơn vị, hàng chục, hàng trăm, … tương tự
việc phân loại thư theo tỉnh thành, quận huyện, 
phường xã, ….
178
Sắp xếp theo phương pháp cơ số Radix Sort 
• Bước 1 :// k cho biết chữ số dùng để phân loại hiện 
hành
– k = 0; // k = 0: hàng đơn vị; k = 1: hàng chục; …
• Bước 2 : //Tạo các lô chứa các loại phần tử khác 
nhau
– Khởi tạo 10 lô B0, B1, …, B9 rỗng; 
• Bước 3 : 
– For i = 1 .. n do
• Đặt ai vào lô Bt với t: chữ số thứ k của ai;
• Bước 3 : 
– Nối B0, B1, …, B9 lại (theo đúng trình tự) thành a.
• Bước 4 : 
– k = k+1;Nếu k < m thì trở lại bước 2. Ngược lại: Dừng
179
Sắp xếp theo phương pháp cơ số Radix Sort 
180
Sắp xếp theo phương pháp cơ số Radix Sort 
181
Sắp xếp theo phương pháp cơ số Radix Sort 
182
Sắp xếp theo phương pháp cơ số Radix Sort 
183
Sắp xếp theo phương pháp cơ số Radix Sort 
184
Sắp xếp theo phương pháp cơ số Radix Sort 
• Đánh giá giải thuật:
– Với một dãy n số, mỗi số có tối đa m chữ số, 
thuật toán thực hiện m lần các thao tác phân lô 
và ghép lô. 
– Trong thao tác phân lô, mỗi phần tử chỉ được xét 
đúng một lần, khi ghép cũng vậy. 
– Như vậy, chi phí cho việc thực hiện thuật toán 
hiển nhiên là O(2mn) = O(n). 
185
Sắp xếp theo phương pháp cơ số Radix Sort 
Nhận xét:
– Sau lần phân phối thứ k các phần tử của A vào 
các lô B0, B1, …, B9, và lấy ngược trở ra, nếu chỉ
xét đến k+1 chữ số của các phần tử trong A, ta sẽ 
có một mảng tăng dần nhờ trình tự lấy ra từ 0 →
9. Nhận xét này bảo đảm tính đúng đắn của thuật 
toán.
– Thuật toán có độ phức tạp tuyến tính nên hiệu 
quả khi sắp dãy cố rất nhiều phần tử, nhất là khi 
khóa sắp xếp không quá dài so với số lượng phần 
tử (điều này thường gặp trong thực tế).
186
Sắp xếp theo phương pháp cơ số Radix Sort 
Nhận xét:
– Thuật toán không có trường hợp xấu nhất và tốt 
nhất. Mọi dãy số đều được sắp với chi phí như
nhau nếu chúng có cùng số phần tử và các khóa 
có cùng chiều dài.
– Thuật toán cài đặt thuận tiện với các mảng với 
khóa sắp xếp là chuỗi (ký tự hay số) hơn là khóa 
số như trong ví dụ do tránh được chi phí lấy các 
chữ số của từng số. 
187
Sắp xếp theo phương pháp cơ số Radix Sort 
Nhận xét:
– Số lượng lô lớn (10 khi dùng số thập phân, 26 khi 
dùng chuỗi ký tự tiếng Anh, …) nhưng tổng kích 
thước của tất cả các lô chỉ bằng dãy ban đầu nên 
ta không thể dùng mảng để biểu diễn B. Như vậy, 
phải dùng cấu trúc dữ liệu động để biểu diễn B 
⇒ Radix Sort rất thích hợp cho sắp xếp trên 
danh sách liên kết.
188
Sắp xếp theo phương pháp cơ số Radix Sort 
Nhận xét:
– Người ta cũng dùng phương pháp phân lô theo 
biểu diễn nhị phân của khóa sắp xếp. Khi đó ta 
có thể dùng hoàn toàn cấu trúc dữ liệu mảng để
biểu diễn B vì chỉ cần dùng hai lô B0 và B1. Tuy 
nhiên, khi đó chiều dài khóa sẽ lớn. Khi sắp các 
dãy không nhiều phần tử, thuật toán Radix sort 
sẽ mất ưu thế so với các thuật toán khác.