std::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 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 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.

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

1. Phạm vi [first, last) là "nửa mở", không bao gồm phần tử last.
2. 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.
3. 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ử (ví dụ: iterator của std::vector, std::array, con trỏ). std::list không cung cấp Random Access Iterator, bạn phải dùng std::list::sort thành viên để thay thế.
4. sort() không đảm bảo tính ổn định (stability). 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ó thể bị thay đổi sau khi sắp xếp. Nếu bạn cần đảm bảo tính ổn định, hãy sử dụng stable_sort().
5. 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.
6. sort() thường sử dụng các thuật toán sắp xếp hiệu quả như Introsort (lai giữa Quicksort, Heapsort và Insertion Sort) hoặc Merge Sort tùy vào implementation của thư viện chuẩn. Do đó, độ phức tạp trung bình của sort() là O(n log n), trong đó n là số phần tử cần sắp xếp.
7. sort() sắp xếp trực tiếp trên phạm vi đầu vào, không yêu cầu thêm không gian lưu trữ đáng kể (ngoài một lượng nhỏ cho đệ quy hoặc các biến tạm).
8. sort() thường được sử dụng để:
   • Sắp xếp các phần tử trong một container (ví dụ: std::vector, std::array, mảng C-style).
   • Sắp xếp một phần của container.
   • Sắp xếp dữ liệu theo thứ tự tăng dần hoặc giảm dần.
   • Sắp xếp dữ liệu theo một tiêu chí tùy chỉnh (ví dụ: sắp xếp các đối tượng theo một thuộc tính cụ thể).

Ví dụ

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

// Hàm so sánh để sắp xếp giảm dần
bool compareDescending(int a, int b) {
  return a > b;
}

// Struct Person để minh họa sắp xếp theo tiêu chí tùy chỉnh
struct Person {
  std::string name;
  int age;
};

// Hàm so sánh để sắp xếp Person theo tuổi tăng dần
bool comparePersonByAge(const Person& a, const Person& b) {
  return a.age < b.age;
}

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

  // Sắp xếp numbers tăng dần (mặc định)
  std::sort(numbers.begin(), numbers.end());

  std::cout << "numbers after sort (ascending): ";
  for (int x : numbers) {
    std::cout << x << " ";
  }
  std::cout << std::endl;

  // Sắp xếp numbers giảm dần sử dụng hàm so sánh compareDescending
  std::sort(numbers.begin(), numbers.end(), compareDescending);

  std::cout << "numbers after sort (descending): ";
  for (int x : numbers) {
    std::cout << x << " ";
  }
  std::cout << std::endl;

  std::vector<Person> people = {
    {"Alice", 30},
    {"Bob", 25},
    {"Charlie", 35}
  };

  // Sắp xếp people theo tuổi tăng dần sử dụng biểu thức lambda
  std::sort(people.begin(), people.end(),
            [](const Person& a, const Person& b) { return a.age < b.age; });

  std::cout << "people after sort (by age):" << 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

stable_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