stable_sort

     Algorithm

Templated algorithm for sorting collections of entities.

Contents

• Synopsis
• Description
• Complexity
• Example
• Warning
• See Also

#include <algorithm>

template <class RandomAccessIterator>
void stable_sort (RandomAccessIterator first, 
                  RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void stable_sort (RandomAccessIterator first,
                  RandomAccessIterator last,
                  Compare comp);

The stable_sort algorithm sorts the elements in the range [first, last). The first version of the algorithm uses less than (<) as the comparison operator for the sort. The second version uses the comparision function comp.

The stable_sort algorithm is considered stable because the relative order of the equal elements is preserved.

stable_sort does at most N(logN) **2, where N equals last -first, comparisons; if enough extra memory is available, it is NlogN.

//
// sort.cpp
//
 #include <vector>
 #include <algorithm>
 #include <functional>
 #include <iostream.h>
 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;
 }
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 need to always supply the Allocator template argument. For instance, you will need to write :

vector<int, allocator>

instead of :

vector<int>

sort, partial_sort, partial_sort_copy