partial_sort


Category: algorithms	Component type: function

Prototype

Partial_sort is an overloaded name; there are actually two partial_sort functions.

template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator first

                  RandomAccessIterator middle

                  RandomAccessIterator last);

template <class RandomAccessIterator
class StrictWeakOrdering>
void partial_sort(RandomAccessIterator first

                  RandomAccessIterator middle

                  RandomAccessIterator last

                  StrictWeakOrdering comp);

Description

Partial_sort rearranges the elements in the range [first last) so that they are partially in ascending order. Specifically it places the smallest middle - first elements sorted in ascending order into the range [first middle). The remaining last - middle elements are placed in an unspecified order into the range [middle last). [1] [2]

The two versions of partial_sort differ in how they define whether one element is less than another. The first version compares objects using operator< and the second compares objects using a function object comp.

The postcondition for the first version of partial_sort is as follows. If i and j are any two valid iterators in the range [first middle) such that i precedes j and if k is a valid iterator in the range [middle last) then *j < *i and *k < *i will both be false. The corresponding postcondition for the second version of partial_sort is that comp(*j *i) and comp(*k *i) are both false. Informally this postcondition means that the first middle - first elements are in ascending order and that none of the elements in [middle last) is less than any of the elements in [first middle).

Definition

Defined in the standard header algorithm and in the nonstandard backward-compatibility header algo.h.

Requirements on types

For the first version:

RandomAccessIterator is a model of Random Access Iterator.
RandomAccessIterator is mutable.
RandomAccessIterator's value type is LessThan Comparable.
The ordering relation on RandomAccessIterator's value type is a strict weak ordering as defined in the LessThan Comparable requirements.

For the second version:

RandomAccessIterator is a model of Random Access Iterator.
RandomAccessIterator is mutable.
StrictWeakOrdering is a model of Strict Weak Ordering.
RandomAccessIterator's value type is convertible to StrictWeakOrdering's argument type.

Preconditions

[first middle) is a valid range.
[middle last) is a valid range.

(It follows from these two conditions that [first last) is a valid range.)

Complexity

Approximately (last - first) * log(middle - first) comparisons.

Example

int A[] = {7
2
6
11
9
3
12
10
8
4
1
5};
const int N = sizeof(A) / sizeof(int);

partial_sort(A
A + 5
A + N);
copy(A
A + N
ostream_iterator<int>(cout
" "));
// The printed result is "1 2 3 4 5 11 12 10 9 8 7 6".

Notes

[1] Note that the elements in the range [first middle) will be the same (ignoring for the moment equivalent elements) as if you had sorted the entire range using sort(first last). The reason for using partial_sort in preference to sort is simply efficiency: a partial sort in general takes less time.

[2] partial_sort(first last last) has the effect of sorting the entire range [first last) just like sort(first last). They use different algorithms however: sort uses the introsort algorithm (a variant of quicksort) and partial_sort uses heapsort. See section 5.2.3 of Knuth (D. E. Knuth The Art of Computer Programming. Volume 3: Sorting and Searching. Addison-Wesley 1975.) and J. W. J. Williams (CACM 7 347 1964). Both heapsort and introsort have complexity of order N log(N) but introsort is usually faster by a factor of 2 to 5.