Bài 22.4: Bài tập thực hành sắp xếp nâng cao trong C++

Chào mừng trở lại với chuỗi bài học C++! Chúng ta đã đi qua những khái niệm cơ bản về sắp xếp. Bây giờ là lúc để nâng tầm kỹ năng của mình bằng cách thực hành các kỹ thuật sắp xếp nâng cao hơn, đặc biệt là cách sử dụng hiệu quả thư viện chuẩn (STL) của C++ để giải quyết các bài toán thực tế phức tạp.

Khi nói đến sắp xếp trong C++, công cụ mạnh mẽ nhất bạn cần nắm vững không gì khác chính là các hàm trong <algorithm>, đặc biệt là sort. Mặc dù bạn có thể tự cài đặt các thuật toán sắp xếp cơ bản như Bubble Sort hay Selection Sort để hiểu nguyên lý, trong thực tế, sort và các biến thể của nó là lựa chọn hàng đầu vì chúng được tối ưu hóa rất cao về hiệu suất.

Bài tập thực hành hôm nay sẽ giúp bạn làm quen với:

  1. Sử dụng sort với custom comparator để sắp xếp các kiểu dữ liệu phức tạp (như struct hoặc class).
  2. Hiểu và sử dụng partial_sort khi chỉ cần sắp xếp một phần của dãy.
  3. Hiểu và sử dụng nth_element để tìm phần tử thứ k hiệu quả.
  4. Tìm hiểu về stable_sort và khi nào cần dùng nó.

Hãy cùng bắt tay vào thực hành!

1. sort với Custom Comparator

sort là một hàm cực kỳ linh hoạt. Ngoài việc sắp xếp các kiểu dữ liệu cơ bản theo thứ tự mặc định (tăng dần), nó cho phép bạn định nghĩa luật sắp xếp riêng thông qua một đối số thứ ba: hàm so sánh (comparison function). Hàm so sánh này nhận hai phần tử cùng kiểu và trả về true nếu phần tử thứ nhất được coi là "nhỏ hơn" phần tử thứ hai theo tiêu chí của bạn, và false ngược lại.

Hàm so sánh này thường được cài đặt dưới dạng lambda expression hoặc một struct/class với toán tử () được nạp chồng (overloaded operator()).

Ví dụ 1: Sắp xếp struct theo một tiêu chí

Giả sử chúng ta có một danh sách các sinh viên, mỗi sinh viên có tên và điểm. Chúng ta muốn sắp xếp danh sách này theo điểm từ thấp đến cao.

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

struct SinhVien {
    string t;
    double d;
};

int main() {
    vector<SinhVien> ds = {
        {"Alice", 8.5},
        {"Bob", 7.2},
        {"Charlie", 9.0},
        {"David", 8.5}
    };

    sort(ds.begin(), ds.end(),
              [](const SinhVien& a, const SinhVien& b) {
                  return a.d < b.d;
              });

    cout << "Danh sach sinh vien sau khi sap xep theo diem tang dan:\n";
    for (const auto& x : ds) {
        cout << x.t << " - " << x.d << "\n";
    }

    return 0;
}

Danh sach sinh vien sau khi sap xep theo diem tang dan:
Bob - 7.2
Alice - 8.5
David - 8.5
Charlie - 9

Giải thích code:

  • Chúng ta khai báo struct SinhVien với hai trường t và d.
  • Tạo một vector chứa các đối tượng SinhVien.
  • Gọi sort. Đối số đầu tiên (ds.begin()) và thứ hai (ds.end()) xác định phạm vi cần sắp xếp (từ đầu đến cuối vector).
  • Đối số thứ ba là một lambda expression [](const SinhVien& a, const SinhVien& b) { return a.d < b.d; }. Đây chính là custom comparator. Lambda này nhận hai đối tượng SinhVien (đặt tên là a và b - truyền bằng tham chiếu const để hiệu quả) và trả về true nếu a.d nhỏ hơn b.d. sort sử dụng luật này để xác định thứ tự các phần tử.

