PDA

View Full Version : Min and Max value in array



Benjamin
27th February 2009, 11:07
Hi all,

I have an array of 200 int elements which can have positive and negative values. What would be the best way to determine min and max value?

Regards,
Benjamin

Lykurg
27th February 2009, 11:24
array? pure c++ or an qt container?

have a look at qMin, qMax (with a loop) or qSort:

void qSort ( RandomAccessIterator begin, RandomAccessIterator end )
Sorts the items in range [begin, end) in ascending order using the quicksort algorithm.
Example:

QList<int> list;
list << 33 << 12 << 68 << 6 << 12;
qSort(list.begin(), list.end());
// list: [ 6, 12, 12, 33, 68 ]
...

^NyAw^
27th February 2009, 11:38
Hi,

Not difficult to implement


int iMax = array[0]; //set min and max as the first element
int iMin = array[0];
for (int i=1; i<arraySize; i++)
{
if (array[i] < iMin)
iMin = array[i];
if (array[i] > iMax)
iMax = array[i];
}


About using qSort and then getting the first and the last values is a good solution if speed is not an issue. Sort algorithms take its time

Lykurg
27th February 2009, 12:02
Sort algorithms take its time

Yepp, that's right. And if time really matters is that quicker?


int iMax = array[0]; //set min and max as the first element
int iMin = array[0];
for (int i=1; i<arraySize; i++)
{
if (array[i] < iMin)
iMin = array[i];
else
{
if (array[i] > iMax)
iMax = array[i];
}
}

Because under circumstances (if array[i] < iMin) the second test isn't performed. If so the question of the day remains: Which is quicker?



int iMax = array[0]; //set min and max as the first element
int iMin = array[0];
for (int i=1; i<arraySize; i++)
{
if (array[i] < iMin)
iMin = array[i];
else
if (array[i] > iMax)
iMax = array[i];
}


or



int iMax = array[0]; //set min and max as the first element
int iMin = array[0];
for (int i=1; i<arraySize; i++)
{
if (array[i] > iMax)
iMax = array[i];
else
if (array[i] < iMin)
iMin = array[i];
}


:rolleyes:

^NyAw^
27th February 2009, 12:47
Hi,

Seems that you are angry because I just pointed that the sort algorithm is slow to just take the min and max values.

In my code the 2 "if" statments are converted to 2 assembler instructions. So every iteration it gets 2 instructions to determine if have to assign the value.

In your code, "if" and "else" are converted to 2 assembler instructions, and then, if the "else" is executed, you have another "if" that is another asm instruction.

So i really depens on the array values because depending on them my code will execute more instructions than your code and maybe your code will be faster. It only depends on array values. Think on the worst case that every next array value is grater that iMax, then your code performs more instructions.

:eek:

Lykurg
27th February 2009, 13:25
Seems that you are angry...
No, sorry, don't get me wrong: I'm not so personally engaged in these things that I can get angry about it.



In my code the 2 "if" statments are converted to 2 assembler instructions. So every iteration it gets 2 instructions to determine if have to assign the value.

In your code, "if" and "else" are converted to 2 assembler instructions, and then, if the "else" is executed, you have another "if" that is another asm instruction.


And this was a real question of me if the code would be faster, which I now know it isn't. (in neither way.)

Thanks

Benjamin
27th February 2009, 13:33
Thank you all for your answers.

^NyAw^
27th February 2009, 13:40
Hi,



And this was a real question of me if the code would be faster, which I now know it isn't. (in neither way.)




Think on the worst case that every next array value is grater than iMax, then your code performs more instructions.


And think on the other case that every next array value is minor than iMin, then my code perform more instructions.

Speaking on order complexity, the two algorithms are O(n), and this is the way that an algorithm speed is calculated because you don't know the values before the code is executed.

The Quicksort algorithm is O(n logn) as mean, but O(n2) on worst and O(n logn) on best that is greatter than O(n).

Benjamin
27th February 2009, 14:43
I have used qMin and qMax functions.

Is there a way to determine at which position is the max or min value?

Lykurg
27th February 2009, 14:50
For finding the max and min the loop from ^NyAw^ should in your case be the best choice. (Then you have also the index, but be aware if there are two or more min/max values...)

Benjamin
27th February 2009, 14:56
This is how I did it:

_maxValue = _dataValues[0];
_minValue = _dataValues[0];


for(int i = 0; i<200; i++){
_maxValue = qMax(_maxValue, _dataValues[i]);
_minValue = qMin(_minValue, _dataValues[i]);
}

How can I know when max or min value is found, so that I can use index.

Lykurg
27th February 2009, 15:01
for(int i = 0; i<200; i++)
Hard coded size is dangerous!


_maxValue = _dataValues[0];
_minValue = _dataValues[0];
int _minValueIndex = 0;
int _maxValueIndex = 0;
for (int i=1; i<_dataValues.size(); i++)
{
if (_dataValues[i] < _minValue)
{
_minValue = _dataValues[i];
_minValueIndex = i;
}
if (_dataValues[i] > _maxValue)
{
_maxValue = _dataValues[i];
_maxValueIndex = i;
}
}

(WITHOUT catching the case if there are two/more min/max values!)

Benjamin
27th February 2009, 15:11
Thank you for your replay.

I am wondering one thing, can this way of finding min and max values work with mixed positive and negative numbers?

Lykurg
27th February 2009, 15:19
I am wondering one thing, can this way of finding min and max values work with mixed positive and negative numbers?

Why not? (-1 > 2) or (2 > -1) are fine...