Bài 22.1: Bài tập thực hành hàm sort trong C++

Chào mừng bạn quay trở lại với series về C++! Hôm nay, chúng ta sẽ cùng nhau đi sâu vào một công cụ cực kỳ mạnh mẽ và được sử dụng rộng rãi trong C++: hàm sort. Đây không chỉ là một bài giới thiệu, mà còn là một buổi thực hành để bạn nắm vững cách sử dụng nó trong các tình huống khác nhau. Sắp xếp dữ liệu là một thao tác cơ bản nhưng vô cùng quan trọng trong lập trình, và sort từ thư viện chuẩn <algorithm> sẽ giúp chúng ta làm điều đó một cách hiệu quả.

sort là gì?

sort là một hàm thuộc thư viện <algorithm> của C++ Standard Library. Nó được thiết kế để sắp xếp các phần tử trong một phạm vi (range) được xác định bởi hai iterator. Mặc định, nó sẽ sắp xếp theo thứ tự tăng dần.

Điểm mạnh của sort là nó có hiệu suất rất tốt. Thông thường, việc triển khai của nó sử dụng một thuật toán lai (hybrid algorithm), phổ biến nhất là IntroSort, kết hợp giữa QuickSort (nhanh trên trung bình), HeapSort (đảm bảo hiệu suất xấu nhất) và InsertionSort (hiệu quả với tập dữ liệu nhỏ hoặc gần như đã sắp xếp). Độ phức tạp thời gian trung bình của sort là $O(N \log N)$, với N là số phần tử cần sắp xếp.

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

sort(first_iterator, last_iterator);

Trong đó:

  • first_iterator: Là một iterator trỏ đến phần tử đầu tiên của phạm vi cần sắp xếp.
  • last_iterator: Là một iterator trỏ đến sau phần tử cuối cùng của phạm vi cần sắp xếp. Lưu ý quan trọng: phạm vi này bao gồm first_iterator nhưng không bao gồm last_iterator.

Để sử dụng sort, bạn cần include header <algorithm>. Nếu làm việc với vector, bạn cũng cần <vector>.

Thực hành Cơ bản: Sắp xếp Mảng và Vector số nguyên

Hãy bắt đầu với trường hợp đơn giản nhất: sắp xếp một mảng hoặc một vector chứa các số nguyên.

Ví dụ 1: Sắp xếp vector<int> tăng dần
#include <iostream>
#include <vector>
#include <algorithm>

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

    cout << "Vector trc sx: ";
    for (int x : a) {
        cout << x << " ";
    }
    cout << endl;

    sort(a.begin(), a.end());

    cout << "Vector sau sx: ";
    for (int x : a) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

Output:

Vector trc sx: 5 2 8 1 9 4 
Vector sau sx: 1 2 4 5 8 9
  • Giải thích:
    • Chúng ta khai báo một vector chứa các số nguyên không theo thứ tự.
    • a.begin() trả về một iterator trỏ đến phần tử đầu tiên (5).
    • a.end() trả về một iterator trỏ đến vị trí ngay sau phần tử cuối cùng (4).
    • sort(a.begin(), a.end()); gọi hàm sort để sắp xếp toàn bộ vector theo thứ tự tăng dần (mặc định).
    • Kết quả in ra sẽ là 1 2 4 5 8 9.
Ví dụ 2: Sắp xếp Mảng C++ (C-style Array)

sort cũng hoạt động với mảng truyền thống của C++, sử dụng con trỏ như iterator.

#include <iostream>
#include <algorithm>

int main() {
    int a[] = {7, 3, 0, 6, 10, 5};
    int sz = sizeof(a) / sizeof(a[0]);

    cout << "Mang trc sx: ";
    for (int i = 0; i < sz; ++i) {
        cout << a[i] << " ";
    }
    cout << endl;

    sort(a, a + sz);

    cout << "Mang sau sx: ";
    for (int i = 0; i < sz; ++i) {
        cout << a[i] << " ";
    }
    cout << endl;

    return 0;
}

Output:

Mang trc sx: 7 3 0 6 10 5 
Mang sau sx: 0 3 5 6 7 10
  • Giải thích:
    • Với mảng C-style a, a tự bản thân nó là một con trỏ trỏ đến phần tử đầu tiên.
    • a + sz (với sz là số lượng phần tử) là con trỏ trỏ đến vị trí sau phần tử cuối cùng.
    • Cách sử dụng sort vẫn giống như với vector, chỉ là cách lấy iterator/con trỏ khác nhau.

Thực hành: Sắp xếp Giảm dần

