<HTML>
<HEAD>
<TITLE>sort()</TITLE>
<LINK REL=StyleSheet HREF="../rw.css" TYPE="text/css" TITLE="Apache stdcxx Stylesheet"></HEAD>
<BODY BGCOLOR=#FFFFFF>
<A HREF="slice-array.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="sort-heap.html"><IMG SRC="images/bnext.gif" WIDTH=25 HEIGHT=21 ALT="Next file" BORDER=O></A><DIV CLASS="DOCUMENTNAME"><B>Apache C++ Standard Library Reference Guide</B></DIV>
<H2>sort()</H2>
<P><B>Library:</B>&nbsp;&nbsp;<A HREF="2-9.html">Algorithms</A></P>

<PRE><HR><B><I>Function</I></B><HR></PRE>

<UL>
<LI><A HREF="#sec1">Local Index</A></LI>
<LI><A HREF="#sec2">Summary</A></LI>
<LI><A HREF="#sec3">Synopsis</A></LI>
<LI><A HREF="#sec4">Description</A></LI>
<LI><A HREF="#sec5">Complexity</A></LI>
<LI><A HREF="#sec6">Example</A></LI>
<LI><A HREF="#sec7">See Also</A></LI>
<LI><A HREF="#sec8">Standards Conformance</A></LI>
</UL>
<A NAME="sec1"><H3>Local Index</H3></A>
No Entries
<A NAME="sec2"><H3>Summary</H3></A>
<P>A templatized algorithm for sorting collections of entities</P>
<A NAME="sec3"><H3>Synopsis</H3></A>

<PRE>#include &lt;algorithm&gt;

namespace std {
  template &lt;class RandomAccessIterator&gt;
  void sort(RandomAccessIterator start, 
            RandomAccessIterator finish);
  template &lt;class RandomAccessIterator, class Compare&gt;
  void sort(RandomAccessIterator start, 
            RandomAccessIterator finish, Compare comp);
}
</PRE>
<A NAME="sec4"><H3>Description</H3></A>
<P>The <SAMP>sort()</SAMP> algorithm sorts the elements in the range <SAMP>[start, finish)</SAMP> in ascending order using either <SAMP>operator&lt;()</SAMP> or the function object <SAMP>comp</SAMP>. The algorithm is not stable; that is, it does not preserve the order of elements that are equivalent (i.e., those for which <SAMP>(a &lt; b &amp;&amp; b &lt; a) == false</SAMP>). If maintaining such an ordering is is important, <SAMP><A HREF="stable-sort.html">stable_sort()</A></SAMP> should be used instead.  <SAMP>sort()</SAMP> is implemented using <I>introsort</I>.</P>
<A NAME="sec5"><H3>Complexity</H3></A>
<P><SAMP>sort()</SAMP> performs approximately <SAMP>N * log(N)</SAMP> comparisons in the worst case, where <SAMP>N</SAMP> equals <SAMP>finish -  start</SAMP>.</P>
<A NAME="sec6"><H3>Example</H3></A>

<UL><PRE>//
//  sort.cpp
//

#include &lt;vector&gt;
#include &lt;algorithm&gt;
#include &lt;functional&gt;
#include &lt;iostream&gt;


struct associate
{
    int num;
    char chr;
    associate (int n, char c) : num (n), chr (c){};
    associate () : num (0), chr ('\0'){};
};


inline bool operator&lt; (const associate &amp;x, const associate &amp;y)
{
    return x.num &lt; y.num;
}


inline std::ostream&amp; operator&lt;&lt; (std::ostream &amp;s, 
                                 const associate &amp;x)
{
    return s &lt;&lt; '&lt;' &lt;&lt; x.num &lt;&lt; ';' &lt;&lt; x.chr &lt;&lt; '&gt;';
}


