Bài 22.5: Bài tập thực hành tối ưu sắp xếp trong C++

Chào mừng các bạn trở lại với series blog của chúng ta về C++! Trong các bài trước, chúng ta có thể đã lướt qua hoặc sử dụng các kỹ thuật sắp xếp cơ bản. Tuy nhiên, việc sắp xếp dữ liệu là một tác vụ cực kỳ phổ biến và quan trọng trong lập trình. Nó không chỉ giúp dữ liệu dễ đọc, dễ tìm kiếm hơn mà còn là bước tiền xử lý cần thiết cho rất nhiều thuật toán khác.

Trong C++, chúng ta có một công cụ vô cùng mạnh mẽ và được tối ưu hóa cao để sắp xếp: các thuật toán trong Thư viện Chuẩn (Standard Library), đặc biệt là sort. Nhưng làm thế nào để sử dụng chúng một cách hiệu quả nhất? Bài viết này sẽ tập trung vào các bài tập thực hành và kỹ thuật tối ưu khi làm việc với sắp xếp trong C++, vượt ra ngoài việc chỉ đơn thuần gọi sort.

Chúng ta sẽ không đi sâu vào cách triển khai chi tiết của các thuật toán sắp xếp (như QuickSort, MergeSort, HeapSort), mà sẽ tập trung vào cách sử dụng các công cụ sẵn có trong C++ STL một cách thông minh và hiệu quả.

Công Cụ Sắp Xếp Cơ Bản: `sort`

Trái tim của việc sắp xếp trong C++ STL là hàm sort, được định nghĩa trong header <algorithm>. Hàm này thường được triển khai dựa trên Introsort, một thuật toán lai (hybrid) kết hợp QuickSort, HeapSort và InsertionSort để đảm bảo hiệu suất tốt trong hầu hết các trường hợp.

sort yêu cầu các iterator truy cập ngẫu nhiên (random-access iterators), điều này có nghĩa là nó hoạt động tốt với vector, deque, array, và mảng C-style thông thường.

Cú pháp cơ bản của sort: sort(first, last); hoặc sort(first, last, compare);

Trong đó:

first: Một iterator trỏ đến phần tử đầu tiên của dải cần sắp xếp.
last: Một iterator trỏ đến sau phần tử cuối cùng của dải cần sắp xếp (phần tử tại last không được bao gồm).
compare: (Tùy chọn) Một đối tượng hàm (function object), hàm, hoặc lambda để định nghĩa tiêu chí so sánh. Mặc định là less<> (sắp xếp tăng dần).

Hãy bắt đầu với một ví dụ đơn giản nhất về cách sử dụng sort:

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

