minmax3.cpp

data structures, algorithms and Application书的源代码

// find min and max of n elements
// non-recursive divide-and-conquer version

#include <iostream.h>

template<class T>
bool MinMax(T w[], int n, T& Min, T& Max)
{// Locate min and max of w[0:n-1].
 // Return false if fewer than one element.
   // special cases, n <= 1
   if (n < 1) return false;
   if (n == 1) {Min = Max = 0; 
                return true;}

   // initialize Min and Max
   int s;  // start point for loop
   if (n % 2) {// n is odd
      Min = Max = 0;
      s = 1;}
   else {// n is even, compare first pair
         if (w[0] > w[1]) {
            Min = 1;
            Max = 0;}
         else {Min = 0;
               Max = 1;}
         s = 2;}

   // compare remaining pairs
   for (int i = s; i < n; i += 2) {
      // find larger of w[i] and w[i+1]
      // then compare larger with w[Max]
      // and smaller with w[Min]
      if (w[i] > w[i+1]) {
         if (w[i] > w[Max]) Max = i;
         if (w[i+1] < w[Min]) Min = i + 1;}
      else {
         if (w[i+1] > w[Max]) Max = i + 1;
         if (w[i] < w[Min]) Min = i;}
      }

   return true;
}

void main(void)
{
   int w[12] = {10, 25, 8, 2, 8, 10, 6, 3, 1, 20, 4, 35};
   int n = 12;
   int Min, Max;
   MinMax(w,n,Min,Max);
   cout << w[Min] << ' ' << w[Max] << endl;
}