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 << '\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
``````
Categories: AlgorithmCPlusPlus

Article Rating
Subscribe
Notify of 