int main() {
    vector<int> so = {5, 2, 8, 1, 9, 4};
    sort(so.begin(), so.end());
    cout << "Vector sau khi sap xep (tang dan): ";
    for (int x : so) {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

Vector sau khi sap xep (tang dan): 1 2 4 5 8 9

Giải thích:

Chúng ta khai báo một vector<int>.
sort(so.begin(), so.end()); gọi hàm sắp xếp cho toàn bộ dải từ so.begin() (phần tử đầu tiên) đến so.end() (sau phần tử cuối cùng).
Mặc định, sort sử dụng phép so sánh operator< hoặc less, nên nó sắp xếp tăng dần.

Tuỳ Chỉnh Tiêu Chí Sắp Xếp với `compare`

Một trong những khả năng mạnh mẽ của sort là khả năng tùy chỉnh tiêu chí sắp xếp bằng cách cung cấp đối số compare. Đối số này phải là một hàm hoặc đối tượng hàm có thể gọi được, nhận hai đối số cùng kiểu với các phần tử đang sắp xếp, và trả về bool. Kết quả true nghĩa là đối số thứ nhất được coi là "nhỏ hơn" hoặc "nên đứng trước" đối số thứ hai.

Sắp xếp Giảm Dần

Để sắp xếp giảm dần, chúng ta cần một hàm so sánh trả về true nếu phần tử thứ nhất lớn hơn phần tử thứ hai. C++ STL cung cấp sẵn greater<>.

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

int main() {
    vector<int> so = {5, 2, 8, 1, 9, 4};
    sort(so.begin(), so.end(), greater<int>());
    cout << "Vector sau khi sap xep (giam dan): ";
    for (int x : so) {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

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

Giải thích:

Chúng ta truyền greater<int>() làm đối số thứ ba. greater<int>() là một đối tượng hàm mà khi được gọi với hai số nguyên a và b, nó trả về a > b. Điều này đảo ngược thứ tự so sánh, dẫn đến sắp xếp giảm dần.

Sắp xếp Đối Tượng Tùy Chỉnh

Đây là lúc compare thực sự thể hiện sức mạnh. Chúng ta thường cần sắp xếp các cấu trúc hoặc lớp dựa trên một hoặc nhiều thành viên của chúng. Lambda expression là một cách thanh lịch và tiện lợi để làm điều này ngay tại chỗ.

Giả sử chúng ta có một cấu trúc Nguoi:

#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}
    };

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

    cout << "Danh sach sau khi sap xep theo tuoi (tang dan):" << endl;
    for (const auto& x : ds) {
        cout << x.ten << " (" << x.tuoi << ") ";
    }
    cout << endl;
    return 0;
}

Danh sach sau khi sap xep theo tuoi (tang dan):
Bob (25) David (25) Alice (30) Charlie (35)

Giải thích:

Chúng ta định nghĩa một cấu trúc Nguoi.
Chúng ta sử dụng một lambda expression [](const Nguoi& a, const Nguoi& b) { return a.tuoi < b.tuoi; } làm hàm so sánh.
Lambda này nhận hai đối tượng Nguoi (truyền bằng tham chiếu hằng để hiệu quả) và trả về true nếu tuổi của a nhỏ hơn tuổi của b. Điều này đảm bảo sort sắp xếp các đối tượng Nguoi dựa trên thuộc tính tuoi theo thứ tự tăng dần.

Bạn có thể thay đổi logic trong lambda để sắp xếp theo tên, theo tuổi giảm dần, hoặc theo nhiều tiêu chí (ví dụ: theo tuổi, nếu tuổi bằng nhau thì 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}
    };

    // Sap xep theo tuoi giam dan
    sort(ds.begin(), ds.end(), [](const Nguoi& a, const Nguoi& b) {
        return a.tuoi > b.tuoi;
    });

    cout << "Danh sach sau khi sap xep theo tuoi (giam dan):" << endl;
    for (const auto& x : ds) {
        cout << x.ten << " (" << x.tuoi << ") ";
    }
    cout << endl;

    // Khoi tao lai du lieu de sap xep voi tieu chi khac
    ds = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 35},
        {"David", 25}
    };

    // Sap xep theo tuoi tang dan, neu cung tuoi thi theo ten tang dan
    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 << "Danh sach sau khi sap xep theo tuoi (tang dan), ten (tang dan):" << endl;
    for (const auto& x : ds) {
        cout << x.ten << " (" << x.tuoi << ") ";
    }
    cout << endl;

    return 0;
}

Danh sach sau khi sap xep theo tuoi (giam dan):
Charlie (35) Alice (30) Bob (25) David (25)
Danh sach sau khi sap xep theo tuoi (tang dan), ten (tang dan):
Bob (25) David (25) Alice (30) Charlie (35)

Kỹ thuật này là cực kỳ quan trọng và được sử dụng rất thường xuyên trong thực tế. Việc nắm vững cách viết lambda so sánh giúp bạn sắp xếp hầu hết mọi cấu trúc dữ liệu tùy chỉnh.

Sắp Xếp Chỉ Một Phần Của Container

Đôi khi, chúng ta không cần sắp xếp toàn bộ container. sort cho phép bạn chỉ định một dải con (sub-range) bằng cách truyền các iterator đến điểm bắt đầu và điểm kết thúc của dải đó.

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

