Bài 22.5: Bài tập thực hành tối ưu sắp xếp trong C++

Chào mừng các bạn trở lại với series blog của chúng ta về C++! Trong các bài trước, chúng ta có thể đã lướt qua hoặc sử dụng các kỹ thuật sắp xếp cơ bản. Tuy nhiên, việc sắp xếp dữ liệu là một tác vụ cực kỳ phổ biến và quan trọng trong lập trình. Nó không chỉ giúp dữ liệu dễ đọc, dễ tìm kiếm hơn mà còn là bước tiền xử lý cần thiết cho rất nhiều thuật toán khác.

Trong C++, chúng ta có một công cụ vô cùng mạnh mẽ và được tối ưu hóa cao để sắp xếp: các thuật toán trong Thư viện Chuẩn (Standard Library), đặc biệt là sort. Nhưng làm thế nào để sử dụng chúng một cách hiệu quả nhất? Bài viết này sẽ tập trung vào các bài tập thực hành và kỹ thuật tối ưu khi làm việc với sắp xếp trong C++, vượt ra ngoài việc chỉ đơn thuần gọi sort.

Chúng ta sẽ không đi sâu vào cách triển khai chi tiết của các thuật toán sắp xếp (như QuickSort, MergeSort, HeapSort), mà sẽ tập trung vào cách sử dụng các công cụ sẵn có trong C++ STL một cách thông minh và hiệu quả.

Công Cụ Sắp Xếp Cơ Bản: `sort`

Trái tim của việc sắp xếp trong C++ STL là hàm sort, được định nghĩa trong header <algorithm>. Hàm này thường được triển khai dựa trên Introsort, một thuật toán lai (hybrid) kết hợp QuickSort, HeapSort và InsertionSort để đảm bảo hiệu suất tốt trong hầu hết các trường hợp.

sort yêu cầu các iterator truy cập ngẫu nhiên (random-access iterators), điều này có nghĩa là nó hoạt động tốt với vector, deque, array, và mảng C-style thông thường.

Cú pháp cơ bản của sort: sort(first, last); hoặc sort(first, last, compare);

Trong đó:

first: Một iterator trỏ đến phần tử đầu tiên của dải cần sắp xếp.
last: Một iterator trỏ đến sau phần tử cuối cùng của dải cần sắp xếp (phần tử tại last không được bao gồm).
compare: (Tùy chọn) Một đối tượng hàm (function object), hàm, hoặc lambda để định nghĩa tiêu chí so sánh. Mặc định là less<> (sắp xếp tăng dần).

Hãy bắt đầu với một ví dụ đơn giản nhất về cách sử dụng sort:

#include <iostream>
#include <vector>
#include <algorithm> // Bao gồm sort

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

    // Sắp xếp vector theo thứ tự tăng dần
    sort(numbers.begin(), numbers.end());

    cout << "Vector sau khi sap xep (tang dan): ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl; // Output: 1 2 4 5 8 9

    return 0;
}

Giải thích:

Chúng ta khai báo một vector<int>.
sort(numbers.begin(), numbers.end()); gọi hàm sắp xếp cho toàn bộ dải từ numbers.begin() (phần tử đầu tiên) đến numbers.end() (sau phần tử cuối cùng).
Mặc định, sort sử dụng phép so sánh operator< hoặc less, nên nó sắp xếp tăng dần.

Tuỳ Chỉnh Tiêu Chí Sắp Xếp với `compare`

Một trong những khả năng mạnh mẽ của sort là khả năng tùy chỉnh tiêu chí sắp xếp bằng cách cung cấp đối số compare. Đối số này phải là một hàm hoặc đối tượng hàm có thể gọi được, nhận hai đối số cùng kiểu với các phần tử đang sắp xếp, và trả về bool. Kết quả true nghĩa là đối số thứ nhất được coi là "nhỏ hơn" hoặc "nên đứng trước" đối số thứ hai.

Sắp xếp Giảm Dần

Để sắp xếp giảm dần, chúng ta cần một hàm so sánh trả về true nếu phần tử thứ nhất lớn hơn phần tử thứ hai. C++ STL cung cấp sẵn greater<>.

