Sắp xếp là một khái niệm mà chúng ta dễ dàng gặp trong cuộc sống cũng như trong công việc. Cùng lấy một vài ví dụ:
- Sắp xếp lại đồ đạc trong phòng, trong nhà.
- Sắp xếp các tài liệu trong tủ sách theo thứ tự.
- Sắp xếp công việc cho anh em trong công ty.......
Trong Tin học, việc sắp xếp luôn luôn diễn ra không ngừng mà đôi khi chúng ta không nhận ra. Chẳng hạn, trong mỗi folder của máy tính, các tệp đều được sắp xếp theo thứ tự bảng chữ cái, và người dùng hoàn toàn có thể điều chỉnh việc sắp xếp theo những thứ tự khác nhau như: ngày tạo tệp, kích thước tệp,...Có đến 40%40\% thời gian tính toán của máy tính là dành cho việc sắp xếp. Mục tiêu của tất cả những việc này, không gì khác ngoài giúp cho dữ liệu được tổ chức một cách khoa học, ngăn nắp, dễ dàng tìm kiếm khi cần đến. Không phải ngẫu nhiên mà giải thuật Sắp xếp nhanh [Quick Sort] được bình chọn là một trong những giải thuật tiêu biểu nhất của thế kỷ XX.
Trong chuyên đề này, chúng ta sẽ cùng xem xét bài toán sắp xếp các đối tượng trong một tập hợp cố định. Giả sử, ta có một tập hợp gồm nn phần tử a1,a2,...,an;a_1, a_2,..., a_n; mỗi phần tử có một giá trị ai.keya_i.key được gọi là khóa sắp xếp. Khi đó mỗi phần tử có thể được biểu diễn bằng một
struct Student
{
string name, class; // Tên và lớp.
double final_point; // Điểm tổng kết.
};
Student a[maxn]; // Mảng A có tối đa maxn phần tử.
2 hoặc
struct Student
{
string name, class; // Tên và lớp.
double final_point; // Điểm tổng kết.
};
Student a[maxn]; // Mảng A có tối đa maxn phần tử.
3, hoặc cũng có thể chỉ là các phần tử đơn lẻ thông thường với kiểu dữ liệu nguyên thủy. Nhiệm vụ đặt ra là cần sắp xếp mảng aa gồm nn đối tượng thành tập có giá trị khóa tăng dần:
a1.key≤a2.key≤⋯≤an.keya_1.key \le a_2.key \le \cdots \le a_n.key
II. Một số giải thuật sắp xếp thường gặp
1. Sắp xếp nổi bọt [Bubble Sort]
Ý tưởng: Xét các cặp phần tử của dãy, nếu như chúng đang đứng sai thứ tự [phần tử đứng trước lại có khóa lớn hơn phần tử đứng sau] thì đổi chỗ chúng, cho tới khi không còn cặp nào đứng sai thứ tự.
Cài đặt mã giả C++:
void bubble_sort[a[]]
{
for [i = 1; i < n; ++i]
for [int j = i + 1; j a[j].key]
swap[a[i], a[j]];
}
Đánh giá độ phức tạp: Tại lượt duyệt thứ ii của vòng lặp bên ngoài, ta cần thực hiện n−in - i lần phép so sánh
struct Student
{
string name, class; // Tên và lớp.
double final_point; // Điểm tổng kết.
};
Student a[maxn]; // Mảng A có tối đa maxn phần tử.
4. Như vậy tổng số phép so sánh là:
[n−1]+[n−2]+⋯+1=n.[n−1]2[n - 1] + [n - 2] + \cdots + 1 = \frac{n.[n - 1]}{2}
Vậy giải thuật có độ phức tạp tương đương O[n2]O[n^2]. Do đó, trong lập trình thi đấu giải thuật này chỉ phù hợp khi cần sắp xếp những tập hợp có khoảng 20002000 phần tử hoặc ít hơn, nếu nhiều hơn sẽ gây ra quá thời gian chạy [TLE].
Ví dụ 1: Sắp xếp tăng dần mảng AA gồm nn số nguyên a1,a2,...,an?a_1, a_2,..., a_n?
void bubble_sort[int a[]]
{
for [int i = 1; i < n; ++i]
for [int j = i + 1; j a[j]]
swap[a[i], a[j]];
}
Ví dụ 2: Một danh sách học sinh gồm nn học sinh, mỗi học sinh có 33 thông số: Tên, Lớp, Điểm tổng kết. Cần sắp xếp các học sinh này theo thứ tự tăng dần về Điểm tổng kết?
Ta có thể biểu diễn danh sách học sinh bằng một mảng AA gồm nn phần tử kiểu
struct Student
{
string name, class; // Tên và lớp.
double final_point; // Điểm tổng kết.
};
Student a[maxn]; // Mảng A có tối đa maxn phần tử.
2 lưu ba thông số trên:
struct Student
{
string name, class; // Tên và lớp.
double final_point; // Điểm tổng kết.
};
Student a[maxn]; // Mảng A có tối đa maxn phần tử.
Kế đến, áp dụng giải thuật sắp xếp nổi bọt với khóa sắp xếp là trường \text{final_point} của mỗi phần tử:
void bubble_sort[Student a[]]
{
for [int i = 1; i < n; ++i]
for [int j = i + 1; j a[j].final_point]
swap[a[i], a[j]];
}
2. Sắp xếp nhanh [Quick Sort]
Giải thuật Sắp xếp nổi bọt chưa đủ tốt với các trường hợp tập sắp xếp có kích thước lớn. Trong trường hợp đó, ta cần một giải thuật tốt hơn, đó là Sắp xếp nhanh.
Ý tưởng: Coi rằng ta đang cần sắp xếp một đoạn có chỉ số từ 11 tới nn trên mảng. Để sắp xếp một đoạn al...ra_{l...r} trong dãy, ta làm như sau:
- Nếu đoạn đó chỉ gồm 11 phần tử thì nó đã được sắp xếp.
- Nếu đoạn đó có nhiều hơn 11 phần tử, chọn giá trị a[mid]a[mid] nằm giữa đoạn làm chốt. Kế đến, ta hoán đổi các phần tử ở hai bên của chốt sao cho: Mọi phần tử có khóa sắp xếp nhỏ hơn khóa của chốt sẽ đứng sang bên trái nó, mọi phần tử có khóa sắp xếp lớn hơn khóa của chốt sẽ đứng sang bên phải nó.
- Tiếp tục sắp xếp theo kiểu trên với hai đoạn con ở hai bên, cuối cùng ta sẽ thu được mảng ban đầu sắp xếp tăng dần theo khóa.
Mã giả C++: Chọn amida_{mid} là phần tử ở giữa đoạn [l,r],[l, r], đồng thời duy trì hai biến i=l,j=ri = l, j = r. Chạy ii sang phải và jj sang trái, nếu phát hiện một cặp vị trí sai thứ tự: i≤ji \le j và ai.key≥amid.key≥aj.keya_i.key \ge a_{mid}.key \ge a_j.key thì hoán đổi vị trí của chúng. Duy trì làm như vậy tới khi i>j,i > j, rồi tiếp tục gọi đệ quy để sắp xếp hai đoạn con trái - phải:
void quick_sort[l, r, a[]]
{
i = l, j = r;
mid = [l + r] / 2;
while [i a[mid].key]
--j;
// Nếu i a_right]
{
return [a_left.first < a_right.first
|| [a_left.first == a_right.first && a_left.second > a_right.second]];
}
Sử dụng hàm trên để kiểm tra một cặp [ai,aj][a_i, a_j] trong đoạn cần sắp xếp có nằm đúng vị trí so với amida_{mid} hay không, nếu không thì cần đổi chỗ chúng:
void quick_sort[int l, int r, pair < int, int > a[]]
{
int i = l, j = r;
int mid = [l + r] / 2;
while [i