Bài 22.3: Bài tập thực hành sắp xếp nhiều tiêu chí trong C++

Chào mừng bạn trở lại với series C++ của FullhouseDev! Hôm nay, chúng ta sẽ cùng đi sâu vào một kỹ thuật sắp xếp mạnh mẽ và cực kỳ phổ biến trong thế giới thực: sắp xếp dựa trên nhiều tiêu chí khác nhau.

Bạn đã quen thuộc với việc sắp xếp một danh sách số theo thứ tự tăng dần hoặc giảm dần, hoặc sắp xếp chuỗi ký tự theo thứ tự bảng chữ cái. Nhưng điều gì xảy ra khi bạn cần sắp xếp một danh sách các sinh viên dựa trên điểm số, và nếu hai sinh viên có điểm số bằng nhau, bạn muốn sắp xếp họ theo tên? Hoặc sắp xếp một danh sách sản phẩm theo loại, sau đó theo giá, và cuối cùng là theo tên? Đây chính là lúc kỹ thuật sắp xếp nhiều tiêu chí tỏa sáng!

Trong C++, thư viện chuẩn <algorithm> cung cấp cho chúng ta công cụ sort vô cùng linh hoạt. Mặc định, sort sử dụng toán tử < để so sánh các phần tử. Tuy nhiên, sức mạnh thực sự của nó nằm ở khả năng nhận một hàm so sánh tùy chỉnh (comparison function). Chính hàm so sánh này sẽ là "bộ não" giúp chúng ta định nghĩa các quy tắc sắp xếp phức tạp, bao gồm cả việc so sánh dựa trên nhiều thuộc tính khác nhau.

Một hàm so sánh tùy chỉnh cho sort thường là một hàm (hoặc lambda expression, hoặc functor) nhận hai tham số cùng kiểu với các phần tử trong container của bạn và trả về true nếu tham số đầu tiên nên đứng trước tham số thứ hai trong danh sách đã sắp xếp, và false ngược lại.

Nguyên tắc vàng khi triển khai hàm so sánh cho nhiều tiêu chí là:

  1. So sánh theo tiêu chí đầu tiên: Nếu hai phần tử khác biệt theo tiêu chí này, quyết định thứ tự ngay lập tức và trả về kết quả.
  2. Nếu hai phần tử giống nhau theo tiêu chí đầu tiên: Chuyển sang so sánh theo tiêu chí thứ hai. Nếu chúng khác biệt, quyết định thứ tự và trả về kết quả.
  3. Nếu vẫn giống nhau: Lặp lại quá trình cho tiêu chí thứ ba, thứ tư, v.v.
  4. Nếu giống nhau hoàn toàn theo tất cả các tiêu chí đã định nghĩa: Thứ tự tương đối giữa chúng không quan trọng đối với các tiêu chí này (thường giữ nguyên thứ tự ban đầu nếu sử dụng stable sort, nhưng sort thông thường không đảm bảo điều này).

Nghe có vẻ lý thuyết? Hãy cùng đi vào các ví dụ minh họa bằng C++ để thấy rõ hơn nhé!

Ví dụ 1: Sắp xếp Sinh viên theo Điểm (Giảm dần), sau đó theo Tên (Tăng dần)

Giả sử chúng ta có một danh sách các sinh viên, mỗi sinh viên có điểm số và tên. Chúng ta muốn xếp hạng sinh viên theo điểm từ cao xuống thấp. Nếu có hai sinh viên cùng điểm, chúng ta muốn xếp họ theo tên theo thứ tự bảng chữ cái.

Đầu tiên, định nghĩa cấu trúc dữ liệu cho Sinh viên:

#include <string>
#include <vector>
#include <iostream>
#include <algorithm> // Cần cho sort

// Cấu trúc dữ liệu cho Sinh viên
struct Student {
    string name;
    int score;
};

// Hàm helper để in danh sách sinh viên
void printStudents(const vector<Student>& students) {
    for (const auto& s : students) {
        cout << s.name << " (" << s.score << ") ";
    }
    cout << endl;
}

