Recover Password

Or login with:

  • Facebookhttp://facebook.com/
  • Googlehttps://www.google.com/accounts/o8/id
  • Yahoohttp://yahoo.com/
advanced search

Valid RSS

Computing › Stl › Algorithms › Sorting ›

stable_sort

Sorts while preserving order of equal elements
+ View version details
Contents
  1. Definition
  2. Interface
  3. Description
  4. Return Value
  5. Complexity
  6. Page Comments

Definition

The stable_sort() algorithm is defined in the standard header <algorithm> and in the nonstandard backward-compatibility header <algo.h>.

Interface

#include <algorithm>
template < class BidirectionalIterator >
   void stable_sort(
      BidirectionalIterator first, 
      BidirectionalIterator last
   );
template < class BidirectionalIterator, class BinaryPredicate >
   void stable_sort(
      BidirectionalIterator first, 
      BidirectionalIterator last,
      BinaryPredicate comp
   );

Parameters:
Parameter Description
first A bidirectional iterator addressing the position of the first element in the range to be sorted
last A bidirectional iterator addressing the position one past the final element in the range to be sorted
comp User-defined predicate function object that defines the comparison criterion to be satisfied by successive elements in the ordering. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied

Description

Stable_sort function sorts a range (like the sort function) but keeps the order of equivalent elements.

The first version compares objects using operator<, and the second compares objects using a function object comp.

Return Value

None.

Complexity

The run-time complexity depends on the amount of memory available. Worst-case behavior (if no auxiliary memory is available) is N (log N)^2 comparisons, where N is last - first, and best case (if a large enough auxiliary memory buffer is available) is N (log N).

References

Example:

Example - stable_sort algorithm
Problem
The following example demonstrates the use of stable_sort():
Workings
#include <vector>
#include <algorithm>
#include <functional>     
#include <iostream>
 
using namespace std;
 
// Return if first element is greater than the second
bool UDgreater (int elem1, int elem2 )
{
  return elem1 > elem2;
}
 
int main()
{
  vector <int> v1;
  vector <int>::iterator Iter1;
 
  int i;
  for (i = 0; i <= 5; i++)
  {
    v1.push_back( 2*i );
  }
 
  for (i = 0; i <= 5; i++)
  {
    v1.push_back( 2*i );
  }
 
  cout <<"Original vector v1 = ( " ;
  for (Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
    cout <<*Iter1<<" ";
  cout <<")"<<endl;
 
  stable_sort(v1.begin( ), v1.end( ) );
  cout <<"Sorted vector v1 = ( " ;
  for (Iter1 = v1.begin( ); Iter1 != v1.end( ); Iter1++)
      cout <<*Iter1<<" ";
  cout <<")"<<endl;
 
  // To sort in descending order, specify binary predicate
  stable_sort(v1.begin( ), v1.end( ), greater<int>( ) );
  cout <<"Resorted (greater) vector v1 = ( " ;
  for (Iter1 = v1.begin( ); Iter1 != v1.end( ); Iter1++)
    cout <<*Iter1<<" ";
  cout <<")"<<endl;
 
  // A user-defined (UD) binary predicate can also be used
  stable_sort(v1.begin( ), v1.end( ), UDgreater );
  cout <<"Resorted (UDgreater) vector v1 = ( " ;
  for (Iter1 = v1.begin( ); Iter1 != v1.end( ); Iter1++)
    cout <<*Iter1<<" ";
  cout <<")"<<endl;
 
  return 0;
}
Solution
Output:

Original vector v1 = ( 0 2 4 6 8 10 0 2 4 6 8 10 )
Sorted vector v1 = ( 0 0 2 2 4 4 6 6 8 8 10 10 )
Resorted (greater) vector v1 = ( 10 10 8 8 6 6 4 4 2 2 0 0 )
Resorted (UDgreater) vector v1 = ( 10 10 8 8 6 6 4 4 2 2 0 0 )
References

See Also

Last Modified: 2012-01-07 21:08:30     Page Rendered: 2012-05-21 15:03:43
 

Page Comments

 
 Format Excel Equations

  You must login to leave a messge