How to find the maximum and minimum value in an array without using if statement.Are there any built in function in to do so in c++? If not is insertion sort the only way?Thanks in advance.
3
-
is the function allowed to use if statements internallyaaronman– aaronman2013-11-20 07:40:59 +00:00Commented Nov 20, 2013 at 7:40
-
1There are some tricks to do it without branching that would presumably meet your needs. Not for the faint of heart. :) graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMaxRetired Ninja– Retired Ninja2013-11-20 08:27:53 +00:00Commented Nov 20, 2013 at 8:27
-
@RetiredNinja's link has examples of branchless conditionals using masks. That's also an approach to vectorize a loop that has a conditional (either manually or done for you by the compiler).Adam– Adam2013-11-20 09:46:35 +00:00Commented Nov 20, 2013 at 9:46
Add a comment
|
2 Answers
Use std::minmax_element if you use C++11, or std::min_element/std::max_element if no.
std::vector<int> v = {1,2,3,4};
auto minmax = std::minmax_element(v.begin(), v.end());
// now minmax.first points on 1 and minmax.second points on 4
However, if if condition should not be used internally - you can use following thing
template<typename Iterator>
std::pair<Iterator, Iterator> minmax_element(Iterator first, Iterator last)
{
Iterator min = first, max = first;
while (first != last)
{
min = *min > *first ? first : min;
max = *max > *first ? max : first;
++first;
}
return std::make_pair(min, max);
}
3 Comments
aaronman
I'm not sure if his question is just unclear but obviously minmax uses if statements internally, and you can do it without
ForEveR
@aaronman Of course it uses if internally, however
sort without if statement is also not simple thing.aaronman
He didn't say anything about sorting, but it's relatively easy to write a function that does the same thing as minmax, of course I could be totally off on my interpretation of his problem
First of all, you can implement function sort(a, b), which returns pair of sorted values. To do it you can use following idea: min(a, b) = (a+b)/2 - |a-b|/2 and max(a, b) = (a+b)/2 + |a-b|/2.
But here you have function |x|=abs(x), which uses 'if' inside. So, we should implement 'abs' without any 'if'. One of the simpliest ways is following: abs(x) = sqrt(x*x) (it is very slow, but it is only an idea). For integer values you can use these approaches: 1, 2, etc.
So, you can implement function sort(a,b) which sorts only pair of values without any 'if'. After it you can use this function to sort the array. After it first element of that sorted array will be minimum value and last element will be maximum element.
