Library: Algorithms
Function
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