C++ Coding Reference: sort() and stable_sort()

Nowadays, you don’t have to implement your sorting algorithms e.g. quicksort, selection sort, insertion sort etc by yourself. Most programming languages provide the functions/library to do the sorting efficiently, mostly in O(nlogN) time.

The simple sorting may be quicker for arrays with fewer elements, thus the sorting function provided in the library may consist of hybrid sorting algorithms, usually divide-and-conquer using quicksort or mergesort, then when the number of elements in the groups are smaller e.g. 20 to 30 numbers, switch to simple quadratic sorting algorithms e.g. selection sorting or insertion sort.

Ref: https://www.quora.com/When-should-one-use-Insertion-vs-Selection-sort
First of all, one should ask why use a quadratic sorting algorithm when asymptotically faster alternatives exists, like mergesort or quicksort. For small arrays (less than 20-30 elements), both insertion sort and selection sort are typically faster than the O(n*logn) alternatives. In fact, many sorting algorithms based on the divide and conquer paradigm switch to insertion sort or selection sort when the array is small enough.

Between insertion sort and selection sort, when to use which? Usually, insertion sort will perform less comparisons than selection sort, depending on the degree of “sortedness” of the array. While selection sort must scan the remaining parts of the array when placing an element, insertion sort only scans as many elements as necessary. That means that when the array is already sorted or almost sorted, insertion sort performs in O(n) time.

One advantage of selection sort over insertion sort, is that the number of writes (swaps) is in O(n), while in insertion sort it is in O(n^2). This may be important if you are sorting on Flash memory, for example, because writes reduce the lifespan of Flash memory.

Both sort() and stable_sort() are provided in the C++ header algorithms and you may want to use namespace std;.

C++ sort() – the unstable sorting

Given a vector of numbers, we can easily use the C++ sort() function to sort the numbers in place – the function takes three parameters, the first two are mandatory parameters i.e. the iterators denoting the start and end range. And the third parameter is the custom comparator – which is optional, if left out, it will use the smaller comparator, which results in the elements sorted in ascending order.

1
2
3

#include <algorithm>
vector<int> nums = { 5, 4, 6, 2, 9 };
sort(begin(nums), end(nums)); // nums will become { 2, 4, 5, 6, 9 };

#include <algorithm>
vector<int> nums = { 5, 4, 6, 2, 9 };
sort(begin(nums), end(nums)); // nums will become { 2, 4, 5, 6, 9 };

The above sort() defaults to the less comparator, which is essentially the same as using the std::less comparator:

1
2
3

#include <algorithm>
vector<int> nums = { 5, 4, 6, 2, 9};
sort(begin(nums), end(nums), std::less<int>()); // nums will become { 2, 4, 5, 6, 9 };

#include <algorithm>
vector<int> nums = { 5, 4, 6, 2, 9};
sort(begin(nums), end(nums), std::less<int>()); // nums will become { 2, 4, 5, 6, 9 };

The std::less is defined in C++ header file functional. And it is virtually the same as passing a lambda function:

1
2
3

#include <algorithm>
vector<int> nums = { 5, 4, 6, 2, 9};
sort(begin(nums), end(nums), [](auto &a, auto &b) { return a < b; }); // nums will become { 2, 4, 5, 6, 9 };

#include <algorithm>
vector<int> nums = { 5, 4, 6, 2, 9};
sort(begin(nums), end(nums), [](auto &a, auto &b) { return a < b; }); // nums will become { 2, 4, 5, 6, 9 };

Now, to sort the array in the reverse order, namely the non-ascending (or descending) order, we can use one of the following:

1
2
3
4

#include <algorithm>
vector<int> nums = { 5, 4, 6, 2, 9};
sort(begin(nums), end(nums), std::greater<int>()); // nums will become { 9, 6, 5, 4, 2 };
sort(begin(nums), end(nums), [](auto &a, auto &b) { return a > b; }); // nums will become { 9, 6, 5, 4, 2 };

#include <algorithm>
vector<int> nums = { 5, 4, 6, 2, 9};
sort(begin(nums), end(nums), std::greater<int>()); // nums will become { 9, 6, 5, 4, 2 };
sort(begin(nums), end(nums), [](auto &a, auto &b) { return a > b; }); // nums will become { 9, 6, 5, 4, 2 };

Here are the C++ template definitions for the std::less and std::greater custom comparators.

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

        // STRUCT TEMPLATE greater
