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 http://www.codecogs.com/reference/computing/stl/algorithms/sorting/sort.php"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 1
The following example demonstrates the use of stable_sort():
#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;
}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 )