Người viết:
Reviewer:
Sắp xếp là một trong những thuật toán cơ bản và nền tảng của lập trình. Mọi ứng dụng xử lý dữ liệu ở mức tối thiểu đều cần sắp xếp theo một thứ tự nào đó. Ví dụ:
Ngoài ra, nhiều thuật toán phức tạp hơn (tìm kiếm, loại trùng, tối ưu hóa, hay các kỹ thuật sử dụng tính đơn điệu) đều dựa vào hoặc được đơn giản hóa nhờ dữ liệu đã được sắp xếp.
Trong C++, hàm std::sort là công cụ bạn thường dùng: nó sắp xếp mảng, vector theo thứ tự bạn mong muốn và đảm bảo độ phức tạp trong mọi trường hợp phổ biến.
Bài viết này sẽ làm rõ các thuật toán sắp xếp thường gặp trong thực tế (quicksort, mergesort, heapsort...), so sánh điểm mạnh/yếu của chúng, và đưa ra một số bài toán minh họa, giúp bạn hiểu khi nào nên dùng thuật toán nào và cách vận dụng chúng trong giải thuật.
Ban đầu, ta chọn ra phần tử nhỏ nhất trong phần tử, đưa nó về đầu dãy. Sau đó lặp lại quá trình sắp xếp với phần còn lại của dãy cho đến khi dãy tăng dần. Nói cách khác, với mỗi vị trí , ta sẽ tìm vị trí sao cho nhỏ nhất rồi hoán đổi và .
void selectionSort(int a[], int n){
for (int i = 0; i < n - 1; i++) {
int min_pos = i;
for (int j = i + 1; j < n; j++) {
if (a[j] < a[min_pos]) {
min_pos = j;
}
}
swap(a[i], a[min_pos]);
}
}
Độ phức tạp: .
Khác với sắp xếp chọn, sắp xếp nổi bọt sẽ so sánh trực tiếp với 2 phần tử liên tiếp. Nếu phần tử đứng trước lớn hơn phần tử đứng sau thì sẽ hoán đổi. Lặp lại cho đến khi dãy tăng dần.
void bubbleSort(int a[], int n){
for (int i = 0; i < n - 1; i++) {
bool swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
swapped = true;
}
}
// Nếu không có hoán đổi nào, mảng đã được sắp xếp
if (!swapped) break;
}
}
Độ phức tạp: .
Số lần hoán đổi (swap) của thuật toán bằng đúng số lượng cặp nghịch thế (inversions) của mảng ban đầu. Tức số cặp chỉ số sao cho .
Ta quan sát thấy mỗi lần ta hoán đổi của Bubble Sort sẽ làm giảm đúng nghịch thế. Hơn nữa, dãy cuối cùng đã được sắp xếp là một dãy không có nghịch thế nào. Từ đó, ta có thể kết luận quá trình giảm số nghịch thế xuống sẽ tốn số lần hoán đổi đúng bằng số nghịch thế ban đầu.
Ta lặp lại thao tác sắp xếp lần. Ở lần thứ , ta đã có dãy phần tử đầu tiên đã được sắp xếp. Để mở rộng thành dãy có phần tử đã được sắp xếp, ta xét rồi tìm vị trí thích hợp để chèn vào. Dễ dàng nhận thấy vị trí thích hợp sẽ là vị trí đứng trước một phần tử lớn hơn và sau phần tử nhỏ hơn hoặc bằng nó.
void insertionSort(int a[], int n){
for (int i = 1; i < n; i++) {
int x = a[i];
int j = i - 1;
while (j >= 0 && a[j] > x) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = x;
}
}
Độ phức tạp: .
Các thuật toán sắp xếp ở trên đều có độ phức tạp , nên trong nhiều trường hợp sẽ không đủ nhanh để xử lý dữ liệu lớn. Ở phần này, ta sẽ tìm hiểu một thuật toán có thể đạt hiệu năng tuyến tính trong những điều kiện phù hợp: Counting Sort.
Ta đếm tần suất xuất hiện của các phần tử, sau đó duyệt toàn bộ từ đến , nếu phần tử xuất hiện thì ta lần lượt in ra phần tử với là số lần xuất hiện của .
const int MAXV = 10000000;
int cnt[MAXV + 1];
void countingSort(int a[], int n){
for (int i = 0; i < n; i++) {
cnt[a[i]]++;
}
int idx = 0;
for (int v = 0; v <= MAXV; v++) {
while (cnt[v]--) {
a[idx++] = v;
}
}
}
Nhận xét: Vòng lặp ngoài ta sẽ chạy từ đến , vòng lặp trong in ra mỗi giá trị lần, vậy tổng tất cả các lần in bằng .
Độ phức tạp: .
Nhược điểm: Mảng không thể chứa các có giá trị âm hay quá lớn (vượt quá ).
Sắp xếp trộn là một thuật toán dựa trên ý tưởng Chia để trị như sau:
Đối với các bài toán cần mô phỏng phép gộp giống như trong Merge Sort, bạn đọc có thể tham khảo hàm merge của C++ STL.
void mergeArray(vector<int> &a, int left, int mid, int right){
vector<int> L(a.begin() + left, a.begin() + mid + 1);
vector<int> R(a.begin() + mid + 1, a.begin() + right + 1);
int i = 0, j = 0, k = left;
while(i < L.size() && j < R.size()){
if (L[i] <= R[j]) a[k++] = L[i++];
else a[k++] = R[j++];
}
while(i < L.size()) a[k++] = L[i++];
while(j < R.size()) a[k++] = R[j++];
}
void MergeSort(vector<int> &a, int left, int right){
if(left >= right) return;
int mid = (left + right) / 2;
MergeSort(a, left, mid);
MergeSort(a, mid + 1, right);
mergeArray(a, left, mid, right);
}
Nhận xét: Mỗi lần chia đôi có tầng chia để trị, ở mỗi tầng, tổng độ dài các dãy con là .
Độ phức tạp: .
Trước khi đến với thuật toán này, bạn đọc nên tham khảo kiến thức cần có về Binary Heap tại đây. Bạn đọc nên xem trước kiến thức trên vì trong bài viết mình sẽ không nói lại.
Heap Sort là thuật toán sắp xếp dựa trên cấu trúc dữ liệu heap - cụ thể là binary heap (cây nhị phân hoàn chỉnh)
Heap Sort hoạt động trên 2 giai đoạn chính:
// Hàm heapify để duy trì tính chất max-heap tại node i
void heapify(int a[], int n, int i){
int largest = i; // Giả sử node i là lớn nhất
int left = 2 * i + 1; // Con trái
int right = 2 * i + 2; // Con phải
// Nếu con trái lớn hơn cha
if(left < n && a[left] > a[largest])
largest = left;
// Nếu con phải lớn hơn cha (hoặc lớn hơn con trái)
if(right < n && a[right] > a[largest])
largest = right;
// Nếu node lớn nhất không phải là node cha
if(largest != i){
swap(a[i], a[largest]); // Hoán đổi
heapify(a, n, largest); // Gọi đệ quy
}
}
void heapSort(int a[], int n){
// Bước 1: Xây dựng max heap
for(int i = n/2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Bước 2: Trích từng phần tử lớn nhất ra cuối mảng
for(int i = n-1; i >= 0; i--){
swap(arr[0], arr[i]); // Đưa max hiện tại ra cuối
heapify(arr, i, 0); // Duy trì heap cho phần còn lại
}
}
Quicksort là một trong những thuật toán sắp xếp hiệu quả nhất và được sử dụng rộng rãi trong nhiều thư viện lập trình hiện nay. Thuật toán hoạt động theo tư tưởng chia để trị:
Trước hết, ta chọn một phần tử làm , sau đó phân hoạch mảng sao cho mọi phần tử nhỏ hơn nằm ở bên trái, và mọi phần tử lớn hơn nằm ở bên phải. Khi mảng đã được chia thành hai phần độc lập, ta tiếp tục đệ quy sắp xếp từng phần con.
Điểm quan trọng nhất của Quicksort nằm ở việc chọn sao cho hai phần sau khi phân hoạch có kích thước tương đối cân bằng. Khi đó, cây đệ quy gần như là cây nhị phân cân bằng, giúp thuật toán đạt được hiệu năng tối ưu.
int vi_tri(int l, int r){
int pivot = a[r];
int i = l - 1;
for(int j = l; j < r; j++){
if(a[j] <= pivot){
i++;
swap(a[i], a[j]);
}
}
i++;
swap(a[i], a[r]);
return i;
}
void quicksort(int l, int r){
if(l >= r) return;
int pos = vi_tri(l, r);
quicksort(l, pos);
quicksort(pos + 1, r);
}
Phương pháp này được Tony Hoare phát triển cùng với khái niệm Quicksort ban đầu:
int vi_tri2(int l, int r){
int pivot = a[l];
int i = l - 1, j = r + 1;
while(true){
do{
i++;
}while(a[i] < pivot);
do{
j--;
}while(a[j] > pivot);
if(i < j){
swap(a[i], a[j]);
}
else return j;
}
}
void quicksort(int l, int r){
if(l >= r) return;
int pos = vi_tri2(l, r);
quicksort(l, pos);
quicksort(pos + 1, r);
}
Độ phức tạp:
Nhược điểm: Qua 2 ví dụ minh họa trên, ta thấy trong trường hợp tệ nhất, Quick Sort có thể chạy lên tới .
Radix Sort không sắp xếp bằng cách so sánh trực tiếp các phần tử, mà sắp xếp theo từng chữ số trong một hệ cơ số . Với hệ cơ số , mỗi số có tối đa chữ số.
Ở mỗi lượt, Radix Sort sắp xếp mảng theo một chữ số, bắt đầu từ chữ số thấp nhất (hàng đơn vị) đến chữ số cao nhất. Việc sắp xếp được thực hiện bằng Counting Sort, vì các chữ số chỉ nằm trong khoảng .
Nhờ tính ổn định này, thứ tự các chữ số đã được sắp xếp ở các lượt trước được giữ nguyên, đảm bảo sau khi xử lý tất cả các chữ số, mảng đã được sắp xếp hoàn chỉnh.
Ví dụ, để sắp xếp dãy gồm các số và hệ cơ số , Radix Sort thực hiện bước sắp xếp như sau:
void countingSortByDigit(vector<int>& a, int exp){
int n = a.size();
vector<int> v(n);
vector<int> dem(10, 0);
// Đếm số lượng xuất hiện của mỗi chữ số
for(int i = 0; i < n; i++){
int digit = (a[i] / exp) % 10;
dem[digit]++;
}
for(int i = 1; i < 10; i++){
dem[i] += dem[i - 1];
}
for(int i = n - 1; i >= 0; i--){
int digit = (a[i] / exp) % 10;
v[dem[digit] - 1] = a[i];
dem[digit]--;
}
for(int i = 0; i < n; i++){
a[i] = v[i];
}
}
void radixSort(vector<int>& a){
// Tìm số lớn nhất để biết số chữ số
int mx = *max_element(a.begin(), a.end());
for(int exp = 1; mx / exp > 0; exp *= 10){
countingSortByDigit(a, exp);
}
}
Độ phức tạp: với là số chữ số của số lớn nhất.
| Thuật toán | Độ phức tạp (Tốt / Trung bình / Xấu) | Bộ nhớ phụ | Tính ổn định | Cách sắp xếp | Ưu điểm | Nhược điểm |
|---|---|---|---|---|---|---|
| Selection Sort (Sắp xếp chọn) | Không ổn định | So sánh, đổi chỗ | Dễ cài đặt, ít hoán đổi | Hiệu năng kém với dữ liệu lớn | ||
| Bubble Sort (Sắp xếp nổi bọt) | Ổn định | So sánh–đổi chỗ | Dễ hiểu, nhận biết nhanh dữ liệu gần sắp xếp | Rất chậm với mảng lớn | ||
| Insertion Sort (Sắp xếp chèn) | / / | Ổn định | So sánh, chèn | Hiệu quả với mảng nhỏ hoặc gần sắp xếp | Kém hiệu quả với dữ liệu ngẫu nhiên | |
| Counting Sort (Sắp xếp đếm/phân phối) | Ổn định | Không so sánh | Rất nhanh với giá trị nhỏ, nguyên dương | Giới hạn phạm vi giá trị, tốn bộ nhớ | ||
| Radix Sort (Sắp xếp cơ số) | Ổn định | Không so sánh | Nhanh với số nguyên có độ dài chữ số cố định | Khó áp dụng cho dữ liệu không phải số hoặc độ dài khác nhau | ||
| Merge Sort (Sắp xếp trộn) | Ổn định | Chia để trị | Độ phức tạp ổn định, thích hợp dữ liệu lớn | Tốn bộ nhớ phụ | ||
| Heap Sort (Sắp xếp vun đống) | Không ổn định | So sánh–đổi chỗ | Không cần bộ nhớ phụ | Khó cài đặt, không ổn định | ||
| Quick Sort (Sắp xếp nhanh) | / / | Không ổn định | Chia để trị | Trung bình rất nhanh, sử dụng phổ biến | Dễ bị nếu chọn pivot kém |
Ở phần giới thiệu ta có nhắc đến hàm sort trong C++ (IntroSort). Về cơ bản, IntroSort chạy dựa trên QuickSort vì thuật toán này nhanh trong hầu hết các trường hợp. Khi phát hiện nguy cơ chậm và có thể rơi vào , nó sẽ chuyển sang dùng HeapSort để đảm bảo hiệu năng. Với các mảng nhỏ, thuật toán dùng thêm InsertionSort cho gọn và nhanh hơn. Nói ngắn gọn, đây là một thuật toán kết hợp nhiều thuật toán sắp xếp khác nhau tùy từng tình huống.
Trong lập trình, hầu hết các ngôn ngữ đều cung cấp hàm sắp xếp để sắp xếp các phần tử trong một dãy theo thứ tự tăng dần hoặc giảm dần.
Tuy nhiên, trong thực tế, không phải lúc nào chúng ta cũng chỉ cần sắp xếp theo giá trị thông thường.
Đôi khi, bài toán yêu cầu sắp xếp theo một tiêu chí đặc biệt — ví dụ như:
Để làm được điều này, ta cần truyền thêm 1 comparator (hàm so sánh tùy chỉnh) vào hàm sort.
Comparator là một hàm (hoặc biểu thức lambda) dùng để xác định quy tắc so sánh giữa 2 phần tử trong quá trình sắp xếp.
Cụ thể, comparator sẽ nhận vào 2 phần tử và , và trả về:
Nói cách khác, comparator giúp ta nói với hàm sort tiêu chí nào "nhỏ hơn" theo ý của riêng mình.
Giả sử ta có mảng:
vector<int> a = {-3, 7, -1, 4, 2};
Nếu sắp xếp bình thường, kết quả sẽ là:
-3, -2, -1, 4, 7
Ta cần tự định nghĩa comparator như sau:
bool cmp(int a, int b){
if (abs(a) != abs(b))
return abs(a) < abs(b);
return a < b; // phân biệt 2 và -2
}
Sau đó truyền vào hàm sort:
sort(a.begin(), a.end(), cmp);
Kết quả là:
-1, -2, -3, 4, 7
Giả sử ta có danh sách học sinh, mỗi học sinh có 2 thông tin: chiều cao và cân nặng.
struct Student{
int height;
int weight;
};
Danh sách ban đầu:
vector<Student> students = {
{170, 60},
{165, 55},
{170, 50},
{160, 45}
}
Yêu cầu:
bool cmp(const Student &a, const Student &b){
if(a.height == b.height)
return a.weight < b.weight;
return a.height < b.height;
}
sort(students.begin(), students.end(), [](const Student &a, const Student &b){
if(a.height == b.height)
return a.weight < b.weight;
return a.height < b.height;
});
Bạn được cho 2 mảng số nguyên cùng độ dài :
và .
Trong 1 thao tác, bạn được phép hoán đổi vị trí và (hoán đổi cả 2 mảng cùng lúc): , .
Mục tiêu biến 2 mảng và thành 2 dãy không giảm. Nếu có thể, in ra danh sách hoán đổi, ngược lại in ra .
Ta nhận xét rằng trong trạng thái cuối cùng, các cặp phải được sắp xếp theo một thứ tự tăng đồng thời - nghĩa là nếu một cặp đứng trước, thì cả 2 phần đều không lớn hơn phần sau.
Do đó, ta có mảng chỉ số và nó sắp xếp theo cặp .
Nếu sau khi sắp xếp, vẫn tồn tại hoặc thì việc sắp xếp đồng thời là không thể xảy ra.
Ngược lại, nếu điều kiện trên thỏa mãn, ta có thể dùng thuật toán sắp xếp (ở đây sẽ dùng bubble sort) để ghi nhận các phép hoán vị.
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--){
int n; cin >> n;
vector<int> a(n), b(n);
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 0; i < n; i++) cin >> b[i];
vector<int> tmp(n);
iota(tmp.begin(), tmp.end(), 0);
sort(tmp.begin(), tmp.end(), [&](int i, int j) {
if (a[i] == a[j]) return b[i] < b[j];
return a[i] < a[j];
});
bool ok = true;
for (int i = 0; i + 1 < n; i++) {
if (a[tmp[i]] > a[tmp[i + 1]] || b[tmp[i]] > b[tmp[i + 1]]) {
cout << -1 << "\n";
ok = false;
break;
}
}
if (!ok) continue;
vector<pair<int,int>> ans;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1; j++) {
if (a[j] > a[j + 1] || b[j] > b[j + 1]) {
swap(a[j], a[j + 1]);
swap(b[j], b[j + 1]);
ans.push_back({j + 1, j + 2});
}
}
}
cout << ans.size() << "\n";
for (auto [x, y] : ans)
cout << x << " " << y << "\n";
}
return 0;
}
Bài toán cho một dãy số gồm phần tử và yêu cầu đếm số lần hoán đổi khi sắp xếp dãy theo thứ tự không giảm bằng thuật toán Bubble Sort đã cho.
Nếu mô phỏng trực tiếp Bubble Sort thì độ phức tạp là , không đủ nhanh với .
Để đếm số nghịch thế, ta sử dụng Merge Sort kết hợp đếm nghịch thế trong quá trình trộn hai dãy con đã được sắp xếp.
Giả sử: Nửa trái đã được sắp xếp và nửa phải đã được sắp xếp.
Khi trộn: Nếu suy ra không có nghịch thế. Nếu , vì nửa trái đã được sắp xếp, nên tất cả các phần tử từ đến cuối nửa trái đều lớn hơn .
Số nghịch thế được cộng thêm là:
Độ phức tạp:
#include <bits/stdc++.h>
using namespace std;
long long cnt = 0;
vector<long long> a, tmp;
void merge_sort(int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = l;
while(i <= mid && j <= r){
if(a[i] <= a[j]){
tmp[k++] = a[i++];
}
else{
tmp[k++] = a[j++];
cnt += (mid - i + 1); // đếm nghịch thế
}
}
while(i <= mid) tmp[k++] = a[i++];
while(j <= r) tmp[k++] = a[j++];
for (int p = l; p <= r; p++) a[p] = tmp[p];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
a.resize(n);
tmp.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
merge_sort(0, n - 1);
cout << cnt;
return 0;
}
https://codeforces.com/problemset?tags=sortings,1200-1500