Ví dụ 2: Sắp xếp struct theo nhiều tiêu chí

Bây giờ, giả sử chúng ta muốn sắp xếp theo điểm giảm dần, nhưng nếu hai sinh viên có cùng điểm thì sắp xếp theo tên tăng dần.

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

struct SinhVien {
    string t;
    double d;
};

int main() {
    vector<SinhVien> ds = {
        {"Alice", 8.5},
        {"Bob", 7.2},
        {"Charlie", 9.0},
        {"David", 8.5},
        {"Anna", 8.5}
    };

    sort(ds.begin(), ds.end(),
              [](const SinhVien& a, const SinhVien& b) {
                  if (a.d != b.d) {
                      return a.d > b.d;
                  } else {
                      return a.t < b.t;
                  }
              });

    cout << "\nDanh sach sinh vien sau khi sap xep theo diem giam dan, ten tang dan:\n";
    for (const auto& x : ds) {
        cout << x.t << " - " << x.d << "\n";
    }

    return 0;
}

Danh sach sinh vien sau khi sap xep theo diem giam dan, ten tang dan:
Charlie - 9
Anna - 8.5
Alice - 8.5
David - 8.5
Bob - 7.2

Giải thích code:

  • Comparator bây giờ phức tạp hơn một chút. Nó kiểm tra xem điểm của a và b có khác nhau không.
  • Nếu điểm khác nhau, nó trả về a.d > b.d (true nếu điểm của a lớn hơn b.d), thực hiện sắp xếp giảm dần theo điểm.
  • Nếu điểm bằng nhau (a.d == b.d), nó mới so sánh tên bằng a.t < b.t, thực hiện sắp xếp tăng dần theo tên.

Đây là cách mạnh mẽ để áp dụng sort cho các tình huống sắp xếp tùy chỉnh.

2. partial_sort - Sắp xếp Chỉ Một Phần Đầu

Đôi khi, bạn không cần sắp xếp toàn bộ dãy, mà chỉ cần tìm và sắp xếp k phần tử nhỏ nhất (hoặc lớn nhất) trong dãy. Việc sắp xếp toàn bộ dãy là không cần thiết và tốn kém. Lúc này, partial_sort là cứu cánh.

Hàm partial_sort(first, middle, last, comp) sắp xếp các phần tử trong phạm vi [first, middle). Sau khi hàm thực thi, các phần tử trong [first, middle) sẽ là k phần tử nhỏ nhất trong toàn bộ phạm vi [first, last), và chúng đã được sắp xếp. Các phần tử còn lại trong [middle, last) không được đảm bảo về thứ tự, nhưng chúng đều lớn hơn hoặc bằng bất kỳ phần tử nào trong [first, middle).

Ví dụ 3: Tìm 3 số nhỏ nhất và sắp xếp chúng

Giả sử bạn có một dãy số ngẫu nhiên và chỉ cần tìm 3 số nhỏ nhất và biết thứ tự của chúng.

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <ctime>

int main() {
    vector<int> so(10);
    mt19937 rd(static_cast<unsigned int>(time(0)));
    uniform_int_distribution<int> pb(1, 100);
    for(int& x : so) {
        x = pb(rd);
    }

    cout << "Day so ban dau: ";
    for (int x : so) {
        cout << x << " ";
    }
    cout << "\n";

    int k = 3;
    if (k > so.size()) {
        k = so.size();
    }

    partial_sort(so.begin(), so.begin() + k, so.end());

    cout << "Cac so nho nhat (va da sap xep): ";
    for (int i = 0; i < k; ++i) {
        cout << so[i] << " ";
    }
    cout << "\n";

    return 0;
}

Day so ban dau: 76 9 92 63 11 86 6 29 45 35 
Cac so nho nhat (va da sap xep): 6 9 11