#include <iostream>
#include <vector>
#include <algorithm> // sort
#include <functional> // greater

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

    // Sắp xếp vector theo thứ tự giảm dần sử dụng greater
    sort(numbers.begin(), numbers.end(), greater<int>());

    cout << "Vector sau khi sap xep (giam dan): ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl; // Output: 9 8 5 4 2 1

    return 0;
}

Giải thích:

Chúng ta truyền greater<int>() làm đối số thứ ba. greater<int>() là một đối tượng hàm mà khi được gọi với hai số nguyên a và b, nó trả về a > b. Điều này đảo ngược thứ tự so sánh, dẫn đến sắp xếp giảm dần.

Sắp xếp Đối Tượng Tùy Chỉnh

Đây là lúc compare thực sự thể hiện sức mạnh. Chúng ta thường cần sắp xếp các cấu trúc hoặc lớp dựa trên một hoặc nhiều thành viên của chúng. Lambda expression là một cách thanh lịch và tiện lợi để làm điều này ngay tại chỗ.

Giả sử chúng ta có một cấu trúc Person:

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

struct Person {
    string name;
    int age;
};

int main() {
    vector<Person> people = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 35},
        {"David", 25}
    };

    // Sắp xếp vector<Person> theo tuổi (tăng dần) sử dụng lambda
    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return a.age < b.age; // Trả về true nếu a.age nhỏ hơn b.age (sắp xếp tăng dần theo tuổi)
    });

    cout << "Danh sach sau khi sap xep theo tuoi (tang dan):" << endl;
    for (const auto& p : people) {
        cout << p.name << " (" << p.age << ") ";
    }
    cout << endl; // Output: Bob (25) David (25) Alice (30) Charlie (35)

    return 0;
}

Giải thích:

Chúng ta định nghĩa một cấu trúc Person.
Chúng ta sử dụng một lambda expression [](const Person& a, const Person& b) { return a.age < b.age; } làm hàm so sánh.
Lambda này nhận hai đối tượng Person (truyền bằng tham chiếu hằng để hiệu quả) và trả về true nếu tuổi của a nhỏ hơn tuổi của b. Điều này đảm bảo sort sắp xếp các đối tượng Person dựa trên thuộc tính age theo thứ tự tăng dần.

Bạn có thể thay đổi logic trong lambda để sắp xếp theo tên, theo tuổi giảm dần, hoặc theo nhiều tiêu chí (ví dụ: theo tuổi, nếu tuổi bằng nhau thì theo tên).

// Sắp xếp theo tuổi giảm dần
sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
    return a.age > b.age; // Trả về true nếu a.age lớn hơn b.age
});

// Sắp xếp theo tuổi tăng dần, nếu tuổi bằng nhau thì theo tên tăng dần
sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
    if (a.age != b.age) {
        return a.age < b.age; // Sắp xếp theo tuổi trước
    }
    return a.name < b.name; // Nếu tuổi bằng nhau, sắp xếp theo tên
});

Kỹ thuật này là cực kỳ quan trọng và được sử dụng rất thường xuyên trong thực tế. Việc nắm vững cách viết lambda so sánh giúp bạn sắp xếp hầu hết mọi cấu trúc dữ liệu tùy chỉnh.

Sắp Xếp Chỉ Một Phần Của Container

Đôi khi, chúng ta không cần sắp xếp toàn bộ container. sort cho phép bạn chỉ định một dải con (sub-range) bằng cách truyền các iterator đến điểm bắt đầu và điểm kết thúc của dải đó.

#include <iostream>
#include <vector>
#include <algorithm> // sort
#include <iterator> // advance

