Computing › Stl › Algorithms › Sorting ›

stable_sort

Sorts while preserving order of equal elements

View version details

Contents

Definition
Interface
Description
Return Value
Complexity
Page Comments

Key Facts

Gyroscopic Couple: The rate of change of angular momentum ( $\inline \tau$ ) = $\inline I\omega\Omega$ (In the limit).

$\inline I$ = Moment of Inertia.
$\inline \omega$ = Angular velocity
$\inline \Omega$ = Angular velocity of precession.

Blaise Pascal (1623-1662) was a French mathematician, physicist, inventor, writer and Catholic philosopher.

Leonhard Euler (1707-1783) was a pioneering Swiss mathematician and physicist.

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

http://msdn.microsoft.com/en-us/

stable_sort

Key Facts

Definition

Interface

Description

Return Value

Complexity

References

Example - stable_sort algorithm

See Also