Algorithms - Sort

Overview

Sorting Algorithms  operate on various types of containers such as sequence, associative and unordered to perform actions such as sorting.

These function accepts parameters like 

• iterators such as forward, input, randomaccess 
• predicates such as binary 

The parameter type  Compare is a function that accepts two inputs and returns bool value (true or false). 

For example, bool issame(int i, int j) {return i == j;} or [](int i, int j) {return i == j;}

Details

Name	Description
void sort ( RandomAccessIterator first, RandomAccessIterator last) void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp)	Sorts the elements in the range [first,last) into ascending order. The elements are compared using operator< for the first version, and comp for the second.
Example vector<int> v{2,5,3,1,4}; //1 //v:{1,2,3,4,5} sort (begin(v), end(v)); //2 //v:{5,4,3,2,1} sort (begin(v), end(v), greater<int>());
void stable_sort (  RandomAccessIterator first, RandomAccessIterator last ) void stable_sort (  RandomAccessIterator first, RandomAccessIterator last,  Compare comp )	Same as sort except it preserves the relative order of the elements with equivalent values. The elements are compared using operator< for the first version, and comp for the second.
Example struct associate {int num; char chr; }; bool operator < (associate a, associate b) { return a.num < b.num; } bool operator > (associate a, associate b) { return a.num > b.num; } vector<associate> v; //1 v.assign( { {-4, ' '}, {16, ' '}, {17, ' '}, {-3, 's'}, {14, ' '}, {-6, ' '}, {-1, ' '}, {-3, 't'}, {23, ' '}, {-3, 'a'}, {-2, ' '}, {-7, ' '}, {-3, 'b'}, {-8, ' '}, {11, ' '}, {-3, 'l'}, {15, ' '}, {-5, ' '}, {-3, 'e'}, {15, ' '} }); /* v:{ {-8, ' '}, {-7, ' '}, {-6, ' '}, {-5, ' '}, {-4, ' '}, {-3, 's'}, {-3, 't'}, {-3, 'a'}, {-3, 'b'}, {-3, 'l'}, {-3, 'e'}, {-2, ' '}, {-1, ' '}, {11, ' '}, {14, ' '}, {15, ' '}, {15, ' '}, {16, ' '}, {17, ' '}, {23, ' '}, } */ stable_sort(begin(v), end(v)); //2 v.assign( { {-4, ' '}, {16, ' '}, {17, ' '}, {-3, 's'}, {14, ' '}, {-6, ' '}, {-1, ' '}, {-3, 't'}, {23, ' '}, {-3, 'a'}, {-2, ' '}, {-7, ' '}, {-3, 'b'}, {-8, ' '}, {11, ' '}, {-3, 'l'}, {15, ' '}, {-5, ' '}, {-3, 'e'}, {15, ' '} }); /* v:{ {-8, ' '}, {-7, ' '}, {-6, ' '}, {-5, ' '}, {-4, ' '}, {-3, 's'}, {-3, 't'}, {-3, 'a'}, {-3, 'b'}, {-3, 'l'}, {-3, 'e'}, {-2, ' '}, {-1, ' '}, {11, ' '}, {14, ' '}, {15, ' '}, {15, ' '}, {16, ' '}, {17, ' '}, {23, ' '}, } */ stable_sort(rbegin(v), rend(v), greater<associate>());
void partial_sort ( RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last) void partial_sort ( RandomAccessIterator first, RandomAccessIterator middle,  RandomAccessIterator last, Compare comp)	Partially sort elements [first,last], in such a way that the elements before middle are the smallest elements in the entire range and are sorted in ascending order, while the  remaining elements are left without any specific order. The elements are compared using operator< for the first version, and comp for the second.
Example vector<int> v; //1 v.assign({5,2,4,3,1}); //v:{1,2,3,5,4} partial_sort (begin(v), begin(v)+3, end(v)); //2 v.assign({5,2,4,3,1}); //v:{2, 1, 3, 4, 5 } partial_sort (rbegin(v), rbegin(v)+3, rend(v),greater<int>());
RandomAccessIterator partial_sort_copy( InputIterator first, InputIterator last,  RandomAccessIterator obeg,  RandomAccessIterator oend) RandomAccessIterator partial_sort_copy( InputIterator first, InputIterator last,  RandomAccessIterator obeg, RandomAccessIterator oend,  Compare comp)	Copies the smallest elements in the range [first,last] to [obeg,oend], sorting the elements copied.  The range [first,last) is not modified. The elements are compared using operator< for the first version, and comp for the second.
Example vector<int> v(3),v2; //1 v2.assign({5,2,4,3,1}); //v:{1,2,3,5,4} partial_sort_copy (begin(v2), end(v2), begin(v), end(v)); //2 v2.assign({5,2,4,3,1}); //v:{2, 1, 3, 4, 5 } partial_sort_copy (rbegin(v2), rend(v2), begin(v), end(v),greater<int>());
bool is_sorted ( ForwardIterator first, ForwardIterator last) bool is_sorted ( ForwardIterator first, ForwardIterator last, Compare comp)	Check whether range is sorted.  Returns true if the range [first,last] is sorted into ascending order.  The elements are compared using operator< for the first version, and comp for the second.
Example vector<int> v; cout << boolalpha; //1 v.assign({5,2,4,3,1}); //prints false cout << is_sorted(begin(v), end(v)) << endl; //v:{1,2,3,5,4} sort (begin(v), end(v)); //prints true cout << is_sorted(begin(v), end(v)) << endl; //2 v.assign({5,2,4,3,1}); //prints false cout << is_sorted(rbegin(v), rend(v), greater<int>()) << endl; //v:{1,2,3,5,4} sort (rbegin(v), rend(v), greater<int>()); //prints true cout << is_sorted(rbegin(v), rend(v),greater<int>()) << endl;
ForwardIterator is_sorted_until ( ForwardIterator first, ForwardIterator last) ForwardIterator is_sorted_until ( ForwardIterator first, ForwardIterator last, Compare comp)	Find first unsorted element in range.  Returns an iterator to the first element in the range [first,last] which does not follow an ascending order.  The range between first and the iterator returned is sorted. If the entire range is sorted, the function returns last. The elements are compared using operator< for the first version, and comp for the second.
Example vector<int> v{1,2,4,3,4,5,6}; //1 //itr:begin()+3 auto itr = is_sorted_until(begin(v), end(v)); //2 //ritr:rbegin()+4 auto ritr = is_sorted_until(rbegin(v), rend(v), greater<int>());
void nth_element ( RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last) void nth_element ( RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp)	Rearranges the elements in the range [first,last], in such a way that the element at the nth position is the element that would be in that position in a sorted sequence. The other elements are left without any specific order, except that none of the elements preceding nth are  greater than it, and none of the elements following it are less. The elements are compared using operator< for the first version, and comp for the second.
Example vector<int> v; //1 v.assign({1,3,2,5,4}); //v:{1, 2, 3, 5, 4} nth_element(begin(v), begin(v)+2, end(v)); //2 v.assign({1,3,2,5,4}); //v:{5, 4, 3, 2, 1 } nth_element(begin(v), begin(v)+2, end(v),greater<int>());

The example depicts the usage.

Summary of Examples

Name	Description	github	wandbox
Example	Usage	source    output	source + output