sort()

Module:  Standard C++ Library   Library:  Algorithms

Function

• Local Index
• Summary
• Synopsis
• Description
• Complexity
• Example
• See Also
• Standards Conformance

A templatized algorithm for sorting collections of entities

#include <algorithm>

namespace std {
  template <class RandomAccessIterator>
  void sort(RandomAccessIterator start, 
            RandomAccessIterator finish);
  template <class RandomAccessIterator, class Compare>
  void sort(RandomAccessIterator start, 
            RandomAccessIterator finish, Compare comp);
}

The sort() algorithm sorts the elements in the range [start, finish) in ascending order using either operator<() or the function object comp. The algorithm is not stable; that is, it does not preserve the order of elements that are equivalent (i.e., those for which (a < b && b < a) == false). If maintaining such an ordering is is important, stable_sort() should be used instead. sort() is implemented using introsort.

sort() performs approximately N * log(N) comparisons in the worst case, where N equals finish - start.

//
//  sort.cpp
//

#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>


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


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


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


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<associate, std::allocator<associate> > 
            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 << "Original    sort      stable_sort"
              << std::endl;
    for (Vector::iterator i = v.begin (), j = v1.begin (),
                          k = v2.begin ();
         i != v.end (); i++, j++, k++)
        std::cout << *i << "     " << *j << "     "
                  << *k << std::endl;

    return 0;
}


Program Output:

Original    sort      stable_sort
<-4; >     <-8; >     <-8; >
<16; >     <-7; >     <-7; >
<17; >     <-6; >     <-6; >
<-3;s>     <-5; >     <-5; >
<14; >     <-4; >     <-4; >
<-6; >     <-3;e>     <-3;s>
<-1; >     <-3;s>     <-3;t>
<-3;t>     <-3;l>     <-3;a>
<23; >     <-3;t>     <-3;b>
<-3;a>     <-3;b>     <-3;l>
<-2; >     <-3;a>     <-3;e>
<-7; >     <-2; >     <-2; >
<-3;b>     <-1; >     <-1; >
<-8; >     <11; >     <11; >
<11; >     <14; >     <14; >
<-3;l>     <15; >     <15; >
<15; >     <15; >     <15; >
<-5; >     <16; >     <16; >
<-3;e>     <17; >     <17; >
<15; >     <23; >     <23; >

stable_sort(), partial_sort(), partial_sort_copy()

ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.3.1.1

Copyright (c) 1994-2006 Rogue Wave Software, a Quovadx Division.
Licensed under the Apache License, Version 2.0.
Contact Rogue Wave about documentation or support issues. You can also seek help from other developers through the Apache stdcxx community (see below).