The Stability Of Sorting Algorithm

If two numbers are equal and the relative positions are not changed after sorting, we think the sorting algorithm is stable.
Stable sort algorithm: bubble sort, insert sort and merge sort.
Unstable sort algorithm: quick sort, heap sort.

Introduce an unstable sort algorithm quick sort. Its core thought is divide and conquer.
1. Take a number from list as a basic number.
2. Put the elements which are bigger than it to the right, the elements which are smaller or equal to it to the left.
3. Repeat the second step for the left and the right intervals until there is only one number in every interval.

The experimental example:
Create a tree structure which contains number and height, we sort elements by value height.

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

using namespace std;

struct Tree
{
    int number;
    int height;
    Tree(const int _number, const int _height)
    {
        number = _number;
        height = _height;
    }
    friend ostream& operator << (ostream &out, Tree &object)
    {
        out << "(" << object.number << ", " << object.height << ")";
        return out;
    }
};

int main()
{
    std::vector<Tree> vec;
    for( int i = 0; i < 10; ++i )
    {
        int randomHeight = (i+1)*10;
        if( i&1 )
        {
            randomHeight = 0;
        }
        vec.push_back( Tree(1+i, randomHeight) );
    }
    for(auto it: vec)
    {
        cout << it << "\t";
    }
    cout << endl;

    sort( vec.begin(), vec.end(), 
        //冒泡排序的分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
        [](const Tree t1, const Tree t2)->bool { 
            if( t1.height <= t2.height )
                return true; 
            return false; 
        } 
        );

    for(auto it: vec)
    {
        cout << it << "\t";
    }
    cout << endl;
 }

Output:

(1, 10) (2, 0) (3, 30) (4, 0) (5, 50) (6, 0) (7, 70) (8, 0) (9, 90) (10, 0) 
(10, 0) (8, 0) (6, 0) (4, 0) (2, 0) (1, 10) (3, 30) (5, 50) (7, 70) (9, 90)

The element which height is 0 has changed position.
Let’s use the stable sort algirthm bubble sort to process all elements.

    for( int i = 0; i < 10; ++i )
    {
        for( int j = 0; j < 10 - i -1; ++j )
        {
            if( vec[j].height > vec[j+1].height )
            {
                swap( vec[j], vec[j+1] );
            }
        }
    }

Output:

(1, 10) (2, 0) (3, 30) (4, 0) (5, 50) (6, 0) (7, 70) (8, 0) (9, 90) (10, 0) 
(2, 0) (4, 0) (6, 0) (8, 0) (10, 0) (1, 10) (3, 30) (5, 50) (7, 70) (9, 90)

The function swap can work because C++ had provided copy constuct function for structure.
The implement version for swap comes from google – libcxx：

template <class _Tp>
inline _LIBCPP_INLINE_VISIBILITY
#ifndef _LIBCPP_HAS_NO_ADVANCED_SFINAE
typename enable_if
<
    is_move_constructible<_Tp>::value &&
    is_move_assignable<_Tp>::value
>::type
#else
void
#endif
swap(_Tp& __x, _Tp& __y) _NOEXCEPT_(is_nothrow_move_constructible<_Tp>::value &&
                                    is_nothrow_move_assignable<_Tp>::value)
{
    _Tp __t(_VSTD::move(__x));
    __x = _VSTD::move(__y);
    __y = _VSTD::move(__t);
}