Algorithm

Here is the algorithm (assumes n even):

void minMax( vector<int> & data, pair<int, int> & result )
{
  int i = 0;
  int curmax = data[i];
  int curmin = data[i+1];

  if( curmax < curmin )
  {
    curmax = data[i+1];
    curmin = data[i];
  }

  int max = curmax;
  int min = curmin;
  
  for( i = 2; i < data.size(); i += 2 )
  {
    curmax = data[i];
    curmin = data[i+1];

    if( curmax < curmin )
    {
      curmax = data[i+1];
      curmin = data[i];
    }

    if( curmax > max )
      max = curmax;

    if( curmin < min )
      min = curmin;
  }
  
  result.first = min;
  result.second = max;
}

Computes min-max in pairs. Only need to compare current min to min and current max to max. How many comparisons all together?


next up previous
Next: Finding the Salutatorian Up: EXTREMALS Previous: Computing Max and Min