
Algorithm
A templatized algorithm for sorting collections of entities.
None
#include <algorithm>
template <class RandomAccessIterator>
void sort (RandomAccessIterator first,
RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first,
RandomAccessIterator last, Compare comp);
The sort algorithm sorts the elements in the range [first, last) using either the less than (<) operator or the comparison operator comp. If the worst case behavior is important, stable_sort or partial_sort should be used.
On average, sort performs approximately N(logN) comparisons, where N equals last - first.
//
// sort.cpp
//
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
using namespace std;
struct associate
{
int num;
char chr;
associate(int n, char c) : num(n), chr(c) {};
associate() : num(0), chr(`\0'){};
};
bool operator<(const associate &x, const associate &y)
{
return x.num < y.num;
}
ostream& operator<<(ostream &s, const associate &x)
{
return s << "<" << x.num << ";" << x.chr << ">";
}
int main ()
{
vector<associate>::iterator i, j, k;
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, ` `)};
// Set up vectors
vector<associate> v(arr, arr+20), v1((size_t)20),
v2((size_t)20);
// Copy original vector to vectors #1 and #2
copy(v.begin(), v.end(), v1.begin());
copy(v.begin(), v.end(), v2.begin());
// Sort vector #1
sort(v1.begin(), v1.end());
// Stable sort vector #2
stable_sort(v2.begin(), v2.end());
// Display the results
cout << "Original sort stable_sort" << endl;
for(i = v.begin(), j = v1.begin(), k = v2.begin();
i != v.end(); i++, j++, k++)
cout << *i << " " << *j << " " << *k << 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; >
If your compiler does not support default template parameters, then you always need to supply the Allocator template argument. For instance, you need to write:
vector<int, allocator<int> >
instead of:
vector<int>
If your compiler does not support namespaces, then you do not need the using declaration for std.
stable_sort, partial_sort, partial_sort_copy