Bài 21.1: Hàm sort và stable_sort trong C++

Chào mừng trở lại với series blog C++ của FullhouseDev! Trong thế giới lập trình, việc tổ chức dữ liệu là một nhiệm vụ cực kỳ quan trọng. Và khi nói đến việc tổ chức dữ liệu bằng cách sắp xếp, Standard Template Library (STL) của C++ cung cấp cho chúng ta những công cụ mạnh mẽ và hiệu quả. Hôm nay, chúng ta sẽ cùng đi sâu vào hai "ngôi sao" trong lĩnh vực này: hàm sort và hàm stable_sort.

Cả hai hàm này đều nằm trong header <algorithm> và được sử dụng để sắp xếp các phần tử trong một phạm vi (range). Tuy nhiên, chúng có một sự khác biệt quan trọng mà việc hiểu rõ sẽ giúp bạn đưa ra lựa chọn đúng đắn cho bài toán của mình.

Hãy cùng bắt đầu!

1. Hàm `sort`: "Ngựa chiến" mặc định

sort là hàm sắp xếp tổng quát và được sử dụng phổ biến nhất trong C++. Nó sắp xếp các phần tử trong một phạm vi [first, last) theo thứ tự tăng dần (mặc định) hoặc theo một tiêu chí tùy chỉnh mà bạn cung cấp.

Đặc điểm nổi bật:

Hiệu suất cao: sort thường được triển khai bằng các thuật toán lai (hybrid algorithms) như Introsort (kết hợp QuickSort, HeapSort, và InsertionSort) để đạt được hiệu suất tốt nhất trong hầu hết các trường hợp. Độ phức tạp thời gian trung bình và xấu nhất thường là O(N log N), với N là số phần tử cần sắp xếp.
Tại chỗ (In-place): Nó thường sắp xếp ngay trên dữ liệu gốc, yêu cầu không gian bộ nhớ phụ O(1) (hoặc O(log N) tùy triển khai cụ thể).
Không ổn định (Unstable): Đây là điểm cốt lõi cần lưu ý. sort không đảm bảo giữ nguyên thứ tự tương đối ban đầu của các phần tử được coi là bằng nhau theo tiêu chí sắp xếp.

Cách sử dụng cơ bản:

Hàm sort có hai dạng chính:

Sắp xếp tăng dần mặc định:
```
void sort( RandomAccessIterator first, RandomAccessIterator last );
```
Sắp xếp phạm vi [first, last) sử dụng toán tử < để so sánh.
Sắp xếp với tiêu chí tùy chỉnh:
```
void sort( RandomAccessIterator first, RandomAccessIterator last, Compare comp );
```
Sắp xếp phạm vi [first, last) sử dụng hàm so sánh comp. comp là một hàm (hoặc function object, lambda) nhận hai đối số và trả về true nếu đối số thứ nhất nên đứng trước đối số thứ hai.

Lưu ý: sort yêu cầu các iterator phải là Random Access Iterator (ví dụ: vector, deque, mảng C kiểu cũ). Nó không hoạt động trực tiếp với list (vì list chỉ cung cấp Bidirectional Iterator).

Các ví dụ minh hoạ với `sort`:

Ví dụ 1: Sắp xếp vector số nguyên tăng dần

Đây là trường hợp sử dụng đơn giản nhất, sử dụng tiêu chí so sánh mặc định (<).

#include <iostream>
#include <vector>
#include <algorithm> // Can include <numeric> for iota but <algorithm> is enough for sort

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

    cout << "Vector truoc khi sort: ";
    for (int n : numbers) {
        cout << n << " ";
    }
    cout << endl;

    // Goi sort de sap xep tu numbers.begin() den numbers.end()
    sort(numbers.begin(), numbers.end());

    cout << "Vector sau khi sort (tang dan):  ";
    for (int n : numbers) {
        cout << n << " ";
    }
    cout << endl;

    return 0;
}

Giải thích: Chúng ta khai báo một vector<int>. Lệnh sort(numbers.begin(), numbers.end()); sẽ sắp xếp các phần tử trong vector từ vị trí bắt đầu (begin()) đến ngay trước vị trí kết thúc (end()). Vì không có hàm so sánh tùy chỉnh, nó sử dụng toán tử < mặc định, dẫn đến kết quả sắp xếp tăng dần.

Ví dụ 2: Sắp xếp vector số nguyên giảm dần

Chúng ta cần cung cấp một hàm so sánh tùy chỉnh. Có thể sử dụng greater<int>() hoặc một lambda expression.

