Sắp xếp vector giảm dần (Descending) trong C++

Sắp xếp std::vector giảm dần dùng std::sort với comparator std::greater<> (C++14) hoặc lambda.

Cách 1: std::greater<> (C++14 transparent comparator)

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional> // greater
using namespace std;

int main() {
    vector<int> v = {10, 9, 8, 6, 7, 2, 5, 1};
    sort(v.begin(), v.end(), greater<>()); // C++14: greater<>() tự suy diễn kiểu
    for (int x : v) cout << x << ' '; // 10 9 8 7 6 5 2 1
    return 0;
}

Cách 2: Lambda (C++11)

sort(v.begin(), v.end(), [](int a, int b) { return a > b; });

Cách 3: Hàm so sánh riêng

bool desc(int a, int b) { return a > b; }
sort(v.begin(), v.end(), desc);

Cách 4: Sắp xếp tăng dần rồi reverse

sort(v.begin(), v.end()); // tăng dần
reverse(v.begin(), v.end()); // O(N)

Độ phức tạp

• sort: O(N log N) trung bình, O(N²) worst-case (Introsort – hybrid quicksort/heapsort/insertion sort).
• stable_sort: O(N log² N) – giữ thứ tự tương đối phần tử bằng nhau.
• greater<> không tốn overhead so với lambda (inline được).

Ví dụ với struct

struct Student { string name; int score; };
vector<Student> students = {{"A", 80}, {"B", 90}, {"C", 70}};

// Giảm dần theo score
sort(students.begin(), students.end(),
     [](const Student& a, const Student& b) { return a.score > b.score; });
// Kết quả: B(90), A(80), C(70)

Lưu ý

• greater<T> (C++11) yêu cầu chỉ định kiểu: greater<int>(). greater<> (C++14) transparent – tự suy diễn.
• Đối với kiểu không hỗ trợ > (ví dụ custom class) – phải cung cấp lambda/func.
• Sắp xếp vector của pointer: sort(v.begin(), v.end(), [](T* a, T* b){ return *a > *b; });.