I have forgotten

• https://me.yahoo.com

# stable_sort

Sorts while preserving order of equal elements

## 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`.

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