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

Chào mừng trở lại với chuỗi bài học C++ của FullhouseDev!

Trong thế giới lập trình, việc xử lý dữ liệu là một phần không thể thiếu. Và hai trong số những thao tác cơ bản, quan trọng nhất mà chúng ta thường xuyên thực hiện trên tập dữ liệu chính là sắp xếp và tìm kiếm. Dữ liệu được sắp xếp gọn gàng giúp việc tìm kiếm trở nên nhanh chóng hơn, phân tích dễ dàng hơn, và các thao tác khác cũng hiệu quả hơn rất nhiều.

May mắn thay, thư viện chuẩn của C++ (Standard Library) cung cấp cho chúng ta những công cụ vô cùng mạnh mẽ và tiện lợi để thực hiện cả hai tác vụ này mà không cần phải tự "phát minh lại bánh xe" (tự cài đặt từ đầu các thuật toán phức tạp).

Bài thực hành hôm nay sẽ giúp bạn làm quen và sử dụng các hàm phổ biến nhất trong thư viện <algorithm> của C++ để sắp xếp và tìm kiếm dữ liệu.

Sắp xếp dữ liệu với `sort`

Sắp xếp là quá trình bố trí các phần tử của một tập hợp theo một thứ tự cụ thể (ví dụ: tăng dần hoặc giảm dần). C++ cung cấp hàm sort trong header <algorithm>, một công cụ cực kỳ hiệu quả (thường sử dụng thuật toán Introsort, là sự kết hợp của QuickSort, HeapSort và InsertionSort) để sắp xếp các container có iterator ngẫu nhiên (như vector, deque, mảng C-style).

Cú pháp cơ bản của sort:

sort(first, last);

Trong đó:

first: Iterator trỏ đến phần tử đầu tiên của phạm vi cần sắp xếp.
last: Iterator trỏ đến vị trí ngay sau phần tử cuối cùng của phạm vi cần sắp xếp.

Mặc định, sort sẽ sắp xếp theo thứ tự tăng dần.

Hãy xem một ví dụ đơn giản với vector các số nguyên:

#include <iostream>
#include <vector>
#include <algorithm> // Can thiet cho sort