Mặc định là tăng dần, nhưng chúng ta hoàn toàn có thể sắp xếp giảm dần bằng cách cung cấp một tiêu chí so sánh (comparison function) cho sort. sort có overload thứ hai nhận thêm một đối số là hàm so sánh:

sort(first_iterator, last_iterator, comparison_function);

Hàm so sánh này là một callable object (có thể là hàm, function object, hoặc lambda) nhận hai đối số (hai phần tử cùng kiểu với các phần tử trong phạm vi) và trả về true nếu phần tử đầu tiên được coi là "nhỏ hơn" phần tử thứ hai theo tiêu chí sắp xếp của bạn (tức là phần tử đầu tiên nên đứng trước phần tử thứ hai trong kết quả sắp xếp).

Đối với sắp xếp giảm dần, "nhỏ hơn" có nghĩa là "lớn hơn" theo giá trị thực.

Ví dụ 3: Sắp xếp Vector giảm dần bằng greater

C++ Standard Library đã cung cấp sẵn một số function object cho các phép so sánh phổ biến như greater.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

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

    cout << "Vector trc sx: ";
    for (int x : a) {
        cout << x << " ";
    }
    cout << endl;

    sort(a.begin(), a.end(), greater<int>());

    cout << "Vector sau sx: ";
    for (int x : a) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

Output:

Vector trc sx: 5 2 8 1 9 4 
Vector sau sx: 9 8 5 4 2 1
  • Giải thích:
    • greater<int>() là một function object. Khi được gọi với hai số a và b, nó trả về true nếu a > b.
    • Khi truyền greater<int>() làm đối số thứ ba cho sort, chúng ta đang yêu cầu sort sử dụng logic so sánh này: sort sẽ đặt a trước b nếu a > b, chính là sắp xếp giảm dần.
Ví dụ 4: Sắp xếp Vector giảm dần bằng Lambda Function

Lambda function (hàm ẩn danh) là một cách rất linh hoạt để định nghĩa hàm so sánh ngay tại chỗ.

#include <iostream>
#include <vector>
#include <algorithm>

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

    cout << "Vector trc sx: ";
    for (int x : a) {
        cout << x << " ";
    }
    cout << endl;

    sort(a.begin(), a.end(), [](int val1, int val2){
        return val1 > val2;
    });

    cout << "Vector sau sx: ";
    for (int x : a) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

Output:

Vector trc sx: 5 2 8 1 9 4 
Vector sau sx: 9 8 5 4 2 1
  • Giải thích:
    • [](int val1, int val2){ return val1 > val2; } là một lambda function.
    • [] là capture clause (trong ví dụ này rỗng vì không cần bắt biến từ môi trường xung quanh).
    • (int val1, int val2) là danh sách tham số.
    • { return val1 > val2; } là thân hàm.
    • Lambda này trả về true nếu val1 lớn hơn val2. Điều này nói với sort rằng nếu val1 > val2, thì val1 được coi là "nhỏ hơn" theo tiêu chí sắp xếp hiện tại và nên đứng trước val2 trong kết quả. Kết quả là sắp xếp giảm dần.

Lambda function đặc biệt hữu ích khi bạn cần một tiêu chí so sánh riêng cho một lần gọi sort cụ thể và không muốn tạo một hàm riêng hay function object phức tạp.

Thực hành: Sắp xếp các Đối tượng Tùy chỉnh (Custom Objects)

Đây là lúc sort thực sự thể hiện sự linh hoạt. Chúng ta có thể sắp xếp các struct hoặc class dựa trên một hoặc nhiều thuộc tính của chúng.

Ví dụ 5: Sắp xếp vector các struct theo tuổi

Giả sử chúng ta có một struct Nguoi và muốn sắp xếp danh sách người theo tuổi của họ.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

struct Nguoi {
    string ten;
    int tuoi;
};

int main() {
    vector<Nguoi> ds = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 35},
        {"David", 25}
    };

    cout << "DS trc sx:" << endl;
    for (const auto& x : ds) {
        cout << x.ten << " (" << x.tuoi << ")" << endl;
    }
    cout << endl;

    sort(ds.begin(), ds.end(), [](const Nguoi& a, const Nguoi& b){
        return a.tuoi < b.tuoi;
    });

    cout << "DS sau sx (tuoi tang):" << endl;
    for (const auto& x : ds) {
        cout << x.ten << " (" << x.tuoi << ")" << endl;
    }
    cout << endl;

    sort(ds.begin(), ds.end(), [](const Nguoi& a, const Nguoi& b){
        return a.tuoi > b.tuoi;
    });

    cout << "DS sau sx (tuoi giam):" << endl;
    for (const auto& x : ds) {
        cout << x.ten << " (" << x.tuoi << ")" << endl;
    }
    cout << endl;

    return 0;
}

