Sắp xếp trong C++: std::sort, comparator và stable_sort

Sắp xếp cũng chỉ là một thuật toán

Ở trang trước bạn đã thấy thư viện chuẩn có sẵn các thuật toán dùng được với mọi dãy thông qua iterator. Sắp xếp là thuật toán bạn sẽ dùng nhiều nhất, và nó có trang riêng vì có vài chỗ hiểm: thứ tự tùy chỉnh, tính ổn định, và một quy tắc mà nếu phá vỡ, bạn sẽ nhận hành vi không xác định thay vì chỉ một kết quả sai.

Công cụ chủ lực là std::sort trong <algorithm>. Bạn đưa cho nó điểm đầu và điểm cuối của một dãy, và nó sắp xếp lại các phần tử ngay tại chỗ theo thứ tự tăng dần:

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

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end());   // ascending, in place

    for (int n : nums) cout << n << " ";  // 1 2 3 5 8 9
    cout << "\n";
    return 0;
}

Không có bản sao nào được tạo: chính vector được sắp xếp lại. Bên dưới, std::sort thường là introsort (quicksort chuyển sang heapsort khi cần), cho độ phức tạp trung bình O(n log n). Gần như lúc nào nó cũng nhanh hơn và ít lỗi hơn nhiều so với tự viết thuật toán sắp xếp.

Nó cũng dùng được với mảng C thông thường, bạn chỉ cần mô tả dãy bằng con trỏ:

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

int main() {
    int arr[] = {40, 10, 30, 20};
    int n = 4;

    sort(arr, arr + n);               // or sort(begin(arr), end(arr));

    for (int x : arr) cout << x << " ";  // 10 20 30 40
    return 0;
}

Thứ tự tùy chỉnh với comparator

Mặc định std::sort sắp xếp các phần tử bằng operator<. Để sắp xếp theo cách khác, hãy truyền đối số thứ ba: một comparator (hàm so sánh) nhận hai phần tử và trả về true nếu phần tử đầu phải đứng trước phần tử thứ hai.

Lambda là lựa chọn tự nhiên. Thứ tự giảm dần chỉ đơn giản là a > b:

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

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end(), [](int a, int b) {
        return a > b;   // "a before b" when a is larger -> descending
    });

    for (int n : nums) cout << n << " ";  // 9 8 5 3 2 1
    cout << "\n";
    return 0;
}

Với trường hợp phổ biến là sắp giảm dần các kiểu có sẵn, thư viện còn có sẵn một comparator là greater<T>() trong <functional>:

#include <functional>
sort(nums.begin(), nums.end(), greater<int>());  // same as a > b

Comparator cũng là cách để sắp xếp theo một thứ khác ngoài chính giá trị, ví dụ sắp xếp chuỗi theo độ dài thay vì theo bảng chữ cái:

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

int main() {
    vector<string> words = {"pear", "fig", "banana", "kiwi"};

    sort(words.begin(), words.end(), [](const string& a, const string& b) {
        return a.size() < b.size();   // shorter words first
    });

    for (const string& w : words) cout << w << " ";  // fig kiwi pear banana
    cout << "\n";
    return 0;
}

Hãy nhận tham số của comparator theo const& với mọi thứ lớn hơn vài byte (như string): sao chép mọi phần tử ở mỗi lần so sánh là lãng phí thuần túy.

Sắp xếp struct theo một trường

Trong chương trình thực tế, bạn thường sắp xếp tập hợp các struct theo một trường của chúng. Comparator chỉ cần lấy đúng trường bạn quan tâm. Ở đây ta sắp xếp mọi người theo tuổi, trẻ nhất trước:

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

struct Person {
    string name;
    int age;
};

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return a.age < b.age;
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    return 0;
}

Để ý rằng Linus và Dennis đều 25 tuổi. Ở đây chúng giữ nguyên thứ tự ban đầu, nhưng std::sort không đảm bảo điều đó. Nếu thứ tự tương đối của các phần tử bằng nhau là quan trọng, hãy dùng std::stable_sort, hàm giữ nguyên thứ tự đó (với chi phí hiệu năng nhỏ):

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

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    stable_sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) { return a.age < b.age; });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    // Linus stays before Dennis - their input order is preserved
    return 0;
}