#include <iostream>
#include <vector>
#include <algorithm> // For sort
#include <functional> // For greater

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

    cout << "Vector truoc khi sort: ";
    for (int n : numbers) {
        cout << n << " ";
    }
    cout << endl;

    // Goi sort voi comparator greater de sap xep giam dan
    sort(numbers.begin(), numbers.end(), greater<int>());

    cout << "Vector sau khi sort (giam dan): ";
    for (int n : numbers) {
        cout << n << " ";
    }
    cout << endl;

    return 0;
}

Giải thích: Ở đây, chúng ta truyền greater<int>() làm đối số thứ ba cho sort. greater<int>() là một function object được cung cấp bởi STL, nó trả về true nếu đối số thứ nhất lớn hơn đối số thứ hai, do đó thực hiện sắp xếp giảm dần.

Ví dụ 3: Sắp xếp cấu trúc dữ liệu tùy chỉnh (minh họa tính không ổn định)

Giả sử chúng ta có danh sách sinh viên và muốn sắp xếp họ dựa trên điểm số.

#include <iostream>
#include <vector>
#include <algorithm> // For sort
#include <string>

struct Student {
    string name;
    int score;
    int id; // De theo doi thu tu ban dau
};

int main() {
    vector<Student> students = {
        {"Alice", 85, 101}, // Alice xuat hien truoc Charlie ban dau
        {"Bob", 92, 102},
        {"Charlie", 85, 103},
        {"David", 78, 104}
    };

    cout << "Danh sach sinh vien truoc khi sort:" << endl;
    for (const auto& s : students) {
        cout << s.name << " (" << s.score << ", id:" << s.id << ") ";
    }
    cout << endl;

    // Sap xep theo diem tang dan su dung lambda
    sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
        return a.score < b.score; // Ham so sanh: sap xep theo diem
    });

    cout << "Danh sach sinh vien sau khi sort theo diem (unstable):" << endl;
    for (const auto& s : students) {
        cout << s.name << " (" << s.score << ", id:" << s.id << ") ";
    }
    cout << endl;

    return 0;
}

Giải thích: Chúng ta định nghĩa struct Student và tạo một vector chứa các đối tượng Student. Hàm sort được gọi với một lambda expression làm comparator. Lambda này so sánh hai sinh viên dựa trên trường score. Output có thể sẽ là: David (78, id:104) Alice (85, id:101) Charlie (85, id:103) Bob (92, id:102) hoặc David (78, id:104) Charlie (85, id:103) Alice (85, id:101) Bob (92, id:102)

Lưu ý quan trọng: Alice và Charlie đều có điểm là 85. Trong dữ liệu gốc, Alice (id 101) đứng trước Charlie (id 103). Tuy nhiên, sau khi dùng sort, không có gì đảm bảo rằng Alice vẫn sẽ đứng trước Charlie trong danh sách kết quả. Vị trí tương đối của chúng có thể bị hoán đổi bởi thuật toán sort. Đây chính là minh họa cho tính không ổn định.

2. Hàm `stable_sort`: Giữ nguyên thứ tự tương đối

Trong nhiều trường hợp, việc giữ nguyên thứ tự ban đầu của các phần tử "bằng nhau" là rất quan trọng. Đây chính là lúc stable_sort tỏa sáng.

Đặc điểm nổi bật:

Ổn định (Stable): Đây là điểm khác biệt then chốt. stable_sort đảm bảo rằng nếu hai phần tử được coi là bằng nhau theo tiêu chí sắp xếp, thì thứ tự tương đối của chúng trong dãy kết quả sẽ giống hệt thứ tự ban đầu của chúng trong dãy đầu vào.
Độ phức tạp thời gian: Thường có độ phức tạp thời gian là O(N log² N). Tuy nhiên, nếu có đủ không gian bộ nhớ phụ, nó có thể đạt được O(N log N).
Độ phức tạp không gian: Có thể yêu cầu không gian bộ nhớ phụ lên tới O(N) để đảm bảo tính ổn định.

Cách sử dụng cơ bản:

Tương tự như sort, stable_sort cũng có hai dạng:

Sắp xếp tăng dần ổn định (mặc định):
```
void stable_sort( RandomAccessIterator first, RandomAccessIterator last );
```
Sắp xếp ổn định phạm vi [first, last) sử dụng toán tử <.
Sắp xếp ổn định với tiêu chí tùy chỉnh:
```
void stable_sort( RandomAccessIterator first, RandomAccessIterator last, Compare comp );
```
Sắp xếp ổn định phạm vi [first, last) sử dụng hàm so sánh comp.

Lưu ý: Giống như sort, stable_sort cũng yêu cầu Random Access Iterator.

Ví dụ minh hoạ với `stable_sort`:

Hãy sử dụng lại ví dụ về sinh viên để thấy rõ sự khác biệt.

Ví dụ 4: Sắp xếp cấu trúc dữ liệu tùy chỉnh (minh họa tính ổn định)

#include <iostream>
#include <vector>
#include <algorithm> // For stable_sort
#include <string>

