1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
|
<HTML>
<!--
-- Copyright (c) 1996,1997
-- Silicon Graphics Computer Systems, Inc.
--
-- Permission to use, copy, modify, distribute and sell this software
-- and its documentation for any purpose is hereby granted without fee,
-- provided that the above copyright notice appears in all copies and
-- that both that copyright notice and this permission notice appear
-- in supporting documentation. Silicon Graphics makes no
-- representations about the suitability of this software for any
-- purpose. It is provided "as is" without express or implied warranty.
--
-- Copyright (c) 1994
-- Hewlett-Packard Company
--
-- Permission to use, copy, modify, distribute and sell this software
-- and its documentation for any purpose is hereby granted without fee,
-- provided that the above copyright notice appears in all copies and
-- that both that copyright notice and this permission notice appear
-- in supporting documentation. Hewlett-Packard Company makes no
-- representations about the suitability of this software for any
-- purpose. It is provided "as is" without express or implied warranty.
--
-->
<Head>
<Title>partial_sort</Title>
<!-- Generated by htmldoc -->
</HEAD>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
ALINK="#ff0000">
<IMG SRC="CorpID.gif"
ALT="Silicon Graphics, Inc." HEIGHT="43" WIDTH="151">
<!--end header-->
<BR Clear>
<H1>partial_sort</H1>
<Table CellPadding=0 CellSpacing=0 width=100%>
<TR>
<TD Align=left><Img src = "algorithms.gif" Alt="" WIDTH = "194" HEIGHT = "38" ></TD>
<TD Align=right><Img src = "function.gif" Alt="" WIDTH = "194" HEIGHT = "38" ></TD>
</TR>
<TR>
<TD Align=left VAlign=top><b>Category</b>: algorithms</TD>
<TD Align=right VAlign=top><b>Component type</b>: function</TD>
</TR>
</Table>
<h3>Prototype</h3>
<tt>Partial_sort</tt> is an overloaded name; there are actually two <tt>partial_sort</tt>
functions.
<pre>
template <class <A href="RandomAccessIterator.html">RandomAccessIterator</A>>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);
template <class <A href="RandomAccessIterator.html">RandomAccessIterator</A>, class <A href="StrictWeakOrdering.html">StrictWeakOrdering</A>>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last,
StrictWeakOrdering comp);
</pre>
<h3>Description</h3>
<tt>Partial_sort</tt> rearranges the elements in the range <tt>[first, last)</tt> so
that they are partially in ascending order. Specifically, it places
the smallest <tt>middle - first</tt> elements, sorted in ascending order,
into the range <tt>[first, middle)</tt>. The remaining <tt>last - middle</tt>
elements are placed, in an unspecified order, into the range <tt>[middle,
last)</tt>. <A href="#1">[1]</A> <A href="#2">[2]</A>
<P>
The two versions of <tt>partial_sort</tt> differ in how they define whether one
element is less than another. The first version compares
objects using <tt>operator<</tt>, and the second compares objects using
a <A href="functors.html">function object</A> <tt>comp</tt>.
<P>
The postcondition for the first version of <tt>partial_sort</tt> is as
follows. If <tt>i</tt> and <tt>j</tt> are
any two valid iterators in the range <tt>[first, middle)</tt> such that <tt>i</tt>
precedes <tt>j</tt>, and if <tt>k</tt> is a valid iterator in the range <tt>[middle,
last)</tt>, then <tt>*j < *i</tt> and <tt>*k < *i</tt> will both be <tt>false</tt>.
The corresponding postcondition for the second version of <tt>partial_sort</tt>
is that <tt>comp(*j, *i)</tt> and <tt>comp(*k, *i)</tt>
are both false. Informally, this postcondition means that the first <tt>middle - first</tt>
elements are in ascending order and that none of the elements in
<tt>[middle, last)</tt> is less than any of the elements in <tt>[first, middle)</tt>.
<h3>Definition</h3>
Defined in <A href="algo.h">algo.h</A>.
<h3>Requirements on types</h3>
For the first version:
<UL>
<LI>
<tt>RandomAccessIterator</tt> is a model of <A href="RandomAccessIterator.html">Random Access Iterator</A>.
<LI>
<tt>RandomAccessIterator</tt> is mutable.
<LI>
<tt>RandomAccessIterator</tt>'s value type is <A href="LessThanComparable.html">LessThan Comparable</A>.
<LI>
The ordering relation on <tt>RandomAccessIterator</tt>'s value type is
a <i>strict weak ordering</i>, as defined in the <A href="LessThanComparable.html">LessThan Comparable</A>
requirements.
</UL>
For the second version:
<UL>
<LI>
<tt>RandomAccessIterator</tt> is a model of <A href="RandomAccessIterator.html">Random Access Iterator</A>.
<LI>
<tt>RandomAccessIterator</tt> is mutable.
<LI>
<tt>StrictWeakOrdering</tt> is a model of <A href="StrictWeakOrdering.html">Strict Weak Ordering</A>.
<LI>
<tt>RandomAccessIterator</tt>'s value type is convertible to
<tt>StrictWeakOrdering</tt>'s argument type.
</UL>
<h3>Preconditions</h3>
<UL>
<LI>
<tt>[first, middle)</tt> is a valid range.
<LI>
<tt>[middle, last)</tt> is a valid range.
</UL>
(It follows from these two conditions that <tt>[first, last)</tt> is a valid range.)
<h3>Complexity</h3>
Approximately <tt>(last - first) * log(middle - first)</tt> comparisons.
<h3>Example</h3>
<pre>
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".
</pre>
<h3>Notes</h3>
<P><A name="1">[1]</A>
Note that the elements in the range <tt>[first, middle)</tt> will be the
same (ignoring, for the moment, equivalent elements) as if you had sorted
the entire range using <tt>sort(first, last)</tt>. The reason for using
<tt>partial_sort</tt> in preference to <tt>sort</tt> is simply efficiency: a partial
sort, in general, takes less time.
<P><A name="2">[2]</A>
<tt>partial_sort(first, last, last)</tt> has the effect of sorting the
entire range <tt>[first, last)</tt>, just like <tt><A href="sort.html">sort</A>(first, last)</tt>. They
use different algorithms, however: <tt>sort</tt> uses the <i>introsort</i> algorithm
(a variant of quicksort), and <tt>partial_sort</tt> uses <i>heapsort</i>. See section 5.2.3 of
Knuth (D. E. Knuth, <i>The Art of Computer
Programming. Volume 3: Sorting and Searching</i>.
Addison-Wesley, 1975.), and J. W. J. Williams (<i>CACM</i> <b>7</b>, 347, 1964).
Both heapsort and introsort have complexity of order <tt>N
log(N)</tt>, but introsort is usually faster by a factor of 2 to 5.
<h3>See also</h3>
<tt><A href="partial_sort_copy.html">partial_sort_copy</A></tt>,
<tt><A href="sort.html">sort</A></tt>,
<tt><A href="stable_sort.html">stable_sort</A></tt>,
<tt><A href="binary_search.html">binary_search</A></tt>,
<tt><A href="lower_bound.html">lower_bound</A></tt>,
<tt><A href="upper_bound.html">upper_bound</A></tt>,
<tt><A href="less.html">less</A><T></tt>,
<A href="StrictWeakOrdering.html">StrictWeakOrdering</A>,
<A href="LessThanComparable.html">LessThan Comparable</A>
<!--start footer-->
<HR SIZE="6">
<A href="http://www.sgi.com/"><IMG SRC="surf.gif" HEIGHT="54" WIDTH="54"
ALT="[Silicon Surf]"></A>
<A HREF="index.html"><IMG SRC="stl_home.gif"
HEIGHT="54" WIDTH="54" ALT="[STL Home]"></A>
<BR>
<FONT SIZE="-2">
<A href="http://www.sgi.com/Misc/sgi_info.html" TARGET="_top">Copyright ©
1996 Silicon Graphics, Inc.</A> All Rights Reserved.</FONT>
<FONT SIZE="-3"><a href="http://www.sgi.com/Misc/external.list.html" TARGET="_top">TrademarkInformation</A>
</FONT>
<P>
</BODY>
</HTML>
|
