Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 8: Sắp xếp

 ký tự. Giải 
thuật radix_sort vốn được đưa ra trong những ngày đầu của lịch sử máy tính để 
sử dụng cho các thẻ đục lỗ, nhưng đã được phát triển thành một phương pháp sắp 
thứ tự rất hiệu quả cho các cấu trúc dữ liệu có liên kết . Ý tưởng được trình bày 
dưới đây cũng được xem như một ứng dụng khá thú vị của hiện thực liên kết của 
CTDL hàng đợi. 
Chương 8 – Sắp xếp 
Giáo trình Cấu trúc dữ liệu và Giải thuật 177
8.9.1. Ý tưởng 
Ý tưởng của giải thuật là xét từng ký tự một và chia danh sách thành nhiều 
danh sách con, số danh sách con phụ thuộc vào số ký tự khác nhau có trong khóa. 
Giả sử các khóa là các từ gồm các chữ cái, thì chúng ta chia danh sách cần sắp 
thứ tự ra 26 danh sách con tại mỗi bước và phân phối các phần tử vào các danh 
sách con này tương ứng với một trong các ký tự có trong khóa. 
Để sắp thứ tự các từ, trước tiên người ta thường chia chúng thành 26 danh 
sách con theo ký tự đầu tiên, sau đó lại chia mỗi danh sách con thành 26 danh 
sách con theo ký tự thứ hai, và cứ thế tiếp tục. Như vậy số danh sách con sẽ trở 
nên quá lớn, chúng ta khó nắm giữ được. Ý tưởng dưới đây nhằm tránh số lượng 
danh sách con bùng nổ quá lớn. Thay vì lần lượt xét các ký tự từ trái qua phải, 
chúng ta sẽ xét theo thứ tự từ phải qua trái. Trước tiên nên chia các phần tử vào 
các danh sách con theo vị trí của ký tự cuối của từ dài nhất. Sau đó các danh sách 
con này lại được nối lại thành một danh sách, thứ tự các từ trong mỗi danh sách 
con giữ nguyên, thứ tự nối các danh sách con tuân theo thứ tự alphabet của các ký 
tự tại vị trí vừa xét. Danh sách này lại được chia theo vị trí kế trước vị trí vừa 
rồi, rồi lại được nối lại. Cứ thế tiếp tục cho đến khi danh sách được chia theo vị 
trí đầu tiên của các chuỗi ký tự và được nối lại, chúng ta sẽ có một danh sách các 
từ có thứ tự theo alphabet. 
Quá trình này được minh họa qua việc sắp thứ tự 9 từ có chiều dài tối đa ba ký 
tự trong hình 8.16. Cột bên trái của hình vẽ là thứ tự ban đầu của các từ. Chúng 
được chia thành 3 danh sách tương ứng với 3 ký tự khác nhau ở vị trí cuối cùng, 
kết quả ở cột thứ hai của hình vẽ, mỗi hình khối biểu diễn một danh sách con. 
Thứ tự giữa các từ trong một danh sách con không thay đổi so với thứ tự giữa 
chúng trong danh sách lớn khi chưa được chia. Tiếp theo, các danh sách con được 
nối lại và được chia thành 2 danh sách con tương ứng 2 ký tự khác nhau ở vị trí 
kế cuối (vị trí thứ hai của từ) như cột thứ ba trong hình. Cuối cùng chúng được nối 
lại và chia thành 4 danh sách con tương ứng 4 ký tự khác nhau ở vị trí đầu của 
các từ. Khi các danh sách con được nối lại thì chúng ta có một danh sách đã có 
thứ tự. 
8.9.2. Hiện thực 
Chúng ta sẽ hiện thực phương pháp này trong C++ cho danh sách các mẫu tin 
có khóa là các chuỗi ký tự. Sau mỗi lần phân hoạch thành các danh sách con, 
chúng được nối lại thành một danh sách để sau đó lại được phân hoạch tiếp tương 
ứng với vị trí kế trước trong khóa. Chúng ta sử dụng các hàng đợi để chứa các 
danh sách con, do trong giải thuật, khi phân hoạch, các phần tử luôn được thêm 
vào cuối các danh sách con và khi nối lại thì các phần tử lại được lấy ra từ đầu 
các danh sách con (FIFO). 
Chương 8 – Sắp xếp 
Giáo trình Cấu trúc dữ liệu và Giải thuật 178
Nếu chúng ta dùng các CTDL hàng và danh sách tổng quát có sẵn để xử lý, sẽ 
có một số thao tác di chuyển các phần tử không cần thiết. Ngược lại, nếu sử dụng 
cấu trúc liên kết, có thể nối các hàng liên kết thành một danh sách kiên kết bằng 
cách nối rear của hàng này vào front của hàng kia, thì chương trình sẽ hiệu 
quả hơn rất nhiều. Quá trình này được minh họa trong hình 8.17. Chương trình 
radix_sort như vậy cần có thêm lớp dẫn xuất từ lớp Queue có bổ sung phương 
thức để nối các hàng lại với nhau, phần này có thể xem như bài tập. Phần minh 
họa tiếp theo chúng ta chỉ sử dụng lớp Queue đơn giản có sẵn. 
Chúng ta sẽ dùng một mảng có 28 hàng đợi để chứa 28 danh sách con. Vị trí 0 
tương ứng ký tự trống (khoảng trắng không có ký tự), các vị trí từ 1 đến 26 tương 
ứng các ký tự chữ cái (không phân biệt chữ hoa chữ thường), còn vị trí 27 tương 
ứng mọi ký tự còn lại (nếu có) xuất hiện trong khóa. Việc xử lý sẽ được lặp lại từ 
ký tự cuối đến ký tự đầu trong khóa, mỗi lần lặp chúng ta sẽ duyệt qua danh sách 
liên kết để thêm từng phần tử vào cuối mỗi danh sách con tương ứng. Sau khi 
danh sách đã được phân hoạch, chúng ta nối các danh sách con lại thành một 
danh sách. Cuối vòng lặp danh sách đã có thứ tự. 
Chúng ta sẽ hiện thực radix_sort như là một phương thức của 
Sortable_list. 
Hình 8.16 – Tiến trình của radix_sort. 
Chương 8 – Sắp xếp 
Giáo trình Cấu trúc dữ liệu và Giải thuật 179
// Có thể sử dụng cho bất kỳ hiện thực nào của List. 
template 
class Sortable_list: public List { 
public: // Các phương thức sắp thứ tự. 
 void radix_sort(); 
private: // Các hàm phụ trợ. 
 void rethread(Queue queues[]); 
}; 
Ở đây, lớp cơ sở List có thể là bất kỳ hiện thực nào của List trong chương 4. 
Hàm phụ trợ rethread sẽ được sử dụng để nối các hàng đợi. 
Chúng ta sẽ sử dụng các phương thức của lớp Record, char key_letter(int 
position) trả về ký tự tại position của khóa, hoặc trả về khoảng trắng nếu 
chiều dài của khóa nhỏ hơn position. Định nghĩa Record như sau: 
Hình 8.17 – Radix sort liên kết 
Chương 8 – Sắp xếp 
Giáo trình Cấu trúc dữ liệu và Giải thuật 180
class Record { 
public: 
 char key_letter(int position) const; 
 Record(); // constructor mặc định. 
 operator Key() const; // trả về khóa của phần tử. 
// Các phương thức và các thuộc tính khác của lớp. 
}; 
8.9.2.1. Phương pháp sắp thứ tự radix_sort 
const int max_chars = 28; 
template 
void Sortable_list::radix_sort() 
/* 
post: Các phần tử của danh sách đã được sắp theo thứ tự alphabet. 
uses: Các phương thức của các lớp List, Queue, và Record; 
 functions position and rethread. 
*/ 
{ 
 Record data; 
 Queue queues[max_chars]; 
 for (int position = key_size - 1; position >= 0; position--) { 
 // Lặp từ vị trí cuối đến vị trí đầu các chuỗi ký tự. 
 while (remove(0, data) == success) { 
 int queue_number = alphabetic_order(data.key_letter(position)); 
 queues[queue_number].append(data); // Đưa vào hàng thích hợp. 
 } 
 rethread(queues);// Nối các danh sách con trong các hàng thành danh sách. 
 } 
} 
Hàm này sử dụng hai hàm phụ trợ: alphabetic_order để xác định hàng đợi 
tương ứng với một ký tự cho trước, và Sortable_list::rethread() để nối các 
hàng. Chúng ta có thể dùng bất kỳ hiện thực nào của hàng tương thích với đặc tả 
Queue trừu tượng trong chương 3. 
8.9.2.2. Chọn một queue 
Hàm alphabetic_order lấy thứ tự của một ký tự cho trước trong bảng chữ 
cái, với quy ước rằng tất cả các ký tự không phải là ký tự chữ cái sẽ có cùng thứ 
tự là 27, khoảng trắng có thứ tự 0. Hàm không phân biệt chữ hoa và chữ thường. 
int alphabetic_order(char c) 
/* 
post: Trả về thứ tự của ký tự trong c theo thứ tự alphabet, hoặc trả về 0 nếu c là khoảng 
trắng. 
*/ 
{ 
 if (c == ' ') return 0; 
 if ('a' <= c && c <= 'z') return c - 'a' + 1; 
 if ('A' <= c && c <= 'Z') return c - 'A' + 1; 
 return 27; 
} 
Chương 8 – Sắp xếp 
Giáo trình Cấu trúc dữ liệu và Giải thuật 181
8.9.2.3. Nối các hàng 
Hàm rethread nối 28 hàng lại thành một Sortable_list. Hàm cũng làm 
rỗng tất cả các hàng này để chúng có thể được sử dụng trong lần lặp sau của giải 
thuật. Hàm này có thể được viết lại theo cách phụ thuộc vào hiện thực của các 
hàng để giải thuật radix_sort có thể chạy nhanh hơn, chúng ta xem như bài 
tập. 
template 
void Sortable_list::rethread(Queue queues[]) 
/* 
post: Mọi hàng được nối lại thành một danh sách, các hàng trở thành rỗng. 
uses: Các phương thức của các lớp List và Queue. 
*/ 
{ 
 Record data; 
 for (int i = 0; i < max_chars; i++) 
 while (!queues[i].empty()) { 
 queues[i].retrieve(data); 
 insert(size(), data); 
 queues[i].serve(); 
 } 
} 
8.9.3. Phân tích phương pháp radix_sort 
Chú ý rằng thời gian để chạy radix_sort là θ(nk), n là số phần tử cần sắp 
thứ tự và k là số ký tự có trong khóa. Thời gian cần cho các phương pháp sắp thứ 
tự khác của chúng ta phụ thuộc vào n và không phụ thuộc trực tiếp vào chiều dài 
của khóa. Thời gian tốt nhất là đối với merge_sort: nlgn + O(n). 
Hiệu quả tương đối của các phương pháp có liên quan đến kích thước nk và n 
lgn, có nghĩa là, k và lgn. Nếu các khóa có chiều dài lớn và số phần tử cần sắp 
thứ tự không lớn (k lớn và lg n tương đối nhỏ), thì các phương pháp khác, tựa như 
merge_sort, sẽ hiệu quả hơn radix_sort; ngược lại nếu k nhỏ (các khóa ngắn) 
và số phần tử cần sắp thứ tự nhiều, thì radix_sort sẽ nhanh hơn mọi phương 
pháp sắp thứ tự mà chúng ta đã biết. 
Chương 8 – Sắp xếp 
Giáo trình Cấu trúc dữ liệu và Giải thuật 182