partial_sort

For example, find the 5 biggest ones in 10 random numbers.
C++
#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 the algorithm of nth_element: the nth position which starts at begin() is nth element after the sort.
All elements before the nth position are equal to the nth element or less than the nth element. But the elements before the nth position may be not sorted.
So the algorithm is suitable to find the nth element for a set.
C++
#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 the user’s special condition at the head part.
It returns an iterator which points to the first one which doesn’t meet the condition.
Be careful that the relative positions of elements may be changed after partition works.
C++
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

0 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

You cannot copy content of this page