Giải thích code:

  • Chúng ta tạo một vector 10 số ngẫu nhiên.
  • Đặt k = 3. Chúng ta muốn 3 số nhỏ nhất.
  • Gọi partial_sort với các iterator so.begin(), so.begin() + k, và so.end().
  • Sau khi gọi hàm, 3 phần tử đầu tiên của vector (so[0], so[1], so[2]) sẽ chứa 3 số nhỏ nhất từ dãy ban đầu và chúng đã được sắp xếp theo thứ tự tăng dần.
  • Các phần tử còn lại (so[3] đến so[9]) có giá trị lớn hơn hoặc bằng bất kỳ số nào trong 3 số đầu tiên, nhưng thứ tự của chúng không được đảm bảo.

partial_sort hiệu quả hơn sort khi k nhỏ hơn đáng kể so với tổng số phần tử.

3. nth_element - Tìm Phần Tử Thứ K

nth_element thậm chí còn hiệu quả hơn partial_sort khi bạn chỉ cần tìm ra phần tử đúng ở vị trí thứ k nếu dãy được sắp xếp, mà không cần quan tâm đến việc các phần tử trước hoặc sau vị trí k có được sắp xếp hay không.

Hàm nth_element(first, nth, last, comp) sẽ đặt phần tử mà lẽ ra đứng ở vị trí nth nếu toàn bộ dãy [first, last) được sắp xếp vào đúng vị trí nth. Đồng thời, nó đảm bảo rằng tất cả các phần tử trong phạm vi [first, nth) đều nhỏ hơn hoặc bằng phần tử tại nth, và tất cả các phần tử trong phạm vi [nth, last) đều lớn hơn hoặc bằng phần tử tại nth.

Ứng dụng phổ biến nhất của nth_element là tìm median (phần tử trung vị) của một tập dữ liệu, hoặc tìm k phần tử nhỏ nhất/lớn nhất (nhưng không cần sắp xếp chúng).

Ví dụ 4: Tìm phần tử trung vị (Median)

Đối với một tập hợp có số phần tử lẻ, median là phần tử ở vị trí chính giữa sau khi sắp xếp. Đối với tập hợp có số phần tử chẵn, median thường được tính là trung bình của hai phần tử ở giữa. nth_element giúp tìm phần tử ở vị trí cần thiết một cách hiệu quả (độ phức tạp trung bình là O(N)).

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <ctime>

int main() {
    vector<int> so = {9, 1, 8, 2, 7, 3, 6, 4, 5, 10, 0};

    cout << "Day so ban dau: ";
    for (int x : so) {
        cout << x << " ";
    }
    cout << "\n";

    size_t k = so.size() / 2;

    nth_element(so.begin(),
                     so.begin() + k,
                     so.end());

    cout << "Phan tu tai vi tri median (" << k << ") la: " << so[k] << "\n";

    cout << "Day so sau nth_element (khong hoan toan sap xep): ";
    for (int x : so) {
        cout << x << " ";
    }
    cout << "\n";

    return 0;
}

Day so ban dau: 9 1 8 2 7 3 6 4 5 10 0 
Phan tu tai vi tri median (5) la: 5
Day so sau nth_element (khong hoan toan sap xep): 0 1 2 3 4 5 7 8 9 10 6

Giải thích code:

  • Chúng ta có một vector 11 phần tử.
  • Vị trí của median (nếu sắp xếp tăng dần) là ở index 5 (vì 11 / 2 = 5 trong phép chia số nguyên).
  • Gọi nth_element với so.begin() + k là iterator thứ hai.
  • Sau khi thực thi, phần tử tại so[k] (index 5) sẽ chính là median của dãy số ban đầu.
  • Các phần tử từ so[0] đến so[4] đều nhỏ hơn hoặc bằng so[5].
  • Các phần tử từ so[6] đến so[10] đều lớn hơn hoặc bằng so[5].
  • Tuy nhiên, các phần tử trong phạm vi [0, 4] không được sắp xếp với nhau, tương tự với phạm vi [6, 10].

nth_element có độ phức tạp trung bình là tuyến tính (O(N)), trong khi sort là O(N log N) và partial_sort là O(N log K). Do đó, khi bạn chỉ cần tìm phần tử thứ k hoặc phân hoạch dãy xung quanh nó, nth_element là lựa chọn hiệu quả nhất.