Bây giờ, chúng ta tạo một vector chứa dữ liệu mẫu và định nghĩa hàm so sánh tùy chỉnh:

int main() {
    vector<Student> students = {
        {"Alice", 85},
        {"Bob", 92},
        {"Charlie", 78},
        {"David", 92},
        {"Eve", 85},
        {"Frank", 95}
    };

    cout << "Danh sach truoc khi sap xep:" << endl;
    printStudents(students);

    // Dùng lambda function làm hàm so sánh
    sort(students.begin(), students.end(),
              [](const Student& a, const Student& b) {
                  // Tieu chi 1: Sap xep theo diem Giam dan (a.score > b.score)
                  if (a.score != b.score) {
                      return a.score > b.score; // 'a' dung truoc 'b' neu diem cua 'a' cao hon
                  }
                  // Tieu chi 2: Neu diem bang nhau, sap xep theo ten Tang dan (a.name < b.name)
                  return a.name < b.name; // 'a' dung truoc 'b' neu ten cua 'a' nho hon (theo bang chu cai)
              });

    cout << "\nDanh sach sau khi sap xep (Diem Giam, Ten Tang):" << endl;
    printStudents(students);

    return 0;
}

Giải thích:

  • Chúng ta định nghĩa một lambda expression (hàm ẩn danh) [](const Student& a, const Student& b) { ... } làm tham số thứ ba cho sort. Lambda này nhận hai đối tượng Student là a và b.
  • Bên trong lambda:
    • Dòng if (a.score != b.score) kiểm tra xem điểm của hai sinh viên có khác nhau không.
    • Nếu khác nhau, chúng ta quyết định thứ tự dựa trên điểm: return a.score > b.score;. Điều này trả về true nếu điểm của a lớn hơn điểm của b, tức là a nên đứng trước b (sắp xếp giảm dần theo điểm).
    • Nếu điểm của a và b bằng nhau (if sai), chúng ta bỏ qua if và đi đến dòng tiếp theo: return a.name < b.name;. Điều này so sánh tên của a và b theo thứ tự tăng dần (toán tử < cho string). Nếu tên của a đứng trước tên của b trong bảng chữ cái, nó trả về true, tức là a nên đứng trước b.
  • Kết quả là danh sách sinh viên được sắp xếp ưu tiên theo điểm giảm dần, và với những người cùng điểm, sẽ được sắp xếp theo tên tăng dần.

Output của ví dụ 1:

Danh sach truoc khi sap xep:
Alice (85) Bob (92) Charlie (78) David (92) Eve (85) Frank (95)

Danh sach sau khi sap xep (Diem Giam, Ten Tang):
Frank (95) Bob (92) David (92) Alice (85) Eve (85) Charlie (78)

Nhận xét: Frank có điểm cao nhất (95) nên đứng đầu. Bob và David cùng 92 điểm, nhưng "Bob" đứng trước "David" theo thứ tự bảng chữ cái, nên Bob đứng trước David. Alice và Eve cùng 85 điểm, "Alice" đứng trước "Eve" nên Alice đứng trước Eve. Charlie có điểm thấp nhất (78) nên đứng cuối.

Ví dụ 2: Sắp xếp Sản phẩm theo Loại (Tăng dần), Giá (Tăng dần), sau đó theo Tên (Tăng dần)

Tiếp tục với một ví dụ phức tạp hơn một chút: sắp xếp danh sách sản phẩm. Mỗi sản phẩm có loại (category), giá (price), và tên (name). Chúng ta muốn sắp xếp chúng theo loại, sau đó theo giá, và cuối cùng là theo tên. Tất cả đều theo thứ tự tăng dần.

Định nghĩa cấu trúc dữ liệu và hàm in:

#include <string>
#include <vector>
#include <iostream>
#include <algorithm> // Cần cho sort

struct Product {
    string category;
    string name;
    double price;
};