Để chủ động phân định khi bằng nhau, chẳng hạn sắp theo tuổi rồi theo tên, hãy chỉ so sánh khóa phụ khi các khóa chính bằng nhau. std::tie giúp viết việc này gọn gàng:

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

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return tie(a.age, a.name) < tie(b.age, b.name);  // age, then name
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";  // Dennis & Linus 25, alphabetical
    return 0;
}

Cái bẫy strict weak ordering

Đây là lỗi nguy hiểm nhất khi sắp xếp trong C++, vì nó không cho bạn một kết quả sai mà cho bạn hành vi không xác định, thường là crash hoặc đọc ra ngoài phạm vi.

std::sort yêu cầu comparator định nghĩa một strict weak ordering. Quy tắc thực tế: comp(x, x) phải là false với mọi phần tử x. Nói cách khác, một phần tử không bao giờ đứng "trước" chính nó. Đó chính xác là điều < và > mang lại, và cũng chính xác là điều <= và >= phá vỡ:

// BUG: returns true when a == b, violating strict weak ordering.
sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b;   // undefined behavior - may crash on some inputs
});

Với <=, comparator khẳng định 5 đứng trước một 5 khác, điều này mâu thuẫn. Khi đó std::sort có thể đưa một con trỏ đi quá cuối dãy. Với đầu vào rất nhỏ đôi khi nó có vẻ vẫn chạy, và điều đó khiến bug này cực kỳ đáng sợ: nó có thể vượt qua test của bạn rồi crash trên production. Cách sửa chỉ đơn giản là <:

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

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

    sort(v.begin(), v.end(), [](int a, int b) {
        return a < b;   // correct: false when equal
    });

    for (int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}

Cái bẫy kinh điển thứ hai: sắp xếp làm mất hiệu lực mọi thứ trỏ vào dãy. Iterator, con trỏ và chỉ số bạn lưu trước khi sắp xếp sẽ không còn trỏ tới cùng phần tử logic nữa, vì các phần tử đã di chuyển. Hãy xác định lại mọi vị trí bạn cần sau khi sắp xếp, đừng bao giờ làm trước.

Sắp xếp một phần của dãy

Đôi khi bạn không cần sắp xếp toàn bộ, chỉ cần vài phần tử đứng đầu. Sắp xếp cả vector chỉ để đọc ba phần tử đầu là lãng phí. std::partial_sort chỉ sắp xếp những phần tử bạn yêu cầu và để phần còn lại theo thứ tự không xác định, nên tốn ít công hơn:

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

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};

    // Put the 3 smallest, in order, at the front. Rest is unspecified.
    partial_sort(v.begin(), v.begin() + 3, v.end());

    for (int i = 0; i < 3; i++) cout << v[i] << " ";  // 1 2 3
    cout << "\n";
    return 0;
}

Và nếu bạn chỉ cần một phần tử sẽ nằm ở một vị trí nhất định, như số trung vị, std::nth_element còn làm ít việc hơn nữa: nó đặt đúng phần tử vào chỉ số đó, mọi phần tử nhỏ hơn ở trước và mọi phần tử lớn hơn ở sau, tất cả với độ phức tạp trung bình O(n).

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

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};
    size_t mid = v.size() / 2;

    nth_element(v.begin(), v.begin() + mid, v.end());

    cout << "median is " << v[mid] << "\n";  // 5
    return 0;
}

Hãy dùng chúng khi "sắp xếp toàn bộ" là nhiều hơn mức bài toán thật sự cần: chúng tiết kiệm thời gian đáng kể với dữ liệu lớn.

Tiếp theo: template

Bạn có để ý rằng cùng một std::sort xử lý được int, string và cả struct Person của bạn, còn greater<int>() cũng dễ dàng thành greater<string>()? Sự tổng quát đó không phải phép màu: đó là template, cơ chế cho phép một đoạn code làm việc với bất kỳ kiểu nào mà nơi gọi đưa vào. Ở trang tiếp theo, chúng ta sẽ xem cách viết hàm và lớp template của riêng bạn, để code của bạn cũng không phụ thuộc vào kiểu như các thuật toán bạn đã dùng.