partial_sort
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.
See also
partial_sort_copy,
sort,
stable_sort,
binary_search,
lower_bound,
upper_bound,
less<T>,
StrictWeakOrdering,
LessThan Comparable
Copyright ©
1999 Silicon Graphics, Inc. All Rights Reserved.
TrademarkInformation
Wyszukiwarka
Podobne podstrony:
partial sort copysort?m60 mod?PTM bubble sortsort?m60 modsort?p35 mod?sort?p35 modsort?m50 mod?sortgroup partial convsort?m45 modsortarm conv partial q7? sourcesort heapsort?p50 mod?sort wstaw 123function yaz sortPartiawięcej podobnych podstron