int main() {
    vector<int> numbers = {10, 20, 1, 8, 15, 5, 25, 12};

    // Sắp xếp chỉ 3 phần tử ở giữa
    // Dải cần sắp xếp: từ index 2 đến index 4 (tức là các số 1, 8, 15)
    // begin() + 2 trỏ đến 1
    // begin() + 5 trỏ đến 5 (là sau phần tử cuối cùng cần sắp xếp là 15)
    sort(numbers.begin() + 2, numbers.begin() + 5);

    cout << "Vector sau khi sap xep phan giua: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl; // Output: 10 20 1 8 15 5 25 12 -> sau sap xep: 10 20 1 8 15 5 25 12 -> *10 20 1 8 15* -> 10 20 *1 8 15* 5 25 12
    // Debug lại output
    // Ban đầu: {10, 20, 1, 8, 15, 5, 25, 12}
    // Dải cần sắp xếp: {1, 8, 15}
    // Sau khi sắp xếp dải: {1, 8, 15} -> {1, 8, 15} (đã theo thứ tự tăng dần)
    // Vector sau: {10, 20, *1, 8, 15*, 5, 25, 12} - thực ra không thay đổi trong trường hợp này!
    // Hãy thử một dải khác dễ thấy hơn
    vector<int> numbers2 = {10, 5, 20, 1, 15, 8, 25, 12};
    // Sắp xếp dải từ index 1 đến index 5 (các số 5, 20, 1, 15)
    // begin() + 1 trỏ đến 5
    // begin() + 5 trỏ đến 8 (là sau phần tử cuối cùng 15)
    sort(numbers2.begin() + 1, numbers2.begin() + 5);

    cout << "Vector 2 sau khi sap xep phan giua: ";
    for (int num : numbers2) {
        cout << num << " ";
    }
    cout << endl; // Output: 10 *1 5 15 20* 8 25 12

    return 0;
}

Giải thích:

Trong ví dụ thứ hai, chúng ta sử dụng numbers2.begin() + 1 và numbers2.begin() + 5 để xác định dải con.
begin() + 1 là iterator tới phần tử thứ hai (giá trị 5).
begin() + 5 là iterator tới phần tử thứ sáu (giá trị 8).
sort sẽ sắp xếp dải bao gồm các phần tử từ begin() + 1 đến trước begin() + 5, tức là các phần tử tại index 1, 2, 3, 4 (giá trị 5, 20, 1, 15). Dải này sau khi sắp xếp tăng dần sẽ là {1, 5, 15, 20}.
Kết quả là vector numbers2 trở thành {10, 1, 5, 15, 20, 8, 25, 12}. Kỹ thuật này rất hữu ích khi bạn chỉ cần sắp xếp một phần dữ liệu lớn mà không muốn tốn thời gian và tài nguyên cho toàn bộ tập dữ liệu.

Lưu Ý về Tính Ổn Định: `stable_sort`

sort thường không đảm bảo tính ổn định. Điều này có nghĩa là nếu có hai phần tử được coi là "bằng nhau" theo tiêu chí so sánh (!(a < b) và !(b < a)), thì thứ tự tương đối ban đầu của chúng có thể bị thay đổi sau khi sắp xếp.

Ví dụ với cấu trúc Person ở trên, nếu bạn sắp xếp theo tuổi, hai người cùng tuổi có thể đổi chỗ cho nhau. Nếu bạn cần giữ nguyên thứ tự ban đầu của các phần tử bằng nhau, bạn cần sử dụng stable_sort.

stable_sort đảm bảo tính ổn định, nhưng có thể kém hiệu quả hơn sort về thời gian chạy hoặc bộ nhớ trong một số trường hợp (thường là O(N log^2 N) hoặc O(N log N) với bộ nhớ phụ O(N)).

#include <iostream>
#include <vector>
#include <algorithm> // sort, stable_sort
#include <string>

struct Person {
    string name;
    int age;
    int original_order; // Thêm trường này để theo dõi thứ tự ban đầu
};

int main() {
    vector<Person> people = {
        {"Bob", 25, 0},    // Index 0
        {"David", 25, 1},  // Index 1
        {"Alice", 30, 2},  // Index 2
        {"Charlie", 35, 3} // Index 3
    };

    // Sắp xếp *không ổn định* theo tuổi
    vector<Person> people_sort = people;
    sort(people_sort.begin(), people_sort.end(), [](const Person& a, const Person& b) {
        return a.age < b.age;
    });

    cout << "sort (khong on dinh) theo tuoi:" << endl;
    for (const auto& p : people_sort) {
        cout << p.name << " (" << p.age << ", original: " << p.original_order << ") ";
    }
    cout << endl; // Output co the la: Bob (25, original: 0) David (25, original: 1) Alice (30, original: 2) Charlie (35, original: 3)
                            // HOẶC: David (25, original: 1) Bob (25, original: 0) Alice (30, original: 2) Charlie (35, original: 3)
                            // Thứ tự của Bob và David (cùng tuổi 25) có thể bị đảo ngược.

    cout << "--------------------" << endl;

    // Sắp xếp *ổn định* theo tuổi
    vector<Person> people_stable_sort = people;
    stable_sort(people_stable_sort.begin(), people_stable_sort.end(), [](const Person& a, const Person& b) {
        return a.age < b.age;
    });

    cout << "stable_sort (on dinh) theo tuoi:" << endl;
    for (const auto& p : people_stable_sort) {
        cout << p.name << " (" << p.age << ", original: " << p.original_order << ") ";
    }
    cout << endl; // Output LUÔN LUÔN là: Bob (25, original: 0) David (25, original: 1) Alice (30, original: 2) Charlie (35, original: 3)
                            // Thứ tự của Bob và David (cùng tuổi 25) được giữ nguyên như ban đầu.

    return 0;
}