template<class _Ty = void>
    struct greater
    {   // functor for operator>
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty first_argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty second_argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef bool result_type;
 
    constexpr bool operator()(const _Ty& _Left, const _Ty& _Right) const
        {   // apply operator> to operands
        return (_Left > _Right);
        }
    };
 
        // STRUCT TEMPLATE less
template<class _Ty = void>
    struct less
    {   // functor for operator<
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty first_argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty second_argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef bool result_type;
 
    constexpr bool operator()(const _Ty& _Left, const _Ty& _Right) const
        {   // apply operator< to operands
        return (_Left < _Right);
        }
    };

		// STRUCT TEMPLATE greater
template<class _Ty = void>
	struct greater
	{	// functor for operator>
	_CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty first_argument_type;
	_CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty second_argument_type;
	_CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef bool result_type;

	constexpr bool operator()(const _Ty& _Left, const _Ty& _Right) const
		{	// apply operator> to operands
		return (_Left > _Right);
		}
	};

		// STRUCT TEMPLATE less
template<class _Ty = void>
	struct less
	{	// functor for operator<
	_CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty first_argument_type;
	_CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty second_argument_type;
	_CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef bool result_type;

	constexpr bool operator()(const _Ty& _Left, const _Ty& _Right) const
		{	// apply operator< to operands
		return (_Left < _Right);
		}
	};

Similarly, there are less_equal and greater_equal for your conveniences. The sort() is not a stable sort, meaning that if the values of two elements are equal, after unstable sorting, the order of them may be swapped. We can take a look on how it affects in the following section i.e. stable_sort().

C++ stable_sort() – the stable sorting algorithm

The stable sorting algorithms guarantee that the order/sequence of the equal-value elements do not change after sorting. Syntactically, the usage of the stable_sort() is the same as aforementioned sort(). Let’s take the following example by using a vector of pairs (two integer pair) then we sort the array by comparing the first numbers (first integer in the pair).

1
2
3
4
5

vector<pair<int, int>> nums = { {5, 9}, {5, 2}, {3, 0}, {5, 3}, {1, 2}, {1, 4} 
    ....... /* lots of other pairs */ };
sort(begin(nums), end(nums), [](auto &a, auto &b) {
    return a.first < b.first;
});

vector<pair<int, int>> nums = { {5, 9}, {5, 2}, {3, 0}, {5, 3}, {1, 2}, {1, 4} 
    ....... /* lots of other pairs */ };
sort(begin(nums), end(nums), [](auto &a, auto &b) {
    return a.first < b.first;
});

After sort() the numbers in the array may become:

1

(1, 2), (1, 4), (3, 0), (5, 2), (5, 3), (5, 9) ... .... ....

(1, 2), (1, 4), (3, 0), (5, 2), (5, 3), (5, 9) ... .... ....

As we can see, there are three (5, ?) pairs, so they are consider equal – however, after unstable sort, the pairs are swapped from (5, 9), (5, 2), (5, 3) to (5, 2), (5, 3), (5, 9).

With unstable sort(), the order may not be guaranteed which means that you may get random sorted results. The stable_sort() should be used if you want to maintain the same order for those elements that are considered equal.

1
2
3
4
5

vector<pair<int, int>> nums = { {5, 9}, {5, 2}, {3, 0}, {5, 3}, {1, 2}, {1, 4}
/* lots of other pairs */ .... };
stable_sort(begin(nums), end(nums), [](auto &a, auto &b) {
    return a.first < b.first;
});

vector<pair<int, int>> nums = { {5, 9}, {5, 2}, {3, 0}, {5, 3}, {1, 2}, {1, 4}
/* lots of other pairs */ .... };
stable_sort(begin(nums), end(nums), [](auto &a, auto &b) {
    return a.first < b.first;
});

And you will be given the following array after stable_sort, for sure.

1

(1, 2), (1, 4), (3, 0), (5, 9), (5, 2), (5, 3) ....

(1, 2), (1, 4), (3, 0), (5, 9), (5, 2), (5, 3) ....

If you are using sort() or stable_sort() in your algorithm design interviews, be reminded that your overall complexity will be at least O(NLogN). If the number of the elements in the array is small e.g. less than 20, you probably won’t notice the differences between sort() and stable_sort() as both will be using the simple sorting e.g. selection sort or insertion sorting which are both stable sorting algorithms.

–EOF (The Ultimate Computing & Technology Blog) —