Min and Max value in array

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

array? pure c++ or an qt container?

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

Quote:

---

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

Code:

---

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

---

...

---

Hi,

Not difficult to implement

Code:

---

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

Quote:

---

Sort algorithms take its time

---

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

Code:

---

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?

Code:

---

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

Code:

---

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:

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:

Quote:

---

Originally Posted by ^NyAw^

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.

Quote:

---

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

Thank you all for your answers.

Hi,

Quote:

---

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

---

Quote:

---

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

I have used qMin and qMax functions.

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

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

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.

Quote:

---

Originally Posted by Benjamin

for(int i = 0; i<200; i++)

---

Hard coded size is dangerous!

Code:

---

_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!)

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?

Quote:

---

Originally Posted by Benjamin

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