Giải thích:

Chúng ta thêm trường original_order để dễ dàng nhận biết thứ tự ban đầu.
Khi sắp xếp bằng sort, thứ tự của "Bob" (original 0) và "David" (original 1) có thể hoán đổi vì cả hai đều có tuổi 25.
Khi sắp xếp bằng stable_sort, thứ tự của "Bob" và "David" luôn được giữ nguyên như trong vector gốc, bởi vì chúng được coi là bằng nhau theo tiêu chí so sánh (tuổi).

Sử dụng stable_sort khi: Thứ tự ban đầu của các phần tử bằng nhau là quan trọng đối với kết quả cuối cùng của bạn. Sử dụng sort khi: Tính ổn định không quan trọng, để có hiệu suất tiềm năng tốt hơn.

Tối Ưu Hóa cho Các Bài Toán "Top K" hoặc Phần Tử Thứ N

Một trong những sai lầm phổ biến khi đối mặt với bài toán "tìm K phần tử nhỏ nhất/lớn nhất" hoặc "tìm phần tử trung vị (median)" là sắp xếp toàn bộ tập dữ liệu rồi mới lấy K phần tử đầu tiên hoặc phần tử ở vị trí mong muốn. Điều này là không cần thiết và kém hiệu quả nếu K nhỏ hơn nhiều so với tổng số phần tử.

C++ STL cung cấp các thuật toán chuyên biệt cho các bài toán này, hiệu quả hơn nhiều so với việc sắp xếp toàn bộ: partial_sort và nth_element. Đây là những kỹ thuật tối ưu quan trọng cần biết.

Tìm K Phần Tử Nhỏ Nhất/Lớn Nhất: `partial_sort`

partial_sort(first, middle, last) sắp xếp các phần tử trong dải [first, last) sao cho các phần tử trong dải con [first, middle) được sắp xếp và là các phần tử nhỏ nhất trong toàn bộ dải [first, last). Các phần tử còn lại trong dải [middle, last) không được sắp xếp theo bất kỳ thứ tự cụ thể nào.

Thời gian chạy của partial_sort thường là O(N log K), trong đó N là tổng số phần tử và K là số phần tử bạn muốn sắp xếp ở đầu (middle - first). So với O(N log N) của sort khi N lớn hơn nhiều so với K, đây là một sự cải thiện đáng kể.

#include <iostream>
#include <vector>
#include <algorithm> // partial_sort
#include <functional> // greater

int main() {
    vector<int> numbers = {10, 5, 20, 1, 15, 8, 25, 12};
    int k = 3; // Muốn tìm 3 phần tử nhỏ nhất

    // Sử dụng partial_sort để tìm 3 phần tử nhỏ nhất
    // Sắp xếp 3 phần tử đầu tiên của vector
    partial_sort(numbers.begin(), numbers.begin() + k, numbers.end());

    cout << k << " phan tu nho nhat la: ";
    for (int i = 0; i < k; ++i) {
        cout << numbers[i] << " ";
    }
    cout << endl; // Output: 1 5 8

    // Vector numbers sau khi partial_sort: {1, 5, 8, 20, 15, 10, 25, 12}
    // (Lưu ý: các phần tử từ index k trở đi không được sắp xếp)
    cout << "Vector sau partial_sort: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    // Tìm 3 phần tử lớn nhất: sử dụng greater
    vector<int> numbers_large = {10, 5, 20, 1, 15, 8, 25, 12};
    partial_sort(numbers_large.begin(), numbers_large.begin() + k, numbers_large.end(), greater<int>());

    cout << k << " phan tu lon nhat la: ";
    for (int i = 0; i < k; ++i) {
        cout << numbers_large[i] << " ";
    }
    cout << endl; // Output: 25 20 15

    return 0;
}

