std::partial_sortis an algorithm in the C++ standard library that can sort some elements in the container so thatNThe elements are arranged in order, without ensuring that the remaining parts are in order. Its time complexity is O(N log N + (M-N)), where M is the size of the entire range and N is the number of elements to be sorted.
1. Syntax
#include <algorithm> template< class RandomIt > void partial_sort( RandomIt first, RandomIt middle, RandomIt last ); template< class RandomIt, class Compare > void partial_sort( RandomIt first, RandomIt middle, RandomIt last, Compare comp );
-
first: The starting iterator of the range to be sorted. -
middle: Specify the previous orderNThe end point of an element, i.e.first + N。 -
last: End iterator for sorting ranges. -
comp(Optional): Custom comparison function.
2. Basic usage
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> vec = {7, 3, 9, 1, 6, 2, 8, 5, 4};
// Sort only the first 5 elements std::partial_sort((), () + 5, ());
// Output the first 5 sorted elements std::cout << "The top 5 smallest elements: ";
for (int i = 0; i < 5; ++i) {
std::cout << vec[i] << " ";
}
std::cout << "\n";
// Output the entire array std::cout << "The whole array: ";
for (int num : vec) {
std::cout << num << " ";
}
std::cout << "\n";
return 0;
}
Output
The first 5 smallest elements: 1 2 3 4 5
The entire array: 1 2 3 4 5 9 8 7 6
Note: The first 5 elements are ordered, but the entire array is still partially unordered.
3. Use custom comparison functions
Can be usedstd::greater<int>()Sort in descending order:
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> vec = {7, 3, 9, 1, 6, 2, 8, 5, 4};
// Get the first 5 largest elements (descending order) std::partial_sort((), () + 5, (), std::greater<int>());
// Output the first 5 sorted elements std::cout << "The top 5 biggest elements: ";
for (int i = 0; i < 5; ++i) {
std::cout << vec[i] << " ";
}
std::cout << "\n";
return 0;
}
Output
The top 5 biggest elements: 9 8 7 6 5
4. Comparison with std::sort and std::nth_element
| algorithm | effect | Complexity | Applicable scenarios |
|---|---|---|---|
| std::sort | Sort all | O(N log N) | Need to sort the entire sequence |
| std::partial_sort | Only the first N elements are ordered | O(N log N + (M-N)) | Only the minimum/maximum N ordered elements are required |
| std::nth_element | Only ensure that the element at N is correct, the left side is smaller than it and the right side is larger than it | O(M) | Just find the N-th smallest element and don't care about the order of other elements |
5. Applicable scenarios
- Find the first K minimum/maximum values
- Data stream processing (stream calculation)
- Top-K Query
- Quickly get top N elements
This is the article about the use of std::partial_sort in C++. For more related C++ std::partial_sort, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!