Sắp xếp vector trong C++ (Tăng dần)

Sắp xếp std::vector tăng dần (mặc định) dùng std::sort từ <algorithm>.

Cú pháp cơ bản

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {10, 9, 8, 6, 7, 2, 5, 1};
    sort(v.begin(), v.end()); // tăng dần (dùng operator<)
    for (int x : v) cout << x << ' '; // 1 2 5 6 7 8 9 10
    return 0;
}

Kết quả

Elements before sorting: 10 9 8 6 7 2 5 1
Elements after sorting: 1 2 5 6 7 8 9 10

Các biến thể

Cần	Code
Tăng dần (mặc định)	`sort(v.begin(), v.end());`
Giảm dần	`sort(v.begin(), v.end(), greater<>());`
Stable sort (giữ thứ tự bằng nhau)	`stable_sort(v.begin(), v.end());`
Sắp xếp một phần (top K)	`partial_sort(v.begin(), v.begin()+K, v.end());`
Nth element (median, partition)	`nth_element(v.begin(), v.begin()+mid, v.end());`
Custom comparator	`sort(v.begin(), v.end(), [](T a, T b){ return ...; });`

Độ phức tạp

sort: Introsort – O(N log N) trung bình, O(N log N) worst-case (chuyển sang heapsort khi recursion sâu).
stable_sort: Merge sort – O(N log² N) hoặc O(N log N) với buffer.
Không gian: O(log N) stack (sort), O(N) buffer (stable_sort).

Yêu cầu cho kiểu T

Phải có operator< (hoặc cung cấp comparator).
operator< phải thỏa mãn Strict Weak Ordering.
MoveConstructible, MoveAssignable (để swap trong sort).

Ví dụ struct

struct Item { int id; double price; };
vector<Item> items = {{1, 10.5}, {2, 5.0}, {3, 20.0}};
sort(items.begin(), items.end(),
     [](const Item& a, const Item& b) { return a.price < b.price; });
// Kết quả: id=2(5.0), id=1(10.5), id=3(20.0)

Mẹo hiệu năng

Tránh copy lớn: sort vector của unique_ptr<T> hoặc index vector.
Dữ liệu gần đã sắp xếp: stable_sort hoặc tim_sort (không có trong STL, dùng thư viện ngoài).
Số lượng nhỏ (N < 50): insertion_sort hand-written nhanh hơn.