[C++] – Sắp xếp

Giới thiệu:

Hàm sort trong C++ được cung cấp trong thư viện <algorithm>. Đây là một trong những hàm thường dùng nhất trong lập trình, đặc biệt là trong các bài toán thi đấu thuật toán. Hàm này có nhiệm vụ sắp xếp dãy phần tử trong một phạm vi nhất định (thường là mảng hoặc vector) theo một tiêu chí cho trước.

Cú pháp cơ sở

sort(first, last); 
sort(first, last, cmp);

Trong đó:

• first, last: iterator (hoặc con trỏ) xác định phạm vi cần sắp xếp.
• cmp: hàm so sánh tùy chọn (comparator). Nếu không truyền thì mặc định là sắp xếp tăng dần (theo toán tử <).

Ví dụ:

#include <bits/stdc++.h>
using namespace std;
int main() {
    vector<int> a = {5, 2, 9, 1, 3};
    
    // Sắp xếp tăng dần
    sort(a.begin(), a.end());
    
    // Sắp xếp giảm dần
    sort(a.begin(), a.end(), greater<int>());
    
    for (int x : a) cout << x << " ";
    return 0;
}

Ví dụ mở rộng biến thể sắp xếp giảm dần

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;

    // Cách 1: sort giảm dần với greater<>
    sort(a.begin(), a.end(), greater<long long>());

    // In kết quả
    for (int i = 0; i < n; ++i) {
        if (i) cout << ' ';
        cout << a[i];
    }
    cout << '\n';

    // --- Tham khảo thêm ---

    // Cách 2: comparator tự viết (lambda): a đứng trước b nếu a > b
    // sort(a.begin(), a.end(), [](long long x, long long y) {
    //     return x > y; // giảm dần
    // });

    // Cách 3: reverse iterator (giữ thứ tự giảm dần mà không cần comparator)
    // sort(a.rbegin(), a.rend()); // lưu ý: hoạt động như sort giảm dần

    return 0;
}

Ứng dụng trong lập trình

1. Giải quyết các bài toán cơ bản: tìm phần tử lớn nhất/nhỏ nhất, sắp xếp danh sách điểm, tên, số liệu.
2. Tiền xử lý dữ liệu: trước khi áp dụng các kỹ thuật khác (hai con trỏ, tìm kiếm nhị phân, quy hoạch động).
3. Ứng dụng trong thuật toán nâng cao: Kruskal (cây khung nhỏ nhất), xử lý sự kiện (sweep line), bài toán tham lam (Greedy).
4. Lập trình thi đấu: hầu như mọi kỳ thi đều có các bài toán cần sắp xếp nhanh để giảm độ phức tạp từ O(n^2) xuống O(n \log n).