std::is_sorted

#include <algorithm>

// Kiểm tra sắp xếp tăng dần theo mặc định sử dụng toán tử <
template <class ForwardIterator>
bool is_sorted (ForwardIterator first, ForwardIterator last);

// Kiểm tra sắp xếp theo tiêu chí so sánh tùy chỉnh
template <class ForwardIterator, class Compare>
bool is_sorted (ForwardIterator first, ForwardIterator last, Compare comp);

Kiểm tra xem một phạm vi (range) đã được sắp xếp theo thứ tự tăng dần (mặc định) hay theo một tiêu chí so sánh tùy chỉnh hay chưa.

Tham số

first

• Forward Iterator trỏ đến phần tử đầu tiên trong phạm vi cần kiểm tra.

last

• Forward Iterator trỏ đến phần tử ngay sau phần tử cuối cùng trong phạm vi cần kiểm tra. 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ề

true

• Nếu phạm vi đã được sắp xếp theo thứ tự chỉ định (tăng dần theo mặc định hoặc theo comp).

false

• Nếu phạm vi chưa được sắp xếp.

Đặc điểm

1. Phạm vi [first, last) là "nửa mở", không bao gồm phần tử last.
2. is_sorted() không thay đổi phạm vi đầu vào.
3. is_sorted() yêu cầu Forward Iterator, cho phép di chuyển một chiều về phía trước.
4. 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 (phiên bản 2) để code ngắn gọn và dễ đọc hơn.
5. Một phạm vi rỗng hoặc chỉ có một phần tử luôn được coi là đã sắp xếp.
6. is_sorted() thường được sử dụng để:
   • Kiểm tra xem dữ liệu trong một container đã được sắp xếp hay chưa trước khi thực hiện các thao tác khác (ví dụ: tìm kiếm nhị phân).
   • Xác minh kết quả của các thuật toán sắp xếp.
   • Đảm bảo tính hợp lệ của dữ liệu đầu vào.

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

• sort() và stable_sort() thực hiện sắp xếp các phần tử trong phạm vi.
• is_sorted() chỉ kiểm tra xem phạm vi đã được sắp xếp hay chưa.

Ví dụ

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

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

int main() {
  std::vector<int> numbers1 = {1, 2, 3, 4, 5};
  std::vector<int> numbers2 = {5, 4, 3, 2, 1};
  std::vector<int> numbers3 = {1, 3, 2, 4, 5};

  // Kiểm tra numbers1 (sắp xếp tăng dần)
  if (std::is_sorted(numbers1.begin(), numbers1.end())) {
    std::cout << "numbers1 is sorted in ascending order.\n";
  } else {
    std::cout << "numbers1 is not sorted in ascending order.\n";
  }

  // Kiểm tra numbers2 (sắp xếp giảm dần) với hàm so sánh
  if (std::is_sorted(numbers2.begin(), numbers2.end(), compareDescending)) {
    std::cout << "numbers2 is sorted in descending order.\n";
  } else {
    std::cout << "numbers2 is not sorted in descending order.\n";
  }

  // Kiểm tra numbers3 (không sắp xếp)
  if (std::is_sorted(numbers3.begin(), numbers3.end())) {
    std::cout << "numbers3 is sorted in ascending order.\n";
  } else {
    std::cout << "numbers3 is not sorted in ascending order.\n";
  }

  return 0;
}

Các hàm liên quan

is_sorted_until	Tìm vị trí phần tử đầu tiên trong một phạm vi mà từ vị trí đó trở đi, phạm vi không còn được sắp xếp theo thứ tự tăng dần hoặc theo một tiêu chí so sánh tùy chỉnh
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