Bài 23.5: Bài tập thực hành kết hợp sắp xếp và tìm kiếm trong C++

Bài 23.5: Bài tập thực hành kết hợp sắp xếp và tìm kiếm trong C++
Chào mừng bạn trở lại với chuỗi bài học về C++! Hôm nay, chúng ta sẽ không chỉ dừng lại ở việc tìm hiểu riêng rẽ các thuật toán sắp xếp hay tìm kiếm nữa, mà sẽ đi sâu vào một kỹ thuật cực kỳ mạnh mẽ và phổ biến trong lập trình thực tế: kết hợp sắp xếp và tìm kiếm.
Bạn đã bao giờ phải tìm kiếm một thông tin cụ thể trong một lượng dữ liệu khổng lồ chưa? Nếu dữ liệu đó không được sắp xếp theo một trật tự nào cả, công việc tìm kiếm có thể trở nên rất chậm chạp. Nhưng nếu dữ liệu đã được sắp xếp gọn gàng, việc tìm kiếm sẽ nhanh hơn gấp nhiều lần! Đó chính là sức mạnh mà chúng ta sẽ khám phá trong bài tập thực hành này.
Tại sao lại kết hợp Sắp xếp và Tìm kiếm?
Hãy tưởng tượng bạn có một danh bạ điện thoại gồm hàng ngàn số. Nếu danh bạ lộn xộn, bạn sẽ phải duyệt qua từng tên một từ đầu đến cuối cho đến khi tìm thấy người mình cần. Đây chính là tìm kiếm tuyến tính (linear search) - đơn giản nhưng kém hiệu quả khi dữ liệu lớn.
Nhưng nếu danh bạ được sắp xếp theo thứ tự bảng chữ cái? Bạn có thể mở danh bạ ở giữa, xem tên đó nằm ở nửa đầu hay nửa sau, rồi lại tiếp tục chia đôi phần còn lại để tìm kiếm. Quá trình này nhanh hơn rất nhiều so với duyệt từng mục. Đây là ý tưởng cốt lõi của tìm kiếm nhị phân (binary search) - một thuật toán cực kỳ hiệu quả nhưng chỉ hoạt động được trên dữ liệu đã được sắp xếp.
Vì vậy, chiến lược phổ biến là:
- Sắp xếp dữ liệu một lần ban đầu.
- Thực hiện tìm kiếm nhị phân (hoặc các thuật toán tìm kiếm hiệu quả khác dựa trên dữ liệu có thứ tự) nhiều lần trên dữ liệu đã được sắp xếp đó.
Chi phí để sắp xếp (thường là O(N log N)) có thể đáng kể, nhưng nếu bạn cần thực hiện nhiều thao tác tìm kiếm sau đó, lợi ích của việc tìm kiếm nhị phân tốc độ cao (O(log N)) sẽ nhanh chóng bù đắp chi phí sắp xếp ban đầu.
Ví dụ 1: Tìm kiếm trên mảng số nguyên
Hãy bắt đầu với một ví dụ đơn giản: tìm kiếm một số trong một vector các số nguyên.
Giả sử chúng ta có vector sau: { 4, 1, 7, 3, 9, 2, 5, 8, 6 }
. Chúng ta muốn tìm số 5
.
Nếu dùng tìm kiếm tuyến tính, chúng ta sẽ kiểm tra 4
, rồi 1
, rồi 7
, 3
, 9
, 2
, 5
. Mất 7 bước.
Nếu chúng ta sắp xếp vector trước: { 1, 2, 3, 4, 5, 6, 7, 8, 9 }
. Bây giờ, để tìm 5
:
- Kiểm tra phần tử ở giữa:
5
. Tìm thấy ngay! Mất 1 bước (trường hợp lý tưởng). - Nếu tìm
2
: Kiểm tra giữa (5
),2
nhỏ hơn5
, tìm ở nửa đầu{1, 2, 3, 4}
. Kiểm tra giữa của nửa đầu (2.5
, lấy3
).2
nhỏ hơn3
, tìm ở nửa đầu của nửa đầu{1, 2}
. Kiểm tra giữa của{1, 2}
(lấy1
).2
lớn hơn1
, tìm ở nửa sau của{1, 2}
({2}
). Kiểm tra2
. Tìm thấy! Mất 4 bước.
Rõ ràng, tìm kiếm trên mảng đã sắp xếp hiệu quả hơn nhiều.
C++ cung cấp các hàm tiện lợi trong thư viện <algorithm>
để thực hiện cả sắp xếp và tìm kiếm nhị phân.
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
vector<int> a = { 4, 1, 7, 3, 9, 2, 5, 8, 6 };
cout << "Vector ban dau: ";
for (int x : a) {
cout << x << " ";
}
cout << endl;
sort(a.begin(), a.end());
cout << "Vector sau khi sap xep: ";
for (int x : a) {
cout << x << " ";
}
cout << endl;
int gt = 5;
bool timThay = binary_search(a.begin(), a.end(), gt);
if (timThay) {
cout << "Da tim thay so " << gt << " trong vector." << endl;
} else {
cout << "Khong tim thay so " << gt << " trong vector." << endl;
}
gt = 10;
timThay = binary_search(a.begin(), a.end(), gt);
if (timThay) {
cout << "Da tim thay so " << gt << " trong vector." << endl;
} else {
cout << "Khong tim thay so " << gt << " trong vector." << endl;
}
return 0;
}
Output:
Vector ban dau: 4 1 7 3 9 2 5 8 6
Vector sau khi sap xep: 1 2 3 4 5 6 7 8 9
Da tim thay so 5 trong vector.
Khong tim thay so 10 trong vector.
Ví dụ 2: Kết hợp với các cấu trúc dữ liệu phức tạp hơn
Kỹ thuật này không chỉ áp dụng cho các kiểu dữ liệu cơ bản như số nguyên. Bạn có thể sắp xếp và tìm kiếm các đối tượng phức tạp hơn, miễn là bạn định nghĩa cách so sánh chúng.
Giả sử chúng ta có một danh sách sinh viên, mỗi sinh viên có ID và tên. Chúng ta muốn tìm kiếm sinh viên dựa trên ID.
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
struct SV {
int id;
string ten;
};
int main() {
vector<SV> ds = {
{103, "Nguyen Van A"},
{101, "Tran Thi B"},
{105, "Le Van C"},
{102, "Pham Thu D"},
{104, "Hoang Van E"}
};
cout << "Danh sach SV ban dau:" << endl;
for (const auto& s : ds) {
cout << "ID: " << s.id << ", Ten: " << s.ten << endl;
}
cout << endl;
sort(ds.begin(), ds.end(),
[](const SV& a, const SV& b) {
return a.id < b.id;
});
cout << "Danh sach SV sau khi sap xep theo ID:" << endl;
for (const auto& s : ds) {
cout << "ID: " << s.id << ", Ten: " << s.ten << endl;
}
cout << endl;
int idT = 102;
auto it = lower_bound(ds.begin(), ds.end(), idT,
[](const SV& s, int tId) {
return s.id < tId;
});
if (it != ds.end() && it->id == idT) {
cout << "Da tim thay sinh vien voi ID " << idT << ":" << endl;
cout << "ID: " << it->id << ", Ten: " << it->ten << endl;
} else {
cout << "Khong tim thay sinh vien voi ID " << idT << "." << endl;
}
idT = 999;
it = lower_bound(ds.begin(), ds.end(), idT,
[](const SV& s, int tId) {
return s.id < tId;
});
if (it != ds.end() && it->id == idT) {
cout << "Da tim thay sinh vien voi ID " << idT << ":" << cout << endl;
cout << "ID: " << it->id << ", Ten: " << it->ten << endl;
} else {
cout << "Khong tim thay sinh vien voi ID " << idT << "." << endl;
}
return 0;
}
Output:
Danh sach SV ban dau:
ID: 103, Ten: Nguyen Van A
ID: 101, Ten: Tran Thi B
ID: 105, Ten: Le Van C
ID: 102, Ten: Pham Thu D
ID: 104, Ten: Hoang Van E
Danh sach SV sau khi sap xep theo ID:
ID: 101, Ten: Tran Thi B
ID: 102, Ten: Pham Thu D
ID: 103, Ten: Nguyen Van A
ID: 104, Ten: Hoang Van E
ID: 105, Ten: Le Van C
Da tim thay sinh vien voi ID 102:
ID: 102, Ten: Pham Thu D
Khong tim thay sinh vien voi ID 999.
Khi nào nên sử dụng kỹ thuật này?
Kỹ thuật sắp xếp rồi tìm kiếm nhị phân rất hữu ích khi:
- Bạn có một lượng dữ liệu lớn.
- Bạn cần thực hiện nhiều thao tác tìm kiếm trên cùng một tập dữ liệu đó.
- Bạn có thể chấp nhận chi phí sắp xếp ban đầu.
Các trường hợp điển hình bao gồm:
- Xây dựng các hệ thống tra cứu nhanh.
- Xử lý dữ liệu trong cơ sở dữ liệu (các chỉ mục - index - trong database thường được xây dựng dựa trên các cấu trúc dữ liệu đã sắp xếp để tăng tốc độ tìm kiếm).
- Các bài toán cần kiểm tra sự tồn tại hoặc tìm kiếm vị trí của các phần tử trong tập hợp lớn.
Comments