🔢 Sorting & Custom Comparators

std::sort là một trong những algorithms hay dùng nhất. Học cách custom sorting cho mọi use case.

Basic Sorting

cpp

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {5, 2, 8, 1, 9, 3};
    
    // Sort ascending (default)
    std::sort(v.begin(), v.end());
    // [1, 2, 3, 5, 8, 9]
    
    // Sort descending với std::greater
    std::sort(v.begin(), v.end(), std::greater<int>());
    // [9, 8, 5, 3, 2, 1]
    
    // Sort descending với lambda
    std::sort(v.begin(), v.end(), [](int a, int b) {
        return a > b;
    });
    
    return 0;
}

Comparator Rules

Comparator phải trả về true nếu a nên đứng trước b:

cpp

// Ascending: a trước b nếu a < b
auto ascending = [](int a, int b) { return a < b; };

// Descending: a trước b nếu a > b  
auto descending = [](int a, int b) { return a > b; };

// ⚠️ QUAN TRỌNG: Comparator phải là "strict weak ordering"
// - comp(a, a) phải = false
// - Nếu comp(a, b), thì !comp(b, a)
// - Transitive: comp(a,b) && comp(b,c) → comp(a,c)

// ❌ SAI: dùng <= gây crash!
auto bad = [](int a, int b) { return a <= b; };  // DON'T!

Sorting Objects

Với operator<

cpp

struct Person {
    std::string name;
    int age;
    
    // Define operator< cho sort mặc định
    bool operator<(const Person& other) const {
        return age < other.age;  // Sort by age
    }
};

std::vector<Person> people = {
    {"Alice", 30},
    {"Bob", 25},
    {"Charlie", 35}
};

std::sort(people.begin(), people.end());
// Sorted by age: Bob(25), Alice(30), Charlie(35)

Với Lambda Comparator

cpp

std::vector<Person> people = {
    {"Alice", 30},
    {"Bob", 25},
    {"Charlie", 35}
};

// Sort by name
std::sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
    return a.name < b.name;
});
// Charlie, Alice, Bob → Alice, Bob, Charlie

// Sort by age descending
std::sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
    return a.age > b.age;
});
// Charlie(35), Alice(30), Bob(25)

Multi-field Sorting

cpp

struct Employee {
    std::string department;
    std::string name;
    int salary;
};

std::vector<Employee> employees = {
    {"HR", "Alice", 5000},
    {"IT", "Bob", 6000},
    {"HR", "Charlie", 5500},
    {"IT", "David", 5500}
};

// Sort: department ASC, then salary DESC
std::sort(employees.begin(), employees.end(), 
    [](const Employee& a, const Employee& b) {
        if (a.department != b.department) {
            return a.department < b.department;  // Primary: dept ASC
        }
        return a.salary > b.salary;  // Secondary: salary DESC
    }
);
// HR: Charlie(5500), Alice(5000)
// IT: Bob(6000), David(5500)

Partial Sort

cpp

std::vector<int> v = {5, 2, 8, 1, 9, 3, 7, 4, 6};

// Chỉ sort 3 phần tử nhỏ nhất (đặt ở đầu)
std::partial_sort(v.begin(), v.begin() + 3, v.end());
// [1, 2, 3, ...rest unsorted]

// nth_element: đặt phần tử thứ n đúng vị trí
std::nth_element(v.begin(), v.begin() + 4, v.end());
// Phần tử thứ 4 (index 4) đúng vị trí
// Tất cả trước nó <= nó, tất cả sau >= nó

Stable Sort

cpp

struct Item {
    int priority;
    std::string name;
};

std::vector<Item> items = {
    {1, "A"},
    {2, "B"},
    {1, "C"},
    {2, "D"}
};

// stable_sort: giữ relative order của equal elements
std::stable_sort(items.begin(), items.end(), 
    [](const Item& a, const Item& b) {
        return a.priority < b.priority;
    }
);
// {1, "A"}, {1, "C"}, {2, "B"}, {2, "D"}
// A vẫn trước C trong priority 1
// B vẫn trước D trong priority 2

// std::sort có thể đảo order của equal elements!

is_sorted và is_sorted_until

cpp

std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {1, 3, 2, 4, 5};

bool sorted1 = std::is_sorted(v1.begin(), v1.end());  // true
bool sorted2 = std::is_sorted(v2.begin(), v2.end());  // false

// Tìm điểm bắt đầu unsorted
auto it = std::is_sorted_until(v2.begin(), v2.end());
// it points to 2 (first out-of-order element)

Sorting with Custom Type (Full Example)

cpp

#include <algorithm>
#include <vector>
#include <iostream>
#include <string>

struct Product {
    std::string name;
    double price;
    int rating;  // 1-5 stars
    
    void print() const {
        std::cout << name << " - $" << price 
                  << " (" << rating << " stars)" << std::endl;
    }
};

int main() {
    std::vector<Product> products = {
        {"Laptop", 999.99, 4},
        {"Phone", 699.99, 5},
        {"Tablet", 499.99, 4},
        {"Watch", 299.99, 3},
        {"Earbuds", 149.99, 5},
    };
    
    // Sort by price (cheap first)
    std::sort(products.begin(), products.end(), 
        [](const Product& a, const Product& b) {
            return a.price < b.price;
        });
    
    std::cout << "=== By Price ===" << std::endl;
    for (const auto& p : products) p.print();
    
    // Sort by rating DESC, then price ASC
    std::sort(products.begin(), products.end(), 
        [](const Product& a, const Product& b) {
            if (a.rating != b.rating) {
                return a.rating > b.rating;  // Higher rating first
            }
            return a.price < b.price;  // Cheaper first if same rating
        });
    
    std::cout << "\n=== By Rating (then Price) ===" << std::endl;
    for (const auto& p : products) p.print();
    
    return 0;
}

Output:

=== By Price ===
Earbuds - $149.99 (5 stars)
Watch - $299.99 (3 stars)
Tablet - $499.99 (4 stars)
Phone - $699.99 (5 stars)
Laptop - $999.99 (4 stars)

=== By Rating (then Price) ===
Earbuds - $149.99 (5 stars)
Phone - $699.99 (5 stars)
Tablet - $499.99 (4 stars)
Laptop - $999.99 (4 stars)
Watch - $299.99 (3 stars)

Performance

Algorithm	Average	Best	Worst	Stable
`std::sort`	O(n log n)	O(n log n)	O(n log n)	❌
`std::stable_sort`	O(n log n)	O(n log n)	O(n log² n)*	✅
`std::partial_sort`	O(n log k)	-	-	❌
`std::nth_element`	O(n)	O(n)	O(n²)**	❌

* Với extra memory, nếu không thì O(n log² n)
** Worst case hiếm gặp với modern implementations

📚 Tổng kết

Concept	Key Takeaway
`std::sort`	Introsort — fast, not stable
`std::stable_sort`	Giữ relative order
Comparator	`return a < b` cho ascending
Strict weak ordering	Không dùng `<=`
Multi-field	Check primary first, then secondary
`partial_sort`	Khi chỉ cần top K

➡️ Tiếp theo

Tiếp theo: Searching — find và binary_search.

🔢 Sorting & Custom Comparators ​

Basic Sorting ​

Comparator Rules ​

Sorting Objects ​

Với operator< ​

Với Lambda Comparator ​

Multi-field Sorting ​

Partial Sort ​

Stable Sort ​

is_sorted và is_sorted_until ​

Sorting with Custom Type (Full Example) ​

Performance ​

📚 Tổng kết ​

➡️ Tiếp theo ​