std::partial_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 partial_sort (RandomAccessIterator first, RandomAccessIterator middle,
                   RandomAccessIterator last);

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

Sắp xếp một phần của một phạm vi (range) sao cho các phần tử trong phạm vi con [first, middle) được sắp xếp theo thứ tự (tăng dần theo mặc định hoặc theo tiêu chí so sánh tùy chỉnh). Các phần tử còn lại trong phạm vi [middle, last) sẽ có giá trị lớn hơn (hoặc không nhỏ hơn) các phần tử trong phạm vi con đã sắp xếp, nhưng thứ tự của chúng là không xác đị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 một phần.

middle

• Random Access Iterator trỏ đến phần tử ngay sau phần tử cuối cùng trong phạm vi con [first, middle) sẽ đượ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

1. Phạm vi [first, last) và [first, middle) là "nửa mở", không bao gồm phần tử last và middle.
2. partial_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. partial_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ử.
4. Thứ tự của các phần tử trong phạm vi [middle, last) là không xác định sau khi partial_sort() thực hiện.
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 (phiên bản 2) để code ngắn gọn và dễ đọc hơn.
6. partial_sort() thường sử dụng thuật toán Heapsort để đạt được hiệu quả sắp xếp một phần. Độ phức tạp thời gian trung bình của partial_sort() là O(n log m), trong đó n là số phần tử trong phạm vi [first, last) và m là số phần tử trong phạm vi con [first, middle).
7. partial_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ể.
8. partial_sort() thường được sử dụng khi:
   • Bạn chỉ cần sắp xếp một phần nhỏ của một tập hợp dữ liệu lớn, thay vì sắp xếp toàn bộ.
   • Bạn cần tìm k phần tử nhỏ nhất (hoặc lớn nhất) trong một tập hợp dữ liệu (trong trường hợp này, middle sẽ là first + k).
   • Bạn muốn thực hiện sắp xếp một phần dữ liệu một cách hiệu quả.

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

• sort() sắp xếp toàn bộ phạm vi.
• stable_sort() sắp xếp toàn bộ phạm vi một cách ổn định.
• partial_sort() chỉ sắp xếp một phần của phạm vi.

Ví dụ

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

// Hàm so sánh để sắp xếp 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};

  // Sắp xếp 4 phần tử nhỏ nhất trong numbers (tăng dần)
  std::partial_sort(numbers.begin(), numbers.begin() + 4, numbers.end());

  std::cout << "numbers after partial_sort (4 smallest): ";
  for (int x : numbers) {
    std::cout << x << " ";
  }
  std::cout << std::endl;

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

  // Sắp xếp 3 phần tử lớn nhất trong numbers2 (giảm dần)
  std::partial_sort(numbers2.begin(), numbers2.begin() + 3, numbers2.end(), compareDescending);

  std::cout << "numbers2 after partial_sort (3 largest): ";
  for (int x : numbers2) {
      std::cout << x << " ";
  }
  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
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
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