stable_sort()

Library:  Algorithms

Function

• Local Index
• Summary
• Synopsis
• Description
• Complexity
• Example
• See Also
• Standards Conformance

Generic algorithm for sorting collections of entities

#include <algorithm>

namespace std {
  template <class RandomAccessIterator>
  void stable_sort(RandomAccessIterator start, 
                   RandomAccessIterator finish);

  template <class RandomAccessIterator, class Compare>
  void stable_sort(RandomAccessIterator start,
                   RandomAccessIterator finish, Compare comp);
}

The stable_sort() algorithm sorts the elements in the range [start, finish) in ascending order. The first version of the algorithm uses operator<() for the sort. The second version uses the function object comp.

The stable_sort() algorithm is considered stable because the relative order of equivalent elements is maintained.

stable_sort() does approximately N * (log(N))2 comparisons, where N equals finish - start. The algorithm calls std::get_temporary_buffer<>() to obtain extra memory. If enough extra memory is available, it does at most N * log(N) comparisons (i.e., the same as sort()).

//
//  sort.cpp
//

#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>


struct associate
{
    int num;
    char chr;
    associate (int n, char c) : num (n), chr (c){};
    associate () : num (0), chr ('\0'){};
};


inline bool operator< (const associate &x, const associate &y)
{
    return x.num < y.num;
}


inline std::ostream& operator<< (std::ostream &s, 
                                 const associate &x)
{
    return s << '<' << x.num << ';' << x.chr << '>';
}


int main ()
{
    const associate arr [20] = {
        associate (-4, ' '), associate (16, ' '),
        associate (17, ' '), associate (-3, 's'),
        associate (14, ' '), associate (-6, ' '),
        associate (-1, ' '), associate (-3, 't'),
        associate (23, ' '), associate (-3, 'a'),
        associate (-2, ' '), associate (-7, ' '),
        associate (-3, 'b'), associate (-8, ' '),
        associate (11, ' '), associate (-3, 'l'),
        associate (15, ' '), associate (-5, ' '),
        associate (-3, 'e'), associate (15, ' ')};

    typedef std::vector<associate, std::allocator<associate> > 
            Vector;

    // Set up vectors.
    Vector v (arr, arr + sizeof arr / sizeof *arr);
    Vector v1 (sizeof arr / sizeof *arr);
    Vector v2 (sizeof arr / sizeof *arr);

    // Copy original vector to vectors #1 and #2.
    std::copy (v.begin (), v.end (), v1.begin ());
    std::copy (v.begin (), v.end (), v2.begin ());

    // Sort vector #1.
    std::sort (v1.begin (), v1.end ());

    // Stable sort vector #2.
    std::stable_sort (v2.begin (), v2.end ());

    // Display the results.
    std::cout << "Original    sort      stable_sort"
              << std::endl;
    for (Vector::iterator i = v.begin (), j = v1.begin (),
                          k = v2.begin ();
         i != v.end (); i++, j++, k++)
        std::cout << *i << "     " << *j << "     "
                  << *k << std::endl;

    return 0;
}


Program Output:

Original    sort      stable_sort
<-4; >     <-8; >     <-8; >
<16; >     <-7; >     <-7; >
<17; >     <-6; >     <-6; >
<-3;s>     <-5; >     <-5; >
<14; >     <-4; >     <-4; >
<-6; >     <-3;e>     <-3;s>
<-1; >     <-3;s>     <-3;t>
<-3;t>     <-3;l>     <-3;a>
<23; >     <-3;t>     <-3;b>
<-3;a>     <-3;b>     <-3;l>
<-2; >     <-3;a>     <-3;e>
<-7; >     <-2; >     <-2; >
<-3;b>     <-1; >     <-1; >
<-8; >     <11; >     <11; >
<11; >     <14; >     <14; >
<-3;l>     <15; >     <15; >
<15; >     <15; >     <15; >
<-5; >     <16; >     <16; >
<-3;e>     <17; >     <17; >
<15; >     <23; >     <23; >

sort(), partial_sort(), partial_sort_copy(), get_temporary_buffer()

ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.3.1.2