std::partial_sort

From Cppreference

C++ Standard Library
Language Utilities library Strings library Containers library Algorithms library Iterators library Numerics library Input/output library Localizations library Regular expressions library (C++0x feature) Atomic operations library (C++0x feature) Thread support library (C++0x feature)
Algorithm library
Functions Non-modifying sequence operations all_of any_of none_of (C++0x) (C++0x) (C++0x) for_each count count_if mismatch equal find find_if find_if_not (C++0x) find_end find_first_of adjacent_find search search_n Modifying sequence operations copy copy_backward fill fill_n transform generate generate_n remove remove_if remove_copy remove_copy_if replace replace_if replace_copy replace_copy_if swap swap_ranges iter_swap partition stable_partition reverse reverse_copy rotate rotate_copy random_shuffle unique unique_copy Sorting operations (on sorted ranges) is_sorted (C++0x) is_sorted_until (C++0x) sort partial_sort partial_sort_copy stable_sort nth_element Binary search operations (on sorted ranges) lower_bound upper_bound binary_search equal_range Set operations (on sorted ranges) merge inplace_merge includes set_difference set_intersection set_symmetric_difference set_union Heap operations is_heap is_heap_until (C++0x) make_heap push_heap pop_heap sort_heap Minimum/maximum operations max max_element min min_element lexicographical_compare next_permutation prev_permutation Numeric operations accumulate inner_product adjacent_difference partial_sum C library qsort bsearch

Defined in header <algorithm>
​template< class InputIterator, class RandomAccessIterator > RandomAccessIterator partial_sort_copy( InputIterator first,                                         InputIterator last,                                         RandomAccessIterator d_first,                                         RandomAccessIterator d_last );​	(1)
​template< class InputIterator, class RandomAccessIterator, class Compare > RandomAccessIterator partial_sort_copy( InputIterator first,                                         InputIterator last,                                         RandomAccessIterator d_first,                                         RandomAccessIterator d_last,                                         Compare comp );​	(2)

Sorts some of the elements in the range [first, last) in ascending order. At most ​d_first - d_last​ of the elements are moved to the range [d_first, d_first + n) and then sorted. n is the number of elements to sort (​n = min(last - first, d_last - d_first)​). The order of equal elements is guaranteed to be preserved. The first version uses ​operator<​ to compare the elements, the second version uses the given comparison function comp.

Contents 1 Parameters 2 Return value 3 Complexity 4 Example 5 See also

Parameters

first, last	-	the range of elements to sort
d_first, d_last	-	random access iterators defining the destination range
comp	-	comparison function which returns ​​true​ if the first argument is less than the second. The signature of the comparison function should be equivalent to the following: ​bool cmp(const Type1 &a, const Type2 &b);​ The signature does not need to have ​const &​, but the function must not modify the objects passed to it. The types ​Type1​ and ​Type2​ must be such that an object of type ​RandomAccessIterator​ can be dereferenced and then implicitly converted to both of them. ​

Return value

an iterator to the element defining the upper boundary of the sorted range, i.e. ​d_first + min(last - first, d_last - d_first)​.

Complexity

O(N*log(min(D-N)), where ​N = std::distance(first, last)​, ​D = std::distance(d_first, d_last)​ applications of cmp.

Example

This section is incomplete

See also

partial_sort	sorts the first N elements of a range (function template)
sort	sorts a range into ascending order (function template)
stable_sort	sorts a range of elements while preserving order between equal elements (function template)