Output:

DS trc sx:
Alice (30)
Bob (25)
Charlie (35)
David (25)

DS sau sx (tuoi tang):
Bob (25)
David (25)
Alice (30)
Charlie (35)

DS sau sx (tuoi giam):
Charlie (35)
Alice (30)
Bob (25)
David (25)
  • Giải thích:
    • Chúng ta tạo một struct Nguoi với ten và tuoi.
    • Lambda function được sử dụng để cung cấp logic so sánh. Lambda [](const Nguoi& a, const Nguoi& b){ return a.tuoi < b.tuoi; } so sánh hai đối tượng Nguoi dựa vào thuộc tính tuoi. Nó trả về true nếu tuổi của a nhỏ hơn tuổi của b, khiến sort đặt a trước b, cho kết quả sắp xếp tăng dần theo tuổi.
    • Lưu ý sử dụng const Nguoi& cho các tham số của lambda. Sử dụng tham chiếu (&) tránh việc sao chép đối tượng lớn (nếu có), và const đảm bảo rằng lambda không sửa đổi các đối tượng đang so sánh.
Ví dụ 6: Sắp xếp vector các struct theo nhiều tiêu chí (tuổi, rồi đến tên)

Thường thì chúng ta cần sắp xếp dựa trên một tiêu chí chính, và nếu hai phần tử bằng nhau theo tiêu chí chính, chúng ta dùng một tiêu chí phụ. Ví dụ, sắp xếp theo tuổi, nếu cùng tuổi thì sắp xếp theo tên.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

struct Nguoi {
    string ten;
    int tuoi;
};

int main() {
    vector<Nguoi> ds = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 35},
        {"David", 25}
    };

    cout << "DS trc sx:" << endl;
    for (const auto& x : ds) {
        cout << x.ten << " (" << x.tuoi << ")" << endl;
    }
    cout << endl;

    sort(ds.begin(), ds.end(), [](const Nguoi& a, const Nguoi& b){
        if (a.tuoi != b.tuoi) {
            return a.tuoi < b.tuoi;
        }
        return a.ten < b.ten;
    });

    cout << "DS sau sx (tuoi tang, ten tang):" << endl;
    for (const auto& x : ds) {
        cout << x.ten << " (" << x.tuoi << ")" << endl;
    }
    cout << endl;

    return 0;
}

Output:

DS trc sx:
Alice (30)
Bob (25)
Charlie (35)
David (25)

DS sau sx (tuoi tang, ten tang):
Bob (25)
David (25)
Alice (30)
Charlie (35)
  • Giải thích:
    • Lambda function kiểm tra if (a.tuoi != b.tuoi).
    • Nếu tuổi khác nhau, nó trả về a.tuoi < b.tuoi, ưu tiên sắp xếp theo tuổi.
    • Nếu tuổi giống nhau (phần else, ngầm định), nó trả về a.ten < b.ten, sử dụng tên làm tiêu chí phụ. string có toán tử < được định nghĩa để so sánh theo thứ tự từ điển.
    • Kết quả sẽ là: Bob (25), David (25), Alice (30), Charlie (35). Bob đứng trước David vì 'B' đứng trước 'D'.

Thực hành: Sắp xếp một Phạm vi con

Bạn không nhất thiết phải sắp xếp toàn bộ container. sort có thể sắp xếp bất kỳ phạm vi nào được định nghĩa bởi hai iterator hợp lệ.

Ví dụ 7: Sắp xếp chỉ một phần của Vector
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    vector<int> a = {10, 20, 5, 15, 30, 25, 0, 40};

    cout << "Vector trc sx pham vi con: ";
    for (int x : a) {
        cout << x << " ";
    }
    cout << endl;

    sort(a.begin() + 2, a.begin() + 6);

    cout << "Vector sau sx pham vi con (idx 2 den 5): ";
    for (int x : a) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

Output:

Vector trc sx pham vi con: 10 20 5 15 30 25 0 40 
Vector sau sx pham vi con (idx 2 den 5): 10 20 5 15 25 30 0 40
  • Giải thích:
    • a.begin() + 2 là iterator trỏ đến phần tử ở index 2 (số 5).
    • a.begin() + 6 là iterator trỏ đến vị trí sau phần tử ở index 5 (sau số 25).
    • sort chỉ tác động lên phạm vi từ index 2 đến 5. Các phần tử ở index 0, 1, 6, 7 vẫn giữ nguyên vị trí.
    • Kết quả sắp xếp phạm vi con {5, 15, 30, 25} thành {5, 15, 25, 30}. Vector cuối cùng sẽ là {10, 20, 5, 15, 25, 30, 0, 40}.

