Maxmin algorithm implementation

Question

I'm currently taking an algorithm course in college. To find the maximum and minimum elements in an array, I'm using a divide and conquer algorithm. Please offer suggestions for this code snippet. I get a headache reading only comments, so please give explanation with sample code.

#include<stdio.h>
#define ARRAY_SIZE(array) (sizeof(array) / sizeof(array[0]))
int tempmax, tempmin;
/*
 * return a 2 element array
 * First element is highest of list
 * Second elements is lowest of list
 *
 */
int* maxmin(const int list[], const int low, const int high, int max, int min)
{
 int mid,max1,min1;
 static int maxAndMin[2]; // to hold the max and min value of list
 // list has only one element
 // so make max and min that element
 if (low == high)
 {
 max = list[low];
 min = list[low];
 }
 // list has two elements then
 // check for which one is greater or smaller
 // and check it with temp values and update
 else if (low == high-1)
 {
 if (list[low] < list[high])
 {
 tempmax = getMax(tempmax, list[high]);
 tempmin = getMin(tempmin, list[low]);
 }
 else
 {
 tempmax = getMax(tempmax, list[low]);
 tempmin = getMin(tempmin, list[high]);
 }
 }
 else
 {
 // if list is not small, divide list into sub-problems
 // Find where to split the set
 mid = (low + high) / 2;
 // Solve the sub-problems
 max1 = list[mid+1];
 min1 = list[mid+1];
 maxmin(list, low, mid, max, min);
 maxmin(list, mid+1, high, max1, min1);
 // Combine the solutions
 tempmax = getMax(tempmax, max1);
 tempmin = getMin(tempmin, min1);
 }
 maxAndMin[0] = tempmax;
 maxAndMin[1] = tempmin;
 return maxAndMin;
}
/*
 * returns the highest element between first and second
 *
 */
int getMax(int first, int second)
{
 return first > second ? first : second;
}
/*
 * returns the lowest element between first and second
 *
 */
int getMin(int first, int second)
{
 return first < second ? first : second;
}
int main(void)
{
 int list[] = {10, 23, 24, 56, 67, 78, 90};
 int *values;
 int size = ARRAY_SIZE(list);
 tempmax = tempmin = list[0];
 values = maxmin(list, 0, size-1, list[0], list[0]);
 printf("The maximum value is = %2d \n", *values);
 printf("The minimum value is = %2d \n", *(values+1));
 return 0;
}

Answer 1

Some comments:

Firstly the interface is odd. Normally when you pass an array, you pass it's size and a pointer to the first element. In the context of your function this means:

int* maxmin(const int list[], size_t size, int max, int min);

Then you call this with:

maxmin(list, mid, max, min);
maxmin(list + mid, size - mid, max1, min1);

or from main

values = maxmin(list, size, list[0], list[0]);

This saves a call parameter (fewer is always preferable) and makes the function more 'normal'.

---

Beyond that, what stand out are the return of a static array and the use of globals. Maybe thread safety is not on your mind and this can be ignored, but bear in mind that returning a static is rarely done. And globals are often best avoided, if they can be.

---

The other thing that strikes me is the awkwardness of the code. Arguably a matter of opinion, there are many variables and their names are hard to tell apart. More importantly the need to find both max and min values complicates the function enormously.

Consider the same task but only looking for the minimum value:

int min(const int list[], const size_t size)
{
 if (size == 1) {
 return list[0];
 }
 else if (size == 2) {
 return list[0] < list[1] ? list[0] : list[1];
 }
 size_t half = size / 2;
 int n = min(list, half);
 int m = min(list + half, size - half);
 return n < m ? n : m;
}

This is so much simpler! And the max version just involves reversing the two comparisons. I would be looking for an excuse to use these rather than your combined function. Against my functions is the fact that calling max and min will be slower than just calling yours (but less than 2:1). In their favour, you might not always want both values.

As this is just an exercise, you don't have to care. But in practice I believe strongly that it is always worth simplifying the requirement/specification if it results in simpler code.

• Anirban Nag 'tintinmj': My excuse to find the max and min value simultaneously is that the algorithm states that way and it's also an important exam question.

Answer 2

• size_t is preferred over int for array indices and sizes (in general) because they cannot be negative. This also ensures you the highest possible numerical range.

• You're correct: tempmax and tempmin shouldn't be global variables. A struct, as you've mentioned, could look like this:

  struct MinMax
  {
   size_t tempmin;
   size_t tempmax;
  };
  

  Create an instance of the structure (so that a function can update it):

  MinMax mm;
  

  Then pass it to a function:

  doSomething(&mm);
  void doSomething(MinMax *mm) {}
  

• It'll be more readable to just use the array's size when checking the number of elements:

  int* maxmin(const size_t size /* other parameters */)
  {
   if (size == 1)
   {
   // do stuff
   }
   else if (size == 2)
   {
   // do other stuff
   }
   else if (size >= 3)
   {
   // do other other stuff
   }
  }
  

  You could then keep low as list[0] and high as list[size-1] within the function, thereby allowing them to be local constants rather than arguments.

• I don't like the idea of having minmax() returning something like that. It's good to cut down on pointers whenever possible, plus it doesn't seem too readable. I'd go with one of these two options:

  1. Split it into two separate functions so that each just returns one value.

  2. Stick with one function, but pass min and max as references and make the function void.

  In main(), you would then have size_t min and size_t max instead of int *values.

• As an alternative to this task, I'd simplify the entire algorithm to use a loop instead. For one thing, you're performing recursion, which is needless here (unless you're required to do so in this course). If you don't need to use recursion:

  First, set min and max as the first array element. Then, go through the loop while updating each one as you respectively encounter a smaller and larger value. It could also be done with two loops, but that would decrease efficiency as each loop is O(n).

• William Morris: Better to pass a pointer to mm
• Jamal: @WilliamMorris: Such as MinMax *mm; void doSomething(MinMax *mm) {}?
• William Morris: Yes, MinMax is a structure that you want the called function to update, so you don't want to pass it by value.
• Jamal: @WilliamMorris: Ah, right. Somehow forgot about that.
• Anirban Nag 'tintinmj': @Jamal Yes iteration is easy but using divide and conquer(recursion) significantly improves the Big O complexity.