blob: 6b022220f93bd5546bbb188731a72a59dde86227 [file] [log] [blame]
 sort()
Apache C++ Standard Library Reference Guide

sort()

Library:  Algorithms

Function

Local Index

No Entries

Summary

A templatized algorithm for sorting collections of entities

Synopsis

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

Description

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.

Complexity

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

Example

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

See Also

stable_sort(), partial_sort(), partial_sort_copy()

Standards Conformance

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