CPP – Partial Sort Algorithm

We need not sort all elements sometimes.
Here are a few simple examples of STL algorithms partial_sort, nth_element, and partition.

partial_sort

For example, find the 5 biggest ones in 10 random numbers.

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> values;
    std::srand(std::time(nullptr));

    // create 10 number which in [0, 100]
    for( int i = 0; i < 10; ++i )
    {
        values.push_back( int( 1.0 * rand() / RAND_MAX * 100+ 0.5 ) );
    }

    for( auto i: values )
    {
        cout << i << "\t";
    }
    cout << endl;

    // sort to get 5 greatest number
    partial_sort( values.begin(), values.begin() + 5, values.end(), [](int a, int b)->bool{ return a > b; } );

    for( auto i: values )
    {
        cout << i << "\t";
    }
    cout << endl;        
    return 0;
}

output:

44 73 61 3 86 79 72 53 75 17
86 79 75 73 72 3 44 53 61 17

nth_element

The feature of algorithm of nth_element: the nth position which start at begin() is nth element after sort.
All elements before nth position are equal to nth_element or less than nth_element. But the elements before nth position may be not sorted.
So the algorithm is suitable to find nth element for a set.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
using namespace std;

std::vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};

void Show()
{
    for( auto it: v )
    {
        cout << it << "\t";
    }
    cout << endl;
}

int main()
{
    std::nth_element(v.begin(), v.begin() + v.size()/2, v.end());
    std::cout << "The median is " << v[v.size()/2] << '\n';
    Show();

    std::nth_element(v.begin(), v.begin()+1, v.end(), std::greater<int>());
    std::cout << "The second largest element is " << v[1] << '\n';
    Show();
}

output:

The median is 5
2 3 3 4 5 6 6 7 9   
The second largest element is 7
9 7 6 6 5 4 3 3 2

partition

The algorithm partition can help us to put all elements that meet user’s special condition at the head part.
It returns a iterator which points to the first one which doesn’t meet condition.
Be careful that the relative positions of elements may be changed after partition works.

int main()
{
    std::vector<int> v = {0,1,2,3,4,5,6,7,8,9};
    std::cout << "Original vector:\n ";
    for(auto it : v) std::cout << it << ' ';

    auto it = std::partition(v.begin(), v.end(), [](int i){return i % 2 == 0;});

    std::cout << "\nPartitioned vector:\n ";

    for_each( std::begin(v), it, [](int val){ cout << val << " "; } );
    std::cout << "* ";
    for_each( it, std::end(v), [](int val){ cout << val << " "; } );
}

output：

Original vector:
 0 1 2 3 4 5 6 7 8 9 
Partitioned vector:
 0 8 2 6 4 * 5 3 7 1 9