Thực hành: Sắp xếp Cặp (Pair)

Một tình huống phổ biến là khi bạn cần sắp xếp dữ liệu nhưng vẫn muốn giữ thông tin về vị trí gốc hoặc một thuộc tính khác. pair rất hữu ích trong trường hợp này.

Ví dụ 8: Sắp xếp các cặp (value, original_index)

Giả sử bạn có một danh sách các giá trị và muốn sắp xếp chúng, nhưng sau đó cần biết giá trị gốc đó ở vị trí nào trong danh sách ban đầu.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

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

    for (int i = 0; i < giaso.size(); ++i) {
        cap_val_idx.push_back({giaso[i], i});
    }

    cout << "Vector cap (gia tri, index) trc sx:" << endl;
    for (const auto& x : cap_val_idx) {
        cout << "(" << x.first << ", " << x.second << ") ";
    }
    cout << endl;

    sort(cap_val_idx.begin(), cap_val_idx.end());

    cout << "Vector cap (gia tri, index) sau sx:" << endl;
    for (const auto& x : cap_val_idx) {
        cout << "(" << x.first << ", " << x.second << ") ";
    }
    cout << endl;

    cout << "Cac gia tri goc theo thu tu da sx:" << endl;
    for (const auto& x : cap_val_idx) {
        cout << giaso[x.second] << " ";
    }
    cout << endl;

    return 0;
}

Output:

Vector cap (gia tri, index) trc sx:
(5, 0) (2, 1) (8, 2) (1, 3) (9, 4) (4, 5) 
Vector cap (gia tri, index) sau sx:
(1, 3) (2, 1) (4, 5) (5, 0) (8, 2) (9, 4) 
Cac gia tri goc theo thu tu da sx:
1 2 4 5 8 9
  • Giải thích:
    • Chúng ta tạo một vector mới chứa các pair<int, int>. Mỗi cặp lưu trữ giá trị gốc (x.first) và index ban đầu của nó (x.second).
    • Mặc định, pair đã có toán tử < được định nghĩa. Nó so sánh phần tử first trước. Nếu first bằng nhau, nó so sánh phần tử second. Điều này rất tiện lợi trong nhiều trường hợp.
    • Khi gọi sort mà không cung cấp hàm so sánh riêng, nó sẽ sử dụng toán tử < mặc định của pair, dẫn đến việc sắp xếp các cặp theo giá trị tăng dần (x.first). Nếu có hai cặp có cùng giá trị, chúng sẽ được sắp xếp theo index ban đầu (x.second).
    • Sau khi sắp xếp, chúng ta có thể duyệt qua vector các cặp đã sắp xếp và sử dụng x.second (index gốc) để truy cập giá trị tương ứng trong vector giaso ban đầu, in chúng ra theo thứ tự đã sắp xếp.

Bạn cũng có thể sử dụng lambda để sắp xếp các cặp theo tiêu chí khác, ví dụ sắp xếp giảm dần theo giá trị hoặc sắp xếp theo index gốc.

Tổng kết Thực hành

Qua các ví dụ trên, bạn đã thấy được sự linh hoạt và mạnh mẽ của sort. Nó không chỉ giới hạn ở việc sắp xếp các kiểu dữ liệu cơ bản mà còn làm việc hiệu quả với các cấu trúc dữ liệu phức tạp hơn và cho phép bạn định nghĩa tiêu chí sắp xếp riêng thông qua hàm so sánh.

  • Sử dụng sort(begin, end) để sắp xếp tăng dần mặc định.
  • Sử dụng sort(begin, end, comparison_function) để sắp xếp theo tiêu chí tùy chỉnh.
  • Lambda function là một cách tuyệt vời để cung cấp tiêu chí so sánh ngay tại chỗ, đặc biệt khi cần logic phức tạp hoặc dựa trên nhiều thuộc tính.
  • Nhớ include <algorithm> và các header cần thiết khác (<vector>, <iostream>, <string>, <utility>, <functional>).

sort là một công cụ cốt lõi trong bộ công cụ của lập trình viên C++. Việc thành thạo nó sẽ giúp bạn giải quyết các bài toán sắp xếp một cách hiệu quả và gọn gàng. Hãy tự mình thử thay đổi các ví dụ, sắp xếp các kiểu dữ liệu khác, hoặc đặt ra các bài toán sắp xếp phức tạp hơn để thực hành nhé!

Comments

There are no comments at the moment.