int main() {
    vector<int> numbers = {5, 2, 8, 1, 9, 4};

    cout << "Vector ban dau: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    // Su dung sort de sap xep vector tang dan
    sort(numbers.begin(), numbers.end());

    cout << "Vector sau khi sap xep tang dan: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Giải thích code:

Chúng ta include các header cần thiết: <iostream> để nhập/xuất, <vector> để sử dụng vector, và <algorithm> để sử dụng sort.
Một vector<int> tên numbers được khởi tạo với một vài giá trị không theo thứ tự.
Chúng ta in ra trạng thái ban đầu của vector.
Dòng mấu chốt: sort(numbers.begin(), numbers.end()); gọi hàm sort. numbers.begin() trả về iterator trỏ đến phần tử đầu tiên, và numbers.end() trả về iterator trỏ đến vị trí sau phần tử cuối cùng. sort sẽ sắp xếp tất cả các phần tử trong phạm vi này.
Cuối cùng, chúng ta in ra vector sau khi đã được sắp xếp.

Kết quả khi chạy chương trình trên sẽ là:

Vector ban dau: 5 2 8 1 9 4
Vector sau khi sap xep tang dan: 1 2 4 5 8 9

Tuyệt vời! Chỉ với một dòng lệnh, chúng ta đã sắp xếp xong vector.

Sắp xếp theo thứ tự khác

Bạn muốn sắp xếp giảm dần? sort có một phiên bản overload cho phép bạn truyền vào một tiêu chí so sánh (comparison criteria) dưới dạng một hàm hoặc một đối tượng hàm (functor).

Để sắp xếp giảm dần, bạn có thể sử dụng greater<int>() (đối tượng hàm được cung cấp trong header <functional>) hoặc viết một lambda function đơn giản:

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional> // Can thiet cho greater

int main() {
    vector<int> numbers = {5, 2, 8, 1, 9, 4};

    // Sap xep vector giam dan su dung greater
    sort(numbers.begin(), numbers.end(), greater<int>());

    cout << "Vector sau khi sap xep giam dan (greater): ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    // Dat lai vector de sap xep lai
    numbers = {5, 2, 8, 1, 9, 4};

    // Sap xep vector giam dan su dung lambda function
    sort(numbers.begin(), numbers.end(), [](int a, int b){
        return a > b; // Tra ve true neu a lon hon b (sap xep giam dan)
    });

    cout << "Vector sau khi sap xep giam dan (lambda): ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Giải thích code:

Chúng ta thêm #include <functional> để sử dụng greater.
Phiên bản sort thứ hai có thêm đối số thứ ba: greater<int>(). Đối tượng này định nghĩa phép so sánh "lớn hơn", làm cho sort sắp xếp các phần tử theo thứ tự giảm dần.
Ví dụ thứ hai sử dụng một lambda function [](int a, int b){ return a > b; }. Lambda này nhận hai số nguyên a và b và trả về true nếu a > b. Khi truyền lambda này cho sort, nó sẽ sử dụng tiêu chí này để quyết định thứ tự các phần tử, dẫn đến sắp xếp giảm dần.

Cả hai cách trên đều cho kết quả sắp xếp giảm dần:

Vector sau khi sap xep giam dan (greater): 9 8 5 4 2 1
Vector sau khi sap xep giam dan (lambda): 9 8 5 4 2 1

Việc hiểu và sử dụng sort với tiêu chí so sánh tùy chỉnh là cực kỳ quan trọng khi bạn cần sắp xếp các cấu trúc dữ liệu phức tạp hơn hoặc theo các quy tắc riêng.

Tìm kiếm dữ liệu với `find` và `binary_search`

Sau khi dữ liệu đã được sắp xếp (hoặc ngay cả khi chưa được sắp xếp), nhu cầu tiếp theo thường là tìm kiếm một phần tử cụ thể nào đó. Thư viện <algorithm> cũng cung cấp các hàm tìm kiếm hiệu quả.

Tìm kiếm tuần tự với `find`

find là hàm tìm kiếm cơ bản nhất. Nó thực hiện tìm kiếm tuần tự (linear search) trong một phạm vi, duyệt qua từng phần tử từ đầu đến cuối để xem có phần tử nào khớp với giá trị cần tìm hay không.

Cú pháp:

find(first, last, value);

first, last: Phạm vi cần tìm kiếm (giống như sort).
value: Giá trị cần tìm.

find trả về một iterator. Nếu tìm thấy phần tử, iterator này trỏ đến vị trí của phần tử đầu tiên tìm thấy. Nếu không tìm thấy, nó trả về iterator last (iterator trỏ đến vị trí ngay sau phần tử cuối cùng của phạm vi).

Hãy xem ví dụ:

#include <iostream>
#include <vector>
#include <algorithm> // Can thiet cho find
#include <iterator>  // Can thiet cho distance (de tinh vi tri)

int main() {
    vector<int> numbers = {10, 20, 30, 40, 50};
    int target1 = 30;
    int target2 = 99;

    // Tim kiem phan tu co gia tri 30
    auto it1 = find(numbers.begin(), numbers.end(), target1);

    // Kiem tra xem phan tu co duoc tim thay khong
    if (it1 != numbers.end()) {
        cout << "Tim thay " << target1 << " tai vi tri index: " << distance(numbers.begin(), it1) << endl;
    } else {
        cout << "Khong tim thay " << target1 << " trong vector." << endl;
    }

    // Tim kiem phan tu co gia tri 99
    auto it2 = find(numbers.begin(), numbers.end(), target2);

    if (it2 != numbers.end()) {
        // Truong hop nay se khong xay ra
        cout << "Tim thay " << target2 << " tai vi tri index: " << distance(numbers.begin(), it2) << endl;
    } else {
        cout << "Khong tim thay " << target2 << " trong vector." << endl;
    }

    return 0;
}

Giải thích code:

Chúng ta include <iterator> để dùng distance (giúp tính khoảng cách từ begin iterator đến iterator tìm thấy, tức là chỉ số index).
find(numbers.begin(), numbers.end(), target1) tìm kiếm giá trị target1 (là 30) trong vector. Iterator it1 sẽ trỏ đến phần tử có giá trị 30.
Điều kiện if (it1 != numbers.end()) kiểm tra xem iterator trả về có phải là iterator end() hay không. Nếu không phải là end(), nghĩa là phần tử đã được tìm thấy.
distance(numbers.begin(), it1) tính số bước từ đầu vector đến vị trí của it1, chính là chỉ số index của phần tử tìm thấy.
Chúng ta lặp lại quá trình tìm kiếm với target2 (là 99). Lần này, find không tìm thấy 99 trong vector, nên nó trả về numbers.end().
Điều kiện if (it2 != numbers.end()) sẽ là false, và thông báo "Khong tim thay..." sẽ được in ra.

Kết quả chạy chương trình:

Tim thay 30 tai vi tri index: 2
Khong tim thay 99 trong vector.

find rất hữu ích vì nó hoạt động trên mọi loại iterator (không yêu cầu ngẫu nhiên) và không yêu cầu dữ liệu phải được sắp xếp. Tuy nhiên, độ phức tạp thời gian của nó là tuyến tính (O(N)), nghĩa là thời gian tìm kiếm tăng tỷ lệ thuận với số lượng phần tử. Với tập dữ liệu lớn, nó có thể chậm.

Tìm kiếm nhị phân với `binary_search`

Khi dữ liệu đã được sắp xếp, chúng ta có thể sử dụng một thuật toán tìm kiếm hiệu quả hơn nhiều là tìm kiếm nhị phân (binary search). Tìm kiếm nhị phân hoạt động bằng cách lặp lại việc chia đôi phạm vi tìm kiếm cho đến khi tìm thấy phần tử hoặc phạm vi trở nên trống rỗng.

binary_search trong <algorithm> thực hiện điều này. Điều kiện tiên quyết quan trọng nhất để sử dụng binary_search là phạm vi dữ liệu phải ĐÃ được sắp xếp theo cùng tiêu chí mà phép tìm kiếm sẽ sử dụng (mặc định là tăng dần).

Cú pháp:

binary_search(first, last, value);

first, last: Phạm vi đã được sắp xếp cần tìm kiếm.
value: Giá trị cần tìm.

binary_search không trả về iterator hay vị trí. Nó chỉ trả về một giá trị bool: true nếu tìm thấy phần tử, false nếu không tìm thấy.

Hãy xem ví dụ, kết hợp với sort:

#include <iostream>
#include <vector>
#include <algorithm> // Can thiet cho sort va binary_search

int main() {
    vector<int> numbers = {10, 50, 20, 40, 30}; // Chua sap xep
    int target1 = 40;
    int target2 = 99;

    // === Buoc 1: Sap xep du lieu (BAT BUOC cho binary_search) ===
    sort(numbers.begin(), numbers.end());

    cout << "Vector sau khi sap xep (de su dung binary_search): ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    // === Buoc 2: Thuc hien tim kiem nhi phan ===

    // Tim kiem phan tu co gia tri 40
    bool found1 = binary_search(numbers.begin(), numbers.end(), target1);

    if (found1) {
        cout << "Tim thay " << target1 << " trong vector (su dung binary_search)." << endl;
    } else {
        cout << "Khong tim thay " << target1 << " trong vector (su dung binary_search)." << endl;
    }

    // Tim kiem phan tu co gia tri 99
    bool found2 = binary_search(numbers.begin(), numbers.end(), target2);

    if (found2) {
        cout << "Tim thay " << target2 << " trong vector (su dung binary_search)." << endl;
    } else {
        cout << "Khong tim thay " << target2 << " trong vector (su dung binary_search)." << endl;
    }

    return 0;
}

Giải thích code:

Chúng ta khởi tạo vector numbers chưa sắp xếp.
Quan trọng: Chúng ta phải gọi sort để sắp xếp vector trước khi sử dụng binary_search.
binary_search(numbers.begin(), numbers.end(), target1) tìm kiếm giá trị target1 (là 40) trong vector đã được sắp xếp. Vì 40 có trong vector, hàm trả về true.
Kết quả found1 là true, thông báo tương ứng được in ra.
binary_search(numbers.begin(), numbers.end(), target2) tìm kiếm giá trị target2 (là 99). Vì 99 không có trong vector, hàm trả về false.
Kết quả found2 là false, thông báo không tìm thấy được in ra.

Kết quả chạy chương trình:

Vector sau khi sap xep (de su dung binary_search): 10 20 30 40 50
Tim thay 40 trong vector (su dung binary_search).
Khong tim thay 99 trong vector (su dung binary_search).

Ưu điểm lớn nhất của binary_search là hiệu quả về thời gian. Độ phức tạp thời gian của nó là logarit (O(log N)), nghĩa là thời gian tìm kiếm chỉ tăng rất chậm khi số lượng phần tử tăng lên. Với các tập dữ liệu lớn, sự khác biệt giữa O(N) của find và O(log N) của binary_search là khổng lồ.

Kết hợp và Thực hành

Trong thực tế, bạn thường sẽ cần kết hợp cả sắp xếp và tìm kiếm. Ví dụ, bạn nhận được một danh sách dữ liệu thô, việc đầu tiên có thể là sắp xếp nó, sau đó bạn có thể thực hiện nhiều thao tác tìm kiếm nhanh chóng trên dữ liệu đã được tổ chức.

Hãy thử các ví dụ trên, thay đổi dữ liệu đầu vào, thử sắp xếp các kiểu dữ liệu khác (ví dụ: string), hoặc tìm kiếm trong các container khác (nếu có thể với iterator ngẫu nhiên). Đây là cách tốt nhất để nắm vững cách sử dụng các công cụ mạnh mẽ này.

Các hàm sort, find, và binary_search chỉ là khởi đầu. Thư viện <algorithm> còn chứa rất nhiều thuật toán hữu ích khác như reverse, unique, lower_bound, upper_bound, min_element, max_element, v.v... Khám phá chúng sẽ mở ra nhiều cánh cửa giải quyết vấn đề hiệu quả hơn trong C++.

Comments

There are no comments at the moment.