std::nth_element

#include <algorithm>

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

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

Sắp xếp một phần của một phạm vi (range) sao cho phần tử tại vị trí nth (được chỉ định) sẽ là phần tử mà lẽ ra sẽ ở vị trí đó nếu toàn bộ phạm vi được 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 một phần.

`nth`

Random Access Iterator trỏ đến phần tử thứ nth trong phạm vi. Phần tử tại vị trí này sau khi nth_element() thực hiện sẽ là phần tử mà lẽ ra sẽ ở đó nếu toàn bộ phạm vi được 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. 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.
nth_element() 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.
nth_element() yêu cầu Random Access Iterator, cho phép truy cập ngẫu nhiên vào các phần tử.
Thứ tự của các phần tử trong các nhóm trước và sau vị trí nth là không xác định (ngoại trừ việc chúng nhỏ hơn/lớn hơn hoặc bằng phần tử tại nth).
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.
nth_element() đảm bảo rằng:
- Tất cả các phần tử trước nth đều không lớn hơn phần tử tại vị trí nth.
- Tất cả các phần tử sau nth đều không nhỏ hơn phần tử tại vị trí nth.
- Lưu ý: nth_element() không đảm bảo các phần tử trong các nhóm (trước nth và sau nth) được sắp xếp.
nth_element() thường sử dụng thuật toán Quickselect hoặc Introselect để tìm phần tử thứ nth (theo thứ tự) một cách hiệu quả. Độ phức tạp thời gian trung bình của nth_element() là O(n), trong đó n là số phần tử trong phạm vi.
nth_element() sắp xếp một phần 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ể.
nth_element() thường được sử dụng để:
- Tìm phần tử có thứ hạng (rank) cụ thể trong một tập hợp dữ liệu (ví dụ: tìm phần tử nhỏ thứ 5, tìm trung vị (median)).
- Phân vùng (partition) dữ liệu xung quanh một phần tử cụ thể (tương tự như partition() nhưng có đảm bảo về vị trí của phần tử nth).
- Tối ưu hóa các thuật toán chỉ yêu cầu một phần của dữ liệu được sắp xếp.

Phân biệt với sort(), partial_sort(), và partition()

sort() sắp xếp toàn bộ phạm vi.
partial_sort() sắp xếp một phần đầu của phạm vi (ví dụ: k phần tử nhỏ nhất).
partition() phân hoạch phạm vi thành hai phần dựa trên một điều kiện, nhưng không sắp xếp các phần tử trong mỗi phần.
nth_element() chỉ đảm bảo phần tử tại vị trí nth có giá trị đúng như khi đã sắp xếp, và các phần tử trước/sau nth nhỏ hơn/lớn hơn hoặc bằng nó, không sắp xếp toàn bộ các phần tử trong các nhóm trước và sau nth.

Ví dụ

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

// Hàm so sánh để tìm phần tử lớn thứ n (giảm dần)
bool compareDescending(int a, int b) {
  return a > b;
}

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

  // Tìm phần tử nhỏ thứ 4 (sắp xếp tăng dần)
  std::nth_element(numbers.begin(), numbers.begin() + 3, numbers.end());

  std::cout << "numbers after nth_element (4th smallest): ";
  for (int x : numbers) {
    std::cout << x << " ";
  }
  std::cout << std::endl;
  std::cout << "The 4th smallest element is: " << numbers[3] << std::endl;

  std::vector<int> numbers2 = {5, 2, 8, 1, 9, 4, 7, 3, 6};
  // Tìm phần tử lớn thứ 3 (sắp xếp giảm dần)
  std::nth_element(numbers2.begin(), numbers2.begin() + 2, numbers2.end(), compareDescending);

  std::cout << "numbers2 after nth_element (3rd largest): ";
  for (int x : numbers2) {
      std::cout << x << " ";
  }
  std::cout << std::endl;
  std::cout << "The 3rd largest element is: " << numbers2[2] << 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
partition	Sắp xếp lại các phần tử trong một phạm vi
find_if	Tìm kiếm phần tử đầu tiên trong một phạm vi thỏa mãn một điều kiện cụ thể được xác định bởi một hàm vị từ

Tham số​

first​

nth​

last​

comp​

Giá trị trả về​

Đặc điểm​

Ví dụ​

Các hàm liên quan​