struct Student {
    string name;
    int score;
    int id; // De theo doi thu tu ban dau
};

int main() {
    vector<Student> students = {
        {"Alice", 85, 101}, // Alice xuat hien truoc Charlie ban dau
        {"Bob", 92, 102},
        {"Charlie", 85, 103}, // Charlie xuat hien sau Alice ban dau
        {"David", 78, 104}
    };

    cout << "Danh sach sinh vien truoc khi stable_sort:" << endl;
    for (const auto& s : students) {
        cout << s.name << " (" << s.score << ", id:" << s.id << ") ";
    }
    cout << endl;

    // Sap xep theo diem tang dan su dung stable_sort va lambda
    stable_sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
        return a.score < b.score; // Ham so sanh: sap xep theo diem
    });

    cout << "Danh sach sinh vien sau khi stable_sort theo diem (stable):" << endl;
    for (const auto& s : students) {
        cout << s.name << " (" << s.score << ", id:" << s.id << ") ";
    }
    cout << endl;

    return 0;
}

Giải thích: Code này tương tự như ví dụ 3, nhưng chúng ta đã thay thế sort bằng stable_sort. Comparator (lambda) vẫn chỉ so sánh theo điểm số (score).

Output sẽ là: David (78, id:104) Alice (85, id:101) Charlie (85, id:103) Bob (92, id:102)

Sự khác biệt quan trọng: Dù Alice (id 101) và Charlie (id 103) có cùng điểm số 85, thứ tự tương đối của họ đã được bảo toàn so với danh sách ban đầu. Alice xuất hiện trước Charlie trong input, và cô ấy vẫn xuất hiện trước Charlie trong output sau khi stable_sort được áp dụng. Đây chính là ý nghĩa của tính ổn định.

3. Khi nào sử dụng `sort` và khi nào sử dụng `stable_sort`?

Việc lựa chọn giữa sort và stable_sort phụ thuộc vào yêu cầu cụ thể của bài toán:

Sử dụng sort khi:
- Bạn chỉ cần các phần tử được sắp xếp theo một tiêu chí nào đó.
- Hiệu suất (tốc độ và bộ nhớ) là ưu tiên hàng đầu.
- Việc giữ nguyên thứ tự ban đầu của các phần tử bằng nhau không quan trọng.
Sử dụng stable_sort khi:
- Bạn cần các phần tử được sắp xếp theo một tiêu chí.
- Đồng thời, bạn bắt buộc phải giữ nguyên thứ tự tương đối ban đầu của các phần tử được coi là bằng nhau theo tiêu chí sắp xếp đó.
- Bạn chấp nhận đánh đổi một chút về hiệu suất hoặc sử dụng thêm bộ nhớ phụ để đảm bảo tính ổn định.

Một trường hợp phổ biến cần dùng stable_sort là khi bạn thực hiện sắp xếp theo nhiều tiêu chí liên tiếp. Ví dụ, sắp xếp danh sách sinh viên theo lớp (sử dụng stable_sort), sau đó sắp xếp tiếp trong mỗi lớp theo tên (sử dụng stable_sort). Nhờ tính ổn định, thứ tự sinh viên trong cùng một lớp vẫn được giữ nguyên khi sắp xếp theo tên. Nếu dùng sort ở bước thứ hai, thứ tự theo lớp có thể bị phá vỡ.

Bài tập ví dụ: C++ Bài 10.A1: Gộp mảng

Cho hai dãy số nguyên đã được sắp xếp không giảm \(a\) và \(b\) lần lượt có \(n\) và \(m\) phần tử. Hãy ghép chúng thành dãy \(c\) được bố trí theo thứ tự không giảm.

INPUT FORMAT

Dòng đầu tiên chứa số nguyên \(n\) và \(m\) ( \( 1 \leq n,m \leq 10^5\)).

Dòng thứ hai chứa \(n\) số nguyên, mỗi số các nhau một dấu cách \((1 \leq a_i < 10^{9})\).

Dòng thứ ba chứa \(m\) số nguyên, mỗi số các nhau một dấu cách \((1 \leq b_i < 10^{9})\)

OUTPUT FORMAT

In ra dãy \(c\) được bố trí theo thứ tự không giảm.

Ví dụ:

Input

5 6
1 3 6 8 10
2 6 7 12 14 15

Output

1 2 3 6 6 7 8 10 12 14 15

Giải thích ví dụ mẫu

Ví dụ 1:
- Dữ liệu: a = [1, 3, 6, 8, 10], b = [2, 6, 7, 12, 14, 15]
- Giải thích: Ghép hai dãy đã sắp xếp a và b để tạo thành dãy c = [1, 2, 3, 6, 6, 7, 8, 10, 12, 14, 15] vẫn được sắp xếp không giảm.

