Min and Max value in array

[Benjamin]

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]

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 ]

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

To copy to clipboard, switch view to plain text mode 

...

[^NyAw^]

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];
}

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];
}

To copy to clipboard, switch view to plain text mode 

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]

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];
  }
}

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];
  }
}

To copy to clipboard, switch view to plain text mode 

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];
}

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];
}

To copy to clipboard, switch view to plain text mode 

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];
}

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];
}

To copy to clipboard, switch view to plain text mode 

[^NyAw^]

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.

[Lykurg]

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]

Thank you all for your answers.

[^NyAw^]

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]

I have used qMin and qMax functions.

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

[Lykurg]

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]

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]

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;
  }
}

_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;
  }
}

To copy to clipboard, switch view to plain text mode 

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

[Benjamin]

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]

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...