4. stable_sort - Sắp xếp Ổn Định

Trong một số trường hợp, khi bạn sắp xếp một tập dữ liệu có các phần tử "bằng nhau" theo tiêu chí so sánh, bạn có thể muốn giữ nguyên thứ tự ban đầu của các phần tử bằng nhau đó. Đây gọi là sắp xếp ổn định (stable sort).

sort thông thường không đảm bảo tính ổn định. Nếu bạn cần điều này, hãy sử dụng stable_sort.

Hàm stable_sort(first, last, comp) thực hiện sắp xếp toàn bộ dãy [first, last) và đảm bảo rằng nếu hai phần tử a và b được coi là bằng nhau theo hàm so sánh (!comp(a, b) && !comp(b, a)), thì thứ tự tương đối của chúng trong dãy kết quả sẽ giống với thứ tự tương đối của chúng trong dãy ban đầu.

Ví dụ 5: Minh họa sự khác biệt giữa sort và stable_sort

Giả sử chúng ta có danh sách các cặp số (value, original_index). Chúng ta muốn sắp xếp danh sách này theo value. Nếu có hai cặp có cùng value, chúng ta muốn cặp nào xuất hiện trước trong danh sách ban đầu thì vẫn xuất hiện trước sau khi sắp xếp.

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

int main() {
    vector<pair<int, int>> dl = {
        {5, 0}, {3, 1}, {5, 2}, {1, 3}, {3, 4}, {4, 5}
    };

    cout << "Du lieu ban dau: ";
    for (const auto& x : dl) {
        cout << "(" << x.first << "," << x.second << ") ";
    }
    cout << "\n";

    vector<pair<int, int>> dl_s = dl;
    sort(dl_s.begin(), dl_s.end(),
              [](const pair<int, int>& a, const pair<int, int>& b) {
                  return a.first < b.first;
              });

    cout << "Ket qua sau sort (khong dam bao on dinh): ";
    for (const auto& x : dl_s) {
        cout << "(" << x.first << "," << x.second << ") ";
    }
    cout << "\n";

    vector<pair<int, int>> dl_ss = dl;
    stable_sort(dl_ss.begin(), dl_ss.end(),
                     [](const pair<int, int>& a, const pair<int, int>& b) {
                         return a.first < b.first;
                     });

    cout << "Ket qua sau stable_sort (dam bao on dinh): ";
    for (const auto& x : dl_ss) {
        cout << "(" << x.first << "," << x.second << ") ";
    }
    cout << "\n";

    return 0;
}

Du lieu ban dau: (5,0) (3,1) (5,2) (1,3) (3,4) (4,5) 
Ket qua sau sort (khong dam bao on dinh): (1,3) (3,1) (3,4) (4,5) (5,0) (5,2) 
Ket qua sau stable_sort (dam bao on dinh): (1,3) (3,1) (3,4) (4,5) (5,0) (5,2)

Giải thích code:

  • Chúng ta có vector các cặp (value, original_index).
  • Chúng ta sắp xếp hai bản sao của vector này bằng sort và stable_sort, cùng sử dụng custom comparator để sắp xếp theo value.
  • Đối với stable_sort, các cặp có cùng value sẽ giữ nguyên thứ tự ban đầu của chúng. Ví dụ, trong dữ liệu gốc (5, 0) đứng trước (5, 2), và (3, 1) đứng trước (3, 4). Sau khi stable_sort, thứ tự này vẫn được duy trì.
  • Đối với sort, thứ tự tương đối của các cặp có cùng value có thể bị đảo lộn tùy thuộc vào cài đặt cụ thể của thư viện.

Lưu ý rằng stable_sort thường có chi phí hiệu năng (thời gian và/hoặc bộ nhớ) cao hơn so với sort vì nó cần thực hiện công việc bổ sung để duy trì tính ổn định. Chỉ sử dụng nó khi tính ổn định là một yêu cầu cần thiết của bài toán.

Comments

There are no comments at the moment.