int main() {
    vector<int> v1 = {10, 20, 1, 8, 15, 5, 25, 12};
    sort(v1.begin() + 2, v1.begin() + 5);
    cout << "Vector sau khi sap xep phan giua (vi du 1): ";
    for (int x : v1) {
        cout << x << " ";
    }
    cout << endl;

    vector<int> v2 = {10, 5, 20, 1, 15, 8, 25, 12};
    sort(v2.begin() + 1, v2.begin() + 5);
    cout << "Vector sau khi sap xep phan giua (vi du 2): ";
    for (int x : v2) {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

Vector sau khi sap xep phan giua (vi du 1): 10 20 1 8 15 5 25 12
Vector sau khi sap xep phan giua (vi du 2): 10 1 5 15 20 8 25 12

Giải thích:

Trong ví dụ thứ hai, chúng ta sử dụng v2.begin() + 1 và v2.begin() + 5 để xác định dải con.
begin() + 1 là iterator tới phần tử thứ hai (giá trị 5).
begin() + 5 là iterator tới phần tử thứ sáu (giá trị 8).
sort sẽ sắp xếp dải bao gồm các phần tử từ begin() + 1 đến trước begin() + 5, tức là các phần tử tại index 1, 2, 3, 4 (giá trị 5, 20, 1, 15). Dải này sau khi sắp xếp tăng dần sẽ là {1, 5, 15, 20}.
Kết quả là vector v2 trở thành {10, 1, 5, 15, 20, 8, 25, 12}. Kỹ thuật này rất hữu ích khi bạn chỉ cần sắp xếp một phần dữ liệu lớn mà không muốn tốn thời gian và tài nguyên cho toàn bộ tập dữ liệu.

Lưu Ý về Tính Ổn Định: `stable_sort`

sort thường không đảm bảo tính ổn định. Điều này có nghĩa là nếu có hai phần tử được coi là "bằng nhau" theo tiêu chí so sánh (!(a < b) và !(b < a)), thì thứ tự tương đối ban đầu của chúng có thể bị thay đổi sau khi sắp xếp.

Ví dụ với cấu trúc Nguoi ở trên, nếu bạn sắp xếp theo tuổi, hai người cùng tuổi có thể đổi chỗ cho nhau. Nếu bạn cần giữ nguyên thứ tự ban đầu của các phần tử bằng nhau, bạn cần sử dụng stable_sort.

stable_sort đảm bảo tính ổn định, nhưng có thể kém hiệu quả hơn sort về thời gian chạy hoặc bộ nhớ trong một số trường hợp (thường là O(N log^2 N) hoặc O(N log N) với bộ nhớ phụ O(N)).

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

struct Nguoi {
    string ten;
    int tuoi;
    int tt_goc;
};

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

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

    cout << "sort (khong on dinh) theo tuoi:" << endl;
    for (const auto& x : ds_k_on_dinh) {
        cout << x.ten << " (" << x.tuoi << ", goc: " << x.tt_goc << ") ";
    }
    cout << endl;

    cout << "--------------------" << endl;

    vector<Nguoi> ds_on_dinh = ds;
    stable_sort(ds_on_dinh.begin(), ds_on_dinh.end(), [](const Nguoi& a, const Nguoi& b) {
        return a.tuoi < b.tuoi;
    });

    cout << "stable_sort (on dinh) theo tuoi:" << endl;
    for (const auto& x : ds_on_dinh) {
        cout << x.ten << " (" << x.tuoi << ", goc: " << x.tt_goc << ") ";
    }
    cout << endl;
    return 0;
}

sort (khong on dinh) theo tuoi:
Bob (25, goc: 0) David (25, goc: 1) Alice (30, goc: 2) Charlie (35, goc: 3)
--------------------
stable_sort (on dinh) theo tuoi:
Bob (25, goc: 0) David (25, goc: 1) Alice (30, goc: 2) Charlie (35, goc: 3)

Giải thích:

Chúng ta thêm trường tt_goc để dễ dàng nhận biết thứ tự ban đầu.
Khi sắp xếp bằng sort, thứ tự của "Bob" (original 0) và "David" (original 1) có thể hoán đổi vì cả hai đều có tuổi 25. Ví dụ trên cho thấy thứ tự giữ nguyên, nhưng nó không được đảm bảo và có thể khác trên các trình biên dịch hoặc hệ thống khác.
Khi sắp xếp bằng stable_sort, thứ tự của "Bob" và "David" luôn được giữ nguyên như trong vector gốc, bởi vì chúng được coi là bằng nhau theo tiêu chí so sánh (tuổi).

Sử dụng stable_sort khi: Thứ tự ban đầu của các phần tử bằng nhau là quan trọng đối với kết quả cuối cùng của bạn. Sử dụng sort khi: Tính ổn định không quan trọng, để có hiệu suất tiềm năng tốt hơn.

Tối Ưu Hóa cho Các Bài Toán "Top K" hoặc Phần Tử Thứ N

Một trong những sai lầm phổ biến khi đối mặt với bài toán "tìm K phần tử nhỏ nhất/lớn nhất" hoặc "tìm phần tử trung vị (median)" là sắp xếp toàn bộ tập dữ liệu rồi mới lấy K phần tử đầu tiên hoặc phần tử ở vị trí mong muốn. Điều này là không cần thiết và kém hiệu quả nếu K nhỏ hơn nhiều so với tổng số phần tử.

C++ STL cung cấp các thuật toán chuyên biệt cho các bài toán này, hiệu quả hơn nhiều so với việc sắp xếp toàn bộ: partial_sort và nth_element. Đây là những kỹ thuật tối ưu quan trọng cần biết.

Tìm K Phần Tử Nhỏ Nhất/Lớn Nhất: `partial_sort`

partial_sort(first, middle, last) sắp xếp các phần tử trong dải [first, last) sao cho các phần tử trong dải con [first, middle) được sắp xếp và là các phần tử nhỏ nhất trong toàn bộ dải [first, last). Các phần tử còn lại trong dải [middle, last) không được sắp xếp theo bất kỳ thứ tự cụ thể nào.

Thời gian chạy của partial_sort thường là O(N log K), trong đó N là tổng số phần tử và K là số phần tử bạn muốn sắp xếp ở đầu (middle - first). So với O(N log N) của sort khi N lớn hơn nhiều so với K, đây là một sự cải thiện đáng kể.

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

int main() {
    vector<int> so = {10, 5, 20, 1, 15, 8, 25, 12};
    int k = 3;

    partial_sort(so.begin(), so.begin() + k, so.end());

    cout << k << " phan tu nho nhat la: ";
    for (int i = 0; i < k; ++i) {
        cout << so[i] << " ";
    }
    cout << endl;

    cout << "Vector sau partial_sort: ";
    for (int x : so) {
        cout << x << " ";
    }
    cout << endl;

    vector<int> so_lon = {10, 5, 20, 1, 15, 8, 25, 12};
    partial_sort(so_lon.begin(), so_lon.begin() + k, so_lon.end(), greater<int>());

    cout << k << " phan tu lon nhat la: ";
    for (int i = 0; i < k; ++i) {
        cout << so_lon[i] << " ";
    }
    cout << endl;
    return 0;
}

3 phan tu nho nhat la: 1 5 8
Vector sau partial_sort: 1 5 8 10 15 20 25 12
3 phan tu lon nhat la: 25 20 15

Giải thích:

partial_sort(so.begin(), so.begin() + k, so.end());
- first: so.begin()
- middle: so.begin() + k (iterator đến vị trí sau phần tử thứ k - tức là index k)
- last: so.end()
Hàm đảm bảo 3 phần tử đầu tiên của vector (so[0], so[1], so[2]) sẽ là 3 phần tử nhỏ nhất trong toàn bộ vector và chúng được sắp xếp tăng dần.

Tìm Phần Tử Thứ N: `nth_element`

nth_element(first, nth, last) sắp xếp các phần tử trong dải [first, last) sao cho phần tử tại vị trí nth (iterator nth) là phần tử mà nó sẽ đứng ở vị trí đó nếu toàn bộ dải được sắp xếp. Ngoài ra, tất cả các phần tử trước vị trí nth đều nhỏ hơn hoặc bằng phần tử tại nth, và tất cả các phần tử sau vị trí nth đều lớn hơn hoặc bằng phần tử tại nth.

Điểm mấu chốt là nth_element chỉ đảm bảo vị trí của phần tử tại nth và phân vùng các phần tử còn lại tương ứng; các phần tử trước nth không nhất thiết phải được sắp xếp với nhau, và các phần tử sau nth cũng vậy.

Lợi ích cực lớn của nth_element là hiệu suất trung bình của nó là tuyến tính, O(N), trong đó N là số phần tử. Điều này làm cho nó trở thành công cụ tối ưu nhất để tìm trung vị, tứ phân vị, hoặc bất kỳ phần tử thứ k nào mà không cần sắp xếp toàn bộ dữ liệu.

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

int main() {
    vector<int> so = {10, 5, 20, 1, 15, 8, 25, 12};
    int n = 4; // Phan tu nho thu 4

    nth_element(so.begin(), so.begin() + n - 1, so.end());

    cout << "Phan tu nho thu " << n << " la: " << so[n - 1] << endl;

    cout << "Vector sau nth_element (tim phan tu nho thu " << n << "): ";
    for (int x : so) {
        cout << x << " ";
    }
    cout << endl;

    vector<int> so_lon = {10, 5, 20, 1, 15, 8, 25, 12};
    int k_max = 3; // Phan tu lon thu 3
    int vi_tri = so_lon.size() - k_max;

    nth_element(so_lon.begin(), so_lon.begin() + vi_tri, so_lon.end());

    cout << "Phan tu lon thu " << k_max << " la: " << so_lon[vi_tri] << endl;

    return 0;
}

Phan tu nho thu 4 la: 8
Vector sau nth_element (tim phan tu nho thu 4): 5 1 8 10 15 20 25 12
Phan tu lon thu 3 la: 15

Giải thích:

Để tìm phần tử nhỏ thứ N, chúng ta gọi nth_element với nth là so.begin() + N - 1.
Để tìm phần tử lớn thứ K, chúng ta gọi nth_element với nth là so.begin() + (so.size() - K).
nth_element là lựa chọn tối ưu khi bạn chỉ cần biết giá trị của phần tử thứ K (ví dụ: trung vị) mà không cần toàn bộ danh sách được sắp xếp.

Comments

There are no comments at the moment.