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> // Bao gồm sort

// Định nghĩa struct SinhVien
struct SinhVien {
    string ten;
    double diem;
};

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

    // Sắp xếp danh sách theo điểm từ thấp đến cao
    // Sử dụng lambda expression làm custom comparator
    sort(danhSach.begin(), danhSach.end(),
              [](const SinhVien& a, const SinhVien& b) {
                  return a.diem < b.diem; // 'a' nhỏ hơn 'b' nếu điểm của 'a' nhỏ hơn điểm của 'b'
              });

    // In kết quả sau khi sắp xếp
    cout << "Danh sach sinh vien sau khi sap xep theo diem tang dan:" << endl;
    for (const auto& sv : danhSach) {
        cout << sv.ten << " - " << sv.diem << endl;
    }

    return 0;
}

Giải thích code:

  • Chúng ta khai báo struct SinhVien với hai trường ten và diem.
  • Tạo một vector chứa các đối tượng SinhVien.
  • Gọi sort. Đối số đầu tiên (danhSach.begin()) và thứ hai (danhSach.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.diem < b.diem; }. Đâ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.diem nhỏ hơn b.diem. 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 ten;
    double diem;
};

int main() {
    vector<SinhVien> danhSach = {
        {"Alice", 8.5},
        {"Bob", 7.2},
        {"Charlie", 9.0},
        {"David", 8.5},
        {"Anna", 8.5} // Thêm một người nữa có cùng điểm 8.5
    };

    // Sắp xếp theo điểm giảm dần, sau đó theo tên tăng dần nếu điểm bằng nhau
    sort(danhSach.begin(), danhSach.end(),
              [](const SinhVien& a, const SinhVien& b) {
                  if (a.diem != b.diem) {
                      return a.diem > b.diem; // Sắp xếp điểm giảm dần
                  } else {
                      return a.ten < b.ten; // Nếu điểm bằng nhau, sắp xếp tên tăng dần
                  }
              });

    // In kết quả
    cout << "\nDanh sach sinh vien sau khi sap xep theo diem giam dan, ten tang dan:" << endl;
    for (const auto& sv : danhSach) {
        cout << sv.ten << " - " << sv.diem << endl;
    }

    return 0;
}

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.diem > b.diem (true nếu điểm của a lớn hơn b.diem), thực hiện sắp xếp giảm dần theo điểm.
  • Nếu điểm bằng nhau (a.diem == b.diem), nó mới so sánh tên bằng a.ten < b.ten, 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> // Để tạo số ngẫu nhiên
#include <ctime>  // Để seed cho random

