Bài 22.3: Bài tập thực hành sắp xếp nhiều tiêu chí trong C++
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à:
- 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ả.
- 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ả.
- Nếu vẫn giống nhau: Lặp lại quá trình cho tiêu chí thứ ba, thứ tư, v.v.
- 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
sortthô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>
struct SinhVien {
string ten;
int diem;
};
void inDS(const vector<SinhVien>& ds) {
for (const auto& sv : ds) {
cout << sv.ten << " (" << sv.diem << ") ";
}
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<SinhVien> ds = {
{"Alice", 85},
{"Bob", 92},
{"Charlie", 78},
{"David", 92},
{"Eve", 85},
{"Frank", 95}
};
cout << "Danh sach truoc khi sap xep:" << endl;
inDS(ds);
sort(ds.begin(), ds.end(),
[](const SinhVien& a, const SinhVien& b) {
if (a.diem != b.diem) {
return a.diem > b.diem;
}
return a.ten < b.ten;
});
cout << "\nDanh sach sau khi sap xep (Diem Giam, Ten Tang):" << endl;
inDS(ds);
return 0;
}
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>
struct SanPham {
string loai;
string ten;
double gia;
};
void inDS(const vector<SanPham>& ds) {
for (const auto& sp : ds) {
cout << sp.loai << "/" << sp.ten << " (" << sp.gia << ") ";
}
cout << endl;
}
Code sắp xếp:
int main() {
vector<SanPham> ds = {
{"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;
inDS(ds);
sort(ds.begin(), ds.end(),
[](const SanPham& a, const SanPham& b) {
if (a.loai != b.loai) {
return a.loai < b.loai;
}
if (a.gia != b.gia) {
return a.gia < b.gia;
}
return a.ten < b.ten;
});
cout << "\nDanh sach sau khi sap xep (Loai Tang, Gia Tang, Ten Tang):" << endl;
inDS(ds);
return 0;
}
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>
struct CongViec {
string moTa;
int uuTien;
string hanChot;
void in() const {
cout << "'" << moTa << "' (Pri: " << uuTien << ", Due: " << hanChot << ") ";
}
};
void inDS(const vector<CongViec>& ds) {
for (const auto& cv : ds) {
cv.in();
}
cout << endl;
}
Code sắp xếp:
int main() {
vector<CongViec> ds = {
{"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;
inDS(ds);
sort(ds.begin(), ds.end(),
[](const CongViec& a, const CongViec& b) {
if (a.uuTien != b.uuTien) {
return a.uuTien > b.uuTien;
}
return a.hanChot < b.hanChot;
});
cout << "\nDanh sach sau khi sap xep (Uu tien Giam, Han chot Tang):" << endl;
inDS(ds);
return 0;
}
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