void printProducts(const vector<Product>& products) {
    for (const auto& p : products) {
        cout << p.category << "/" << p.name << " (" << p.price << ") ";
    }
    cout << endl;
}

Code sắp xếp:

int main() {
    vector<Product> products = {
        {"Electronics", "Laptop", 1200.0},
        {"Books", "C++ Primer", 60.0},
        {"Electronics", "Mouse", 25.0},
        {"Books", "Effective C++", 40.0},
        {"Electronics", "Keyboard", 75.0},
        {"Books", "The Hitchhiker's Guide", 15.0}
    };

    cout << "Danh sach truoc khi sap xep:" << endl;
    printProducts(products);

    sort(products.begin(), products.end(),
              [](const Product& a, const Product& b) {
                  // Tieu chi 1: Sap xep theo Loai Tang dan (a.category < b.category)
                  if (a.category != b.category) {
                      return a.category < b.category;
                  }
                  // Tieu chi 2: Neu Loai giong nhau, sap xep theo Gia Tang dan (a.price < b.price)
                  if (a.price != b.price) {
                      return a.price < b.price;
                  }
                  // Tieu chi 3: Neu Loai va Gia giong nhau, sap xep theo Ten Tang dan (a.name < b.name)
                  return a.name < b.name;
              });

    cout << "\nDanh sach sau khi sap xep (Loai Tang, Gia Tang, Ten Tang):" << endl;
    printProducts(products);

    return 0;
}

Giải thích:

  • Lambda function của chúng ta giờ đây có ba cấp độ kiểm tra.
  • Đầu tiên, nó so sánh a.category và b.category. Nếu chúng khác nhau, kết quả a.category < b.category quyết định thứ tự.
  • Chỉ khi a.category == b.category (điều kiện if đầu tiên sai), nó mới tiếp tục so sánh a.price và b.price. Nếu giá khác nhau, a.price < b.price quyết định thứ tự.
  • Chỉ khi cả loại và giá đều bằng nhau, nó mới so sánh tên a.name và b.name bằng a.name < b.name.
  • Lưu ý rằng ở mỗi cấp độ, chúng ta sử dụng toán tử < để thực hiện sắp xếp tăng dần. Nếu muốn sắp xếp giảm dần ở một tiêu chí nào đó, bạn chỉ cần thay đổi thành >.

Output của ví dụ 2:

Danh sach truoc khi sap xep:
Electronics/Laptop (1200) Books/C++ Primer (60) Electronics/Mouse (25) Books/Effective C++ (40) Electronics/Keyboard (75) Books/The Hitchhiker's Guide (15)

Danh sach sau khi sap xep (Loai Tang, Gia Tang, Ten Tang):
Books/The Hitchhiker's Guide (15) Books/Effective C++ (40) Books/C++ Primer (60) Electronics/Mouse (25) Electronics/Keyboard (75) Electronics/Laptop (1200)

Nhận xét: Đầu tiên, nhóm "Books" đứng trước "Electronics" vì "B" đứng trước "E". Trong nhóm "Books", các sản phẩm được sắp xếp theo giá tăng dần (15, 40, 60). Trong nhóm "Electronics", các sản phẩm được sắp xếp theo giá tăng dần (25, 75, 1200). Trong ví dụ này, không có trường hợp hai sản phẩm cùng loại và cùng giá, nên tiêu chí thứ ba (tên) không cần đến để phá vỡ sự "hòa".

Ví dụ 3: Sắp xếp Công việc theo Độ ưu tiên (Giảm dần), sau đó theo Hạn chót (Tăng dần)

Một ví dụ thực tế khác: sắp xếp danh sách các công việc (Task). Mỗi công việc có độ ưu tiên (số nguyên, số càng cao càng ưu tiên) và hạn chót (giả sử là chuỗi ngày tháng). Chúng ta muốn các công việc có độ ưu tiên cao hơn đứng trước, và nếu hai công việc có cùng độ ưu tiên, công việc nào có hạn chót sớm hơn sẽ đứng trước.

Định nghĩa cấu trúc dữ liệu và hàm in:

#include <string>
#include <vector>
#include <iostream>
#include <algorithm> // Cần cho sort

struct Task {
    string description;
    int priority; // Cao hon la uu tien hon
    string dueDate; // Dang YYYY-MM-DD de so sanh chuoi truc tiep

    // Helper de in
    void print() const {
        cout << "'" << description << "' (Pri: " << priority << ", Due: " << dueDate << ") ";
    }
};

void printTasks(const vector<Task>& tasks) {
    for (const auto& t : tasks) {
        t.print();
    }
    cout << endl;
}

Code sắp xếp:

int main() {
    vector<Task> tasks = {
        {"Finish report", 2, "2024-08-10"},
        {"Email client", 3, "2024-08-05"},
        {"Plan meeting", 1, "2024-08-15"},
        {"Review code", 3, "2024-08-08"},
        {"Write blog post", 2, "2024-08-05"}
    };

    cout << "Danh sach truoc khi sap xep:" << endl;
    printTasks(tasks);

    sort(tasks.begin(), tasks.end(),
              [](const Task& a, const Task& b) {
                  // Tieu chi 1: Sap xep theo Do uu tien Giam dan (a.priority > b.priority)
                  if (a.priority != b.priority) {
                      return a.priority > b.priority; // 'a' dung truoc 'b' neu priority cua 'a' cao hon
                  }
                  // Tieu chi 2: Neu Do uu tien giong nhau, sap xep theo Han chot Tang dan (a.dueDate < b.dueDate)
                  return a.dueDate < b.dueDate; // 'a' dung truoc 'b' neu han chot cua 'a' som hon
              });

    cout << "\nDanh sach sau khi sap xep (Uu tien Giam, Han chot Tang):" << endl;
    printTasks(tasks);

    return 0;
}

Giải thích:

  • Ở đây, tiêu chí đầu tiên là độ ưu tiên, sắp xếp giảm dần. Logic return a.priority > b.priority; thực hiện điều này. Nếu a có độ ưu tiên cao hơn b, biểu thức a.priority > b.priority là true, hàm trả về true, báo cho sort biết a nên đứng trước b.
  • Nếu độ ưu tiên bằng nhau, chúng ta chuyển sang so sánh hạn chót. Hạn chót được lưu dưới dạng chuỗi YYYY-MM-DD. Với định dạng này, so sánh chuỗi trực tiếp (<) sẽ cho kết quả đúng theo thứ tự thời gian (ngày sớm hơn có chuỗi nhỏ hơn).
  • Logic return a.dueDate < b.dueDate; thực hiện sắp xếp tăng dần theo hạn chót.

Output của ví dụ 3:

Danh sach truoc khi sap xep:
'Finish report' (Pri: 2, Due: 2024-08-10) 'Email client' (Pri: 3, Due: 2024-08-05) 'Plan meeting' (Pri: 1, Due: 2024-08-15) 'Review code' (Pri: 3, Due: 2024-08-08) 'Write blog post' (Pri: 2, Due: 2024-08-05)

Danh sach sau khi sap xep (Uu tien Giam, Han chot Tang):
'Email client' (Pri: 3, Due: 2024-08-05) 'Review code' (Pri: 3, Due: 2024-08-08) 'Write blog post' (Pri: 2, Due: 2024-08-05) 'Finish report' (Pri: 2, Due: 2024-08-10) 'Plan meeting' (Pri: 1, Due: 2024-08-15)

Nhận xét: Các công việc có độ ưu tiên 3 đứng đầu. Trong nhóm này, "Email client" có hạn chót 08-05 đứng trước "Review code" có hạn chót 08-08. Tiếp theo là nhóm độ ưu tiên 2. Trong nhóm này, "Write blog post" có hạn chót 08-05 đứng trước "Finish report" có hạn chót 08-10. Cuối cùng là công việc có độ ưu tiên 1. Kết quả hoàn toàn tuân thủ các quy tắc đã đặt ra.

Comments

There are no comments at the moment.