Giải thích:

partial_sort(numbers.begin(), numbers.begin() + k, numbers.end());
- first: numbers.begin()
- middle: numbers.begin() + k (iterator đến vị trí sau phần tử thứ k - tức là index k)
- last: numbers.end()
Hàm đảm bảo 3 phần tử đầu tiên của vector (numbers[0], numbers[1], numbers[2]) sẽ là 3 phần tử nhỏ nhất trong toàn bộ vector và chúng được sắp xếp tăng dần.

Tìm Phần Tử Thứ N: `nth_element`

nth_element(first, nth, last) sắp xếp các phần tử trong dải [first, last) sao cho phần tử tại vị trí nth (iterator nth) là phần tử mà nó sẽ đứng ở vị trí đó nếu toàn bộ dải được sắp xếp. Ngoài ra, tất cả các phần tử trước vị trí nth đều nhỏ hơn hoặc bằng phần tử tại nth, và tất cả các phần tử sau vị trí nth đều lớn hơn hoặc bằng phần tử tại nth.

Điểm mấu chốt là nth_element chỉ đảm bảo vị trí của phần tử tại nth và phân vùng các phần tử còn lại tương ứng; các phần tử trước nth không nhất thiết phải được sắp xếp với nhau, và các phần tử sau nth cũng vậy.

Lợi ích cực lớn của nth_element là hiệu suất trung bình của nó là tuyến tính, O(N), trong đó N là số phần tử. Điều này làm cho nó trở thành công cụ tối ưu nhất để tìm trung vị, tứ phân vị, hoặc bất kỳ phần tử thứ k nào mà không cần sắp xếp toàn bộ dữ liệu.

#include <iostream>
#include <vector>
#include <algorithm> // nth_element

int main() {
    vector<int> numbers = {10, 5, 20, 1, 15, 8, 25, 12};
    int n = 4; // Muốn tìm phần tử thứ 4 (index 3 nếu sắp xếp tăng dần)

    // Tìm phần tử sẽ ở vị trí index n-1 = 3 nếu vector được sắp xếp
    // Tức là phần tử nhỏ thứ 4
    nth_element(numbers.begin(), numbers.begin() + n - 1, numbers.end());

    cout << "Phan tu nho thu " << n << " la: " << numbers[n - 1] << endl; // Output: Phan tu nho thu 4 la: 8

    // Vector numbers sau khi nth_element: {5, 1, 8, 10, 15, 20, 25, 12}
    // (Các phần tử trước 8 <= 8, các phần tử sau 8 >= 8, nhưng không được sắp xếp nội bộ)
    cout << "Vector sau nth_element: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl; // Output: có thể là 5 1 8 10 15 20 25 12 HOẶC 1 5 8 10 15 20 25 12 (thứ tự trước và sau 8 không cố định)

    // Tìm phần tử lớn thứ 3 (tức là phần tử sẽ ở vị trí numbers.size() - 3 nếu sắp xếp tăng dần)
    vector<int> numbers_large = {10, 5, 20, 1, 15, 8, 25, 12};
    int k_largest = 3; // Muốn tìm phần tử lớn thứ 3
    int nth_pos = numbers_large.size() - k_largest; // Vị trí index nếu sắp xếp tăng dần

    nth_element(numbers_large.begin(), numbers_large.begin() + nth_pos, numbers_large.end());

    cout << "Phan tu lon thu " << k_largest << " la: " << numbers_large[nth_pos] << endl; // Output: Phan tu lon thu 3 la: 15

    return 0;
}

Giải thích:

Để tìm phần tử nhỏ thứ N, chúng ta gọi nth_element với nth là numbers.begin() + N - 1.
Để tìm phần tử lớn thứ K, chúng ta gọi nth_element với nth là numbers.begin() + (numbers.size() - K).
nth_element là lựa chọn tối ưu khi bạn chỉ cần biết giá trị của phần tử thứ K (ví dụ: trung vị) mà không cần toàn bộ danh sách được sắp xếp.

Comments

There are no comments at the moment.