std::stable_sort

#include <algorithm>

// Sắp xếp tăng dần theo mặc định sử dụng toán tử <
template <class RandomAccessIterator>
void stable_sort (RandomAccessIterator first, RandomAccessIterator last);

// Sắp xếp theo tiêu chí so sánh tùy chỉnh
template <class RandomAccessIterator, class Compare>
void stable_sort (RandomAccessIterator first, RandomAccessIterator last,
                  Compare comp);

Sắp xếp các phần tử trong một phạm vi (range) theo thứ tự tăng dần (mặc định) hoặc theo một tiêu chí so sánh tùy chỉnh. Điểm khác biệt quan trọng so với sort() là stable_sort() đảm bảo tính ổn định (stability) của phép sắp xếp.

Tham số

`first`

Random Access Iterator trỏ đến phần tử đầu tiên trong phạm vi cần sắp xếp.

`last`

Random Access Iterator trỏ đến phần tử ngay sau phần tử cuối cùng trong phạm vi cần sắp xếp. Phạm vi là [first, last).

`comp`

Một hàm hoặc đối tượng hàm (comparator) nhận hai đối số (hai phần tử trong phạm vi) và trả về true nếu phần tử thứ nhất được coi là nhỏ hơn phần tử thứ hai theo tiêu chí so sánh, false nếu ngược lại. (Phiên bản 2)

Giá trị trả về

Không có giá trị trả về

Đặc điểm

Phạm vi [first, last) là "nửa mở", không bao gồm phần tử last.
stable_sort() thay đổi trực tiếp thứ tự các phần tử trong phạm vi gốc, không tạo ra một phạm vi mới.
stable_sort() yêu cầu Random Access Iterator, cho phép truy cập ngẫu nhiên vào các phần tử.
Trong C++11 trở lên, bạn có thể sử dụng biểu thức lambda cho hàm so sánh comp để code ngắn gọn và dễ đọc hơn.
stable_sort() thường sử dụng thuật toán Merge Sort (sắp xếp trộn) hoặc các biến thể của nó để đảm bảo tính ổn định. Do đó, độ phức tạp thời gian của stable_sort() là O(n log n) trong trường hợp tốt nhất, trung bình và xấu nhất. Tuy nhiên, stable_sort() có thể sử dụng thêm bộ nhớ, tối đa bằng một nửa kích thước của phạm vi, trong khi sort() có thể không cần.
stable_sort() thường được triển khai theo cách tại chỗ (in-place) nếu có đủ bộ nhớ, có nghĩa là nó sắp xếp trực tiếp trên phạm vi đầu vào mà không cần thêm không gian lưu trữ đáng kể. Tuy nhiên, nó vẫn cần sử dụng thêm một lượng bộ nhớ nhất định để lưu các phần tử tạm, nên trong trường hợp xấu nhất, nó có thể không phải là tại chỗ.
stable_sort() được sử dụng khi:
- Bạn cần sắp xếp các phần tử trong một container (ví dụ: std::vector, std::array, mảng C-style) và giữ nguyên thứ tự tương đối của các phần tử bằng nhau.
- Bạn cần sắp xếp một phần của container theo thứ tự ổn định.
- Bạn cần sắp xếp dữ liệu theo thứ tự tăng dần hoặc giảm dần một cách ổn định.
- Bạn cần sắp xếp dữ liệu theo một tiêu chí tùy chỉnh một cách ổn định.

Tính ổn định (Stability)

Tính ổn định có nghĩa là thứ tự tương đối của các phần tử bằng nhau (theo tiêu chí so sánh) được giữ nguyên sau khi sắp xếp. Ví dụ, nếu bạn đang sắp xếp danh sách sinh viên theo điểm số và hai sinh viên có cùng điểm số, thì stable_sort() đảm bảo rằng thứ tự ban đầu của hai sinh viên đó trong danh sách sẽ được giữ nguyên sau khi sắp xếp. sort() không đảm bảo điều này.

Phân biệt với sort()

sort() sắp xếp không ổn định. Thứ tự tương đối của các phần tử bằng nhau có thể bị thay đổi.
stable_sort() sắp xếp ổn định. Thứ tự tương đối của các phần tử bằng nhau được giữ nguyên.
sort() thường nhanh hơn stable_sort() trong thực tế, nhưng có thể không ổn định.
stable_sort() thường chậm hơn sort(), nhưng đảm bảo tính ổn định.

Ví dụ

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

// Struct Person để minh họa sắp xếp ổn định
struct Person {
  std::string name;
  int age;
};

// Hàm so sánh để sắp xếp Person theo tên, nếu tên bằng nhau thì sắp xếp theo tuổi giảm dần
bool comparePerson(const Person& a, const Person& b) {
  if (a.name != b.name) {
    return a.name < b.name;
  } else {
    return a.age > b.age;
  }
}

int main() {
  std::vector<Person> people = {
    {"Alice", 30},
    {"Bob", 25},
    {"Charlie", 35},
    {"Alice", 28},
    {"Bob", 30}
  };

  // Sắp xếp people sử dụng stable_sort và hàm so sánh comparePerson
  std::stable_sort(people.begin(), people.end(), comparePerson);

  std::cout << "people after stable_sort:" << std::endl;
  for (const auto& p : people) {
    std::cout << p.name << " (" << p.age << ") ";
  }
  std::cout << std::endl;

  return 0;
}

Các hàm liên quan


sort	Sắp xếp các phần tử trong một phạm vi theo thứ tự tăng dần hoặc theo một tiêu chí so sánh tùy chỉnh
partial_sort	Sắp xếp một phần của một phạm vi
search	Tìm kiếm sự xuất hiện đầu tiên của một dãy con trong một phạm vi lớn hơn
reverse	Đảo ngược thứ tự các phần tử trong một phạm vi được chỉ định

Tham số​

first​

last​

comp​

Giá trị trả về​

Đặc điểm​

Ví dụ​

Các hàm liên quan​