int main ()
{
    const associate arr [20] = {
        associate (-4, ' '), associate (16, ' '),
        associate (17, ' '), associate (-3, 's'),
        associate (14, ' '), associate (-6, ' '),
        associate (-1, ' '), associate (-3, 't'),
        associate (23, ' '), associate (-3, 'a'),
        associate (-2, ' '), associate (-7, ' '),
        associate (-3, 'b'), associate (-8, ' '),
        associate (11, ' '), associate (-3, 'l'),
        associate (15, ' '), associate (-5, ' '),
        associate (-3, 'e'), associate (15, ' ')};

    typedef std::vector&lt;associate, std::allocator&lt;associate&gt; &gt; 
            Vector;

    // Set up vectors.
    Vector v (arr, arr + sizeof arr / sizeof *arr);
    Vector v1 (sizeof arr / sizeof *arr);
    Vector v2 (sizeof arr / sizeof *arr);

    // Copy original vector to vectors #1 and #2.
    std::copy (v.begin (), v.end (), v1.begin ());
    std::copy (v.begin (), v.end (), v2.begin ());

    // Sort vector #1.
    std::sort (v1.begin (), v1.end ());

    // Stable sort vector #2.
    std::stable_sort (v2.begin (), v2.end ());

    // Display the results.
    std::cout &lt;&lt; "Original    sort      stable_sort"
              &lt;&lt; std::endl;
    for (Vector::iterator i = v.begin (), j = v1.begin (),
                          k = v2.begin ();
         i != v.end (); i++, j++, k++)
        std::cout &lt;&lt; *i &lt;&lt; "     " &lt;&lt; *j &lt;&lt; "     "
                  &lt;&lt; *k &lt;&lt; std::endl;

    return 0;
}


Program Output:
</PRE></UL>
<UL><PRE>Original    sort      stable_sort
&lt;-4; &gt;     &lt;-8; &gt;     &lt;-8; &gt;
&lt;16; &gt;     &lt;-7; &gt;     &lt;-7; &gt;
&lt;17; &gt;     &lt;-6; &gt;     &lt;-6; &gt;
&lt;-3;s&gt;     &lt;-5; &gt;     &lt;-5; &gt;
&lt;14; &gt;     &lt;-4; &gt;     &lt;-4; &gt;
&lt;-6; &gt;     &lt;-3;e&gt;     &lt;-3;s&gt;
&lt;-1; &gt;     &lt;-3;s&gt;     &lt;-3;t&gt;
&lt;-3;t&gt;     &lt;-3;l&gt;     &lt;-3;a&gt;
&lt;23; &gt;     &lt;-3;t&gt;     &lt;-3;b&gt;
&lt;-3;a&gt;     &lt;-3;b&gt;     &lt;-3;l&gt;
&lt;-2; &gt;     &lt;-3;a&gt;     &lt;-3;e&gt;
&lt;-7; &gt;     &lt;-2; &gt;     &lt;-2; &gt;
&lt;-3;b&gt;     &lt;-1; &gt;     &lt;-1; &gt;
&lt;-8; &gt;     &lt;11; &gt;     &lt;11; &gt;
&lt;11; &gt;     &lt;14; &gt;     &lt;14; &gt;
&lt;-3;l&gt;     &lt;15; &gt;     &lt;15; &gt;
&lt;15; &gt;     &lt;15; &gt;     &lt;15; &gt;
&lt;-5; &gt;     &lt;16; &gt;     &lt;16; &gt;
&lt;-3;e&gt;     &lt;17; &gt;     &lt;17; &gt;
&lt;15; &gt;     &lt;23; &gt;     &lt;23; &gt;
</PRE></UL>
<A NAME="sec7"><H3>See Also</H3></A>
<P><SAMP><A HREF="stable-sort.html">stable_sort()</A></SAMP>, <SAMP><A HREF="partial-sort.html">partial_sort()</A></SAMP>, <SAMP><A HREF="partial-sort-copy.html">partial_sort_copy()</A></SAMP></P>
<A NAME="sec8"><H3>Standards Conformance</H3></A>
<P><I>ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.3.1.1</I></P>

<BR>
<HR>
<A HREF="slice-array.html"><IMG SRC="images/bprev.gif" WIDTH=20 HEIGHT=21 ALT="Previous file" BORDER=O></A><A HREF="noframes.html"><IMG SRC="images/btop.gif" WIDTH=56 HEIGHT=21 ALT="Top of Document" BORDER=O></A><A HREF="booktoc.html"><IMG SRC="images/btoc.gif" WIDTH=56 HEIGHT=21 ALT="Contents" BORDER=O></A><A HREF="tindex.html"><IMG SRC="images/bindex.gif" WIDTH=56 HEIGHT=21 ALT="Index page" BORDER=O></A><A HREF="sort-heap.html"><IMG SRC="images/bnext.gif" WIDTH=20 HEIGHT=21 ALT="Next file" BORDER=O></A>

<!-- Google Analytics tracking code -->
<script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
</script>
<script type="text/javascript">
    _uacct = "UA-1775151-1";
    urchinTracker();
</script>
<!-- end of Google Analytics tracking code -->

</BODY>
</HTML>