Simultaneous minimum and maximum

Question

I've tried to implement an algorithm that would search for both minimum and maximum elements in a given array, and used the ideas from Cormen's Introduction to Algorithms. My code compiles and starts working, outputs the generated random array and then does nothing for a really long time. Why could that be?

The code is this:

// fast min and max --cormen exercise 1.cpp: entry point
//implemented from a verbal description in cormen's book, p 243

#include "stdafx.h"
#include <vector>
#include <ctime>
#include <cstdlib>
#include <iostream>

struct min_and_max
{
    int min, max;
};


min_and_max find_min_and_max(std::vector<int>& A)
{
    int n = A.size();
    int min, max;
    if (n%2 == 1)
        min = max = A[0];
    if (n%2 == 0)
        if (A[0] < A[1])
        {
            min = A[0];
            max = A[1];
        }
        else
        {
            min = A[1];
            max = A[0];
        }
    for(int i = 2; i < A.size(); (i + 2))
    {
        if (A[i] < A[i+1])
        {
            if (min > A[i])
                min = A[i];
            if (max < A[i+1])
                max = A[i+1];
        }
        else
        {
            if (min > A[i+1])
                min = A[i+1];
            if (max < A[i])
                max = A[i];
        }
    }
    min_and_max result;
    result.min = min;
    result.max = max;

    return result;
}

int main()
{
    std::srand(std::time(0));
    std::vector<int> A(10);
    for (auto i = 0; i < A.size(); i++)
        {
            A[i] = rand() % 1000;
            std::cout << A[i] << " ";           
        }
    std::cout << std::endl; //IT GOES AS FAR AS THIS
    std::cout << "The array has been analyzed; its' minimum is " << find_min_and_max(A).min << "and its' maximum is " << find_min_and_max(A).max << std::endl;

    return 0;
}

