The stable_sort function in C++ is employed to arrange the elements within the range [first, last) in ascending order, similar to sort function, while preserving the sequence of equivalent elements.
The elements are assessed with the < operator in the initial iteration, and with comp in the subsequent iteration.
Syntax
template <class RandomAccessIterator>
void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );
template <class RandomAccessIterator, class Compare>
void stable_sort ( RandomAccessIterator first, RandomAccessIterator last,
Compare comp );
Parameter
A bidirectional iterator that points to the initial element within the range intended for sorting.
last : A bidirectional iterator indicating the element before the last one in the range intended to be sorted.
A custom binary predicate function named "comp" is defined by the user to evaluate whether two arguments are in a specific order. It returns true if the arguments are in the desired order, otherwise, it returns false. This function adheres to the strict weak ordering principle to arrange the elements accordingly.
Return value
Complexity
The time complexity during execution is influenced by the quantity of memory accessible.
If there is adequate additional memory accessible, the complexity scales linearly with the span from the initial to the final point. It executes a maximum of N*log2(N) comparisons of elements, where N equals the difference between the last and first indexes.
If additional memory is not accessible, then the time complexity increases proportionally with the distance from the initial to the final element. The algorithm executes a maximum of N*log2(N) element comparisons, where N represents the difference between the last and first elements.
Data races
The items within the range [first, last) are altered.
Exceptions
This function will raise an exception in the event that any comparison of elements, swapping of elements, or operation on an iterator results in an exception.
Please note that invalid parameters cause an undefined behavior.
Example 1
Let's explore a straightforward example to showcase the functionality of stable_sort:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> v = {3, 1, 4, 2, 5};
cout<<"Before sorting: ";
for_each(v.begin(), v.end(), [](int x) {
cout << x << " ";
});
stable_sort(v.begin(), v.end());
cout<<"\nAfter sorting: ";
for_each(v.begin(), v.end(), [](int x) {
cout << x << " ";
});
return 0;
}
Output:
Before sorting: 3 1 4 2 5
After sorting: 1 2 3 4 5
Example 2
Let's see another simple example:
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Employee {
Employee(int age, string name) : age(age), name(name) { }
int age;
string name; // Does not particpate in comparisons
};
bool operator<(const Employee &lhs, const Employee &rhs) {
return lhs.age < rhs.age;
}
int main()
{
vector<Employee> v = {
Employee(58, "Robin"),
Employee(23, "Bob"),
Employee(60, "Devid"),
};
stable_sort(v.begin(), v.end());
cout<<"Age : Name "<<endl<<"-----------\n";
for (const Employee &e : v) {
cout << e.age << " : " << e.name << '\n';
}
return 0;
}
Output:
Age : Name
-----------
23 : Bob
58 : Robin
60 : Devid
Example 3
Let's see another simple example:
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
struct Student {
string name;
int sec;
char group;
};
bool compBySec(Student a, Student b)
{
return a.sec < b.sec;
}
bool compByGroup(Student a, Student b)
{
return a.group < b.group;
}
bool compByName(Student a, Student b)
{
return a.name < b.name;
}
void print(const vector <Student>& v)
{
cout << "Name \tSec\tGroup" << "\n-------------------------"<<endl;
for (unsigned int i = 0; i < v.size(); i++)
{
cout << v[i].name << "\t" << v[i].sec<< "\t"
<< v[i].group << endl;
}
}
int main()
{
vector <Student> Students;
string name[] = {"Anjali", "Bob", "Chinu ", "Faizal ",
"Nikita ", "Deep ", "Aman", "Rohit "};
int sec[] = {3, 4, 3, 3, 1, 4, 3, 2};
int group[] = {'A', 'C', 'A', 'A', 'A', 'B', 'B', 'A'};
for (int i = 0; i < 8; i++)
{
Student p;
p.name = name[i];
p.sec = sec[i];
p.group = group[i];
Students.push_back(p);
}
stable_sort(Students.begin(), Students.end(), compByName);
cout << "Stable Sort by name" << endl;
print(Students);
cout << endl;
stable_sort(Students.begin(), Students.end(), compBySec);
cout << "Stable Sort by section" << endl;
print(Students);
return 0;
}
Output:
Stable Sort by name
Name Sec Group
-------------------------
Aman 3 B
Anjali 3 A
Bob 4 C
Chinu 3 A
Deep 4 B
Faizal 3 A
Nikita 1 A
Rohit 2 A
Stable Sort by section
Name Sec Group
-------------------------
Nikita 1 A
Rohit 2 A
Aman 3 B
Anjali 3 A
Chinu 3 A
Faizal 3 A
Bob 4 C
Deep 4 B
Example 4
Let's see another simple example:
#include <vector>
#include <algorithm>
#include <functional> // For greater<int>( )
#include <iostream>
// Return whether first element is greater than the second
bool UDgreater (int elem1, int elem2 )
{
return elem1 > elem2;
}
int main( )
{
using namespace std;
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 )
