stable_sort


function template
<algorithm> 
template <class RandomAccessIterator>
  void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
  void stable_sort ( RandomAccessIterator first, RandomAccessIterator last,
                     Compare comp );

Sort elements preserving order of equivalents

Sorts the elements in the range [first,last) into ascending order, like sort, but stable_sort grants that the relative order of the elements with equivalent values is preserved.

The elements are compared using operator< for the first version, and comp for the second.

Parameters

first, last
Random-Access iterators to the initial and final positions of the sequence to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
comp
Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.


Return value

none

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
// stable_sort example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool compare_as_ints (double i,double j)
{
  return (int(i)<int(j));
}

int main () {
  double mydoubles[] = {3.14, 1.41, 2.72, 4.67, 1.73, 1.32, 1.62, 2.58};

  vector<double> myvector;
  vector<double>::iterator it;

  myvector.assign(mydoubles,mydoubles+8);

  cout << "using default comparison:";
  stable_sort (myvector.begin(), myvector.end());
  for (it=myvector.begin(); it!=myvector.end(); ++it)
    cout << " " << *it;

  myvector.assign(mydoubles,mydoubles+8);

  cout << "\nusing 'compare_as_ints' :";
  stable_sort (myvector.begin(), myvector.end(), compare_as_ints);
  for (it=myvector.begin(); it!=myvector.end(); ++it)
    cout << " " << *it;

  cout << endl;

  return 0;
}


compare_as_ints is a function that compares only the integral part of the elements, therefore, elements with the same integral part are considered equivalent. stable_sort preserves the relative order these had before the sorting. Output:
using default comparison: 1.32 1.42 1.62 1.73 2.58 2.72 3.14 4.67
using 'compare_as_ints' : 1.41 1.73 1.32 1.62 2.72 2.58 3.14 4.67



Complexity

Between N*logN and N*(LogN^2) comparisons (where N is last-first).

See also

sort Sort elements in range (function template)
partial_sort Partially Sort elements in range (function template)
search Find subsequence in range (function template)
reverse Reverse range (function template)