<br>

Hiểu rõ bài toán: Ta có hai mảng a và b đã được sắp xếp theo thứ tự không giảm. Yêu cầu là tạo ra một mảng c chứa tất cả các phần tử của a và b, và mảng c này cũng phải được sắp xếp theo thứ tự không giảm.
Nhận biết tính chất quan trọng: Vì cả hai mảng đầu vào (a và b) đã được sắp xếp, ta có thể tận dụng tính chất này để gộp chúng một cách hiệu quả mà không cần sắp xếp lại toàn bộ mảng kết quả từ đầu (như cách đơn giản là nối a và b rồi sort).
Thuật toán gộp (Merge Algorithm - Tư duy hai con trỏ):
- Ý tưởng chính: Ta sẽ duyệt qua cả hai mảng a và b đồng thời. Tại mỗi bước, ta so sánh phần tử hiện tại đang xét của mảng a với phần tử hiện tại đang xét của mảng b. Phần tử nào nhỏ hơn (hoặc bằng) sẽ được đưa vào mảng kết quả trước. Sau đó, ta tiến con trỏ (hoặc chỉ số) của mảng chứa phần tử vừa được đưa vào.
- Cụ thể:
  - Sử dụng hai con trỏ (hoặc chỉ số mảng), một cho mảng a (gọi là i) và một cho mảng b (gọi là j), ban đầu cả hai đều ở vị trí đầu tiên (chỉ số 0).
  - Sử dụng một con trỏ/chỉ số khác cho mảng kết quả (gọi là k), ban đầu cũng ở vị trí 0.
  - Trong khi cả i chưa hết mảng a ( i < n) và j chưa hết mảng b (j < m):
    - So sánh phần tử a[i] và b[j].
    - Nếu a[i] <= b[j], đưa a[i] vào mảng kết quả tại vị trí k, rồi tăng i lên 1.
    - Ngược lại (nếu b[j] < a[i]), đưa b[j] vào mảng kết quả tại vị trí k, rồi tăng j lên 1.
    - Sau khi đưa một phần tử vào mảng kết quả, luôn tăng k lên 1.
  - Sau khi vòng lặp trên kết thúc, có thể một trong hai mảng a hoặc b vẫn còn các phần tử chưa được đưa vào mảng kết quả (vì mảng kia đã hết trước). Vì các phần tử còn lại này đã lớn hơn tất cả các phần tử của mảng kia đã được đưa vào, ta chỉ việc sao chép tất cả các phần tử còn lại của mảng chưa hết vào cuối mảng kết quả.
  - Nếu a còn phần tử (i < n), sao chép a[i] đến hết vào mảng kết quả.
  - Nếu b còn phần tử (j < m), sao chép b[j] đến hết vào mảng kết quả.
Sử dụng thư viện chuẩn C++ (std):
- Để lưu trữ các dãy số, cách tốt nhất trong C++ là sử dụng vector.
- Đọc dữ liệu vào hai vector<int> cho a và b.
- Tạo một vector<int> cho kết quả c với kích thước là n + m.
- Quan trọng nhất: Thư viện chuẩn C++ cung cấp một hàm có sẵn thực hiện chính xác thuật toán gộp hai dãy đã sắp xếp này: merge. Đây là cách ngắn gọn và hiệu quả nhất để làm điều này trong C++.
- Hàm merge nhận các iterator chỉ định phạm vi của hai dãy đầu vào và một iterator chỉ định vị trí bắt đầu ghi kết quả.
- Bạn sẽ gọi merge với các iterator a.begin(), a.end(), b.begin(), b.end(), và c.begin().
Các bước thực hiện sử dụng std:
- Include các header cần thiết: <iostream>, <vector>, <algorithm>.
- Đọc n và m.
- Khai báo và đọc dữ liệu vào hai vector<int>: vector<int> a(n); và vector<int> b(m);. Dùng vòng lặp để đọc từng phần tử.
- Khai báo vector<int> c(n + m); cho mảng kết quả.
- Sử dụng merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); để thực hiện việc gộp.
- In ra các phần tử của c, cách nhau bằng dấu cách.
Lưu ý về hiệu quả: Cách gộp sử dụng thuật toán hai con trỏ hoặc merge có độ phức tạp thời gian là O(n + m) vì mỗi phần tử của a và b chỉ được xét và sao chép đúng một lần. Đây là độ phức tạp tối ưu cho bài toán này vì ta phải đọc và ghi ít nhất O(n+m) phần tử. Độ phức tạp không gian là O(n + m) để lưu trữ mảng kết quả.

Tóm lại, hướng giải quyết tối ưu và sử dụng std một cách hiệu quả là đọc dữ liệu vào vector và dùng hàm merge để tạo mảng kết quả, sau đó in mảng kết quả.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.