Книга: Standard Template Library Programmer

partial_sort

partial_sort

Category: algorithms

Component type: function

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);

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).

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

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.

• [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.)

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

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".

[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.

partial_sort_copy, sort, stable_sort, binary_search, lower_bound, upper_bound, less<T>, StrictWeakOrdering, LessThan Comparable

Оглавление книги