int main() {
    vector<int> numbers(10);
    // Khởi tạo vector với các số ngẫu nhiên
    mt19937 rng(static_cast<unsigned int>(time(0)));
    uniform_int_distribution<int> dist(1, 100);
    for(int& n : numbers) {
        n = dist(rng);
    }

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

    // Chúng ta muốn tìm và sắp xếp 3 số nhỏ nhất
    int k = 3;

    // Kiểm tra k có hợp lệ không
    if (k > numbers.size()) {
        k = numbers.size();
    }

    // Sử dụng partial_sort
    // Phạm vi sắp xếp là [numbers.begin(), numbers.begin() + k)
    partial_sort(numbers.begin(), numbers.begin() + k, numbers.end());

    cout << "Cac so nho nhat (va da sap xep): ";
    // Chỉ in ra k phần tử đầu tiên
    for (int i = 0; i < k; ++i) {
        cout << numbers[i] << " ";
    }
    cout << endl;

    // Các phần tử còn lại (từ index k trở đi) không được đảm bảo thứ tự,
    // nhưng chúng đều >= bất kỳ phần tử nào trong k phần tử đầu tiên.
    // cout << "Phan con lai (khong dam bao thu tu): ";
    // for (size_t i = k; i < numbers.size(); ++i) {
    //     cout << numbers[i] << " ";
    // }
    // cout << endl;

    return 0;
}

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 numbers.begin(), numbers.begin() + k, và numbers.end().
  • Sau khi gọi hàm, 3 phần tử đầu tiên của vector (numbers[0], numbers[1], numbers[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 (numbers[3] đến numbers[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> numbers = {9, 1, 8, 2, 7, 3, 6, 4, 5, 10, 0}; // 11 phần tử

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

    // Vị trí của phần tử trung vị (median) trong dãy 11 phần tử
    // là index 5 (0-indexed), vì sau khi sắp xếp sẽ là 0 1 2 3 4 *5* 6 7 8 9 10
    size_t median_index = numbers.size() / 2;

    // Sử dụng nth_element để đưa phần tử ở vị trí median vào đúng chỗ
    nth_element(numbers.begin(), // first
                     numbers.begin() + median_index, // nth
                     numbers.end()); // last

    cout << "Phan tu tai vi tri median (" << median_index << ") la: " << numbers[median_index] << endl;

    // Lưu ý: cac phan tu truoc index median <= numbers[median_index]
    // va cac phan tu sau index median >= numbers[median_index],
    // nhung chung KHONG nhat thiet da duoc sap xep trong pham vi cua chung.
    cout << "Day so sau nth_element (khong hoan toan sap xep): ";
    for (int n : numbers) {
        cout << n << " ";
    }
    cout << endl;

    return 0;
}

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 numbers.begin() + median_index là iterator thứ hai.
  • Sau khi thực thi, phần tử tại numbers[median_index] (index 5) sẽ chính là median của dãy số ban đầu.
  • Các phần tử từ numbers[0] đến numbers[4] đều nhỏ hơn hoặc bằng numbers[5].
  • Các phần tử từ numbers[6] đến numbers[10] đều lớn hơn hoặc bằng numbers[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> // Cho pair

int main() {
    vector<pair<int, int>> data = {
        {5, 0}, {3, 1}, {5, 2}, {1, 3}, {3, 4}, {4, 5}
    }; // value, original_index

    cout << "Du lieu ban dau: ";
    for (const auto& p : data) {
        cout << "(" << p.first << "," << p.second << ") ";
    }
    cout << endl;

    // --- Sử dụng sort (có thể không ổn định) ---
    vector<pair<int, int>> data_for_sort = data; // Tạo bản sao
    sort(data_for_sort.begin(), data_for_sort.end(),
              [](const pair<int, int>& a, const pair<int, int>& b) {
                  return a.first < b.first; // Sap xep theo value tang dan
              });

    cout << "Ket qua sau sort (khong dam bao on dinh): ";
    for (const auto& p : data_for_sort) {
        cout << "(" << p.first << "," << p.second << ") ";
    }
    cout << endl;
    // Quan sat cac cap co value = 3: (3,1) va (3,4). Thu tu co the thay doi.
    // Quan sat cac cap co value = 5: (5,0) va (5,2). Thu tu co the thay doi.


    // --- Sử dụng stable_sort (ổn định) ---
    vector<pair<int, int>> data_for_stable_sort = data; // Tao ban sao
    stable_sort(data_for_stable_sort.begin(), data_for_stable_sort.end(),
                     [](const pair<int, int>& a, const pair<int, int>& b) {
                         return a.first < b.first; // Sap xep theo value tang dan
                     });

    cout << "Ket qua sau stable_sort (dam bao on dinh): ";
    for (const auto& p : data_for_stable_sort) {
        cout << "(" << p.first << "," << p.second << ") ";
    }
    cout << endl;
    // Quan sat cac cap co value = 3: (3,1) va (3,4). (3,1) luon xuat hien truoc (3,4) vi original_index 1 < 4.
    // Quan sat cac cap co value = 5: (5,0) va (5,2). (5,0) luon xuat hien truoc (5,2) vi original_index 0 < 2.


    return 0;
}

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.