As a side note, you can use `std:pair` to store both min and max values, instead of creating your own pair, also you can make `typedef pair min_and_max` — higuaro, Oct 14 '13 at 20:21
Now the code runs properly, I can wonder about that: I have used `std::pair` in a previous version of this code, and then I somehow got the impression that a `struct` is faster. Is it really? — Chiffa, Oct 14 '13 at 20:24
Incidentally, why are you making your algorithm this complicated? What's wrong with the [naive implementation](http://pastebin.com/nHPpzWNi)? — Matteo Italia, Oct 14 '13 at 20:25
@Chiffa: `std::pair` is a struct almost identical to the one you used; also, the time used by your function is dominated by the loop looking for min/max, a difference in the return type is going to be negligible anyway. — Matteo Italia, Oct 14 '13 at 20:27
Nothing, I guess. My idea was to write code that'd implement an algorithm's logic clearly - which, I hope, it does. It could probably be rewritten and simplified, but that's for tomorrow :-) — Chiffa, Oct 14 '13 at 20:28
@MatteoItalia, well, then I'd fall back to trusting the STL when in doubt. — Chiffa, Oct 14 '13 at 20:31
it isn't it enough with a loop? `int maxval = INT_MIN; int minval = INT_MAX; for (auto& i : A ) { maxval = std::max( maxval, i ); minval = std::min( minval, i ); }` — AndersK, Oct 14 '13 at 20:31
Your struct is same as `std::pair` but with better member names. — Pete Becker, Oct 14 '13 at 20:37
It depends on the implementation, but basically it should be a template for a struct, check this implementation for [example](http://cs.brown.edu/~jwicks/libstdc++/html_user/stl__pair_8h-source.html) — higuaro, Oct 14 '13 at 20:47
In case you didn't know, there is a standard library algorithm for this called [`std::minmax_element`](http://en.cppreference.com/w/cpp/algorithm/minmax_element). — Blastfurnace, Oct 14 '13 at 21:05
Your problem is solved, but you still have an error. Try testing with `{1,9,2,8,3}`. — Mark Ransom, Oct 14 '13 at 21:16
Tried it, yes, it outputs a wrong maximum. Could you please give a hint about the error? — Chiffa, Oct 14 '13 at 22:44
Also, how did you come up with this input in the first place? — Chiffa, Oct 14 '13 at 22:50
Look at the `for` loop and its limits, along with the code in the loop. That's what I did when I noticed the bug, then I worked backwards to create a test case. — Mark Ransom, Oct 15 '13 at 16:05

score 7 · Accepted Answer · answered Oct 14 '13 at 20:18

7

 for(int i = 2; i < A.size(); (i + 2))

i + 2 won't change the value of i, you need to use i += 2.

answered Oct 14 '13 at 20:18

Zac Wrangler

1,445
9
8

Thanks, didn't really know how to write this increment properly. – Chiffa Oct 14 '13 at 20:21
Normally we use i++ which compiler interprets as 2 things return i and also increment it. http://stackoverflow.com/questions/24853/what-is-the-difference-between-i-and-i – Nishant Oct 14 '13 at 20:36
2

@Nishant `i++` is used when you want to increment it by 1 and it would better be `++i`. – Zac Wrangler Oct 14 '13 at 20:44

score 4 · Answer 2 · answered Oct 14 '13 at 20:19

4

The problem lies here:

for(int i = 2; i < A.size(); (i + 2))

You never actually increment i, thus causing an infinite loop.

change it to:

for(int i = 2; i < A.size(); i+=2)

answered Oct 14 '13 at 20:19

pippin1289

4,861
2
22
37

score 2 · Answer 3 · edited May 23 '17 at 10:31

Additional to the given answers, if you're using c++11 you can simplify your algorithm using lambdas and the std::for_each function:

#include <algorithm>
#include <iostream>
#include <cmath>

int main() { 
    int array[] = { -8, 8, 0, 9, 5, -3, 4, 6, -1, 15, 31 };
    int min, max;
    // User std::for_each(v.begin(), v.end(), ...) for either vector or list
    std::for_each(std::begin(array), std::end(array), [&min, &max](int elem) { 
        max = std::max(max, elem);
        min = std::min(min, elem);
    });
    std::cout << min << ", " << max << std::endl;
    return 0;
}

And maybe it could be even simpler

Update: As @Blastfurnace pointed out, the std::minmax_element function could be used to further reduce the code needed for searching both the min and max element, yielding this shorter version:

#include <algorithm>
#include <iostream>
#include <vector>   

int main() { 
    std::vector<int> values = { -8, 8, 0, 9, 5, -3, 4, 6, -1, 15, 31 };
    auto minAndMax = std::minmax_element(values.begin(), values.end());
    std::cout << *minAndMax.first << ", " << *minAndMax.second << std::endl;
    return 0;
}

Is important to note that everything done in this answer, besides being OT, is for the sake of learning, to give the OP alternatives to improve his (or her) work and help other users that could have the same requirement.

If you are using `C++11` it might make more sense to just use [`std::minmax_element`](http://en.cppreference.com/w/cpp/algorithm/minmax_element) — Blastfurnace, Oct 14 '13 at 21:00
As I, personally, like lambdas, I would probably use them. As for the `std::minmax_element` it deals with several equivalent elements in a manner I'm not sure I need for this particular code. — Chiffa, Oct 14 '13 at 21:08
@Chiffa: I also think lambdas are fantastic but `std::minmax_element` performs a minimum number of comparisons, it's correct, and it's library code I don't have to reinvent. — Blastfurnace, Oct 14 '13 at 21:14
About the update -- this is really educational, and I'll be steadily improving my solution. — Chiffa, Oct 15 '13 at 01:50

score 0 · Answer 4 · answered Oct 14 '13 at 20:42

In any case the algorithm is incorrect because the vector can have the size equal to 0. In this case 1) you try to access alements that are not exist and 2) you return undefined values from the function. The more correct approach is to return indexes of the minimum and maximum elements and in the case if the vector is empty return a pair of A.size().

Simultaneous minimum and maximum

4 Answers4