HiveBrain v1.2.0
Get Started
← Back to all entries
patterncMinor

Maxmin algorithm implementation

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
algorithmimplementationmaxmin

Problem

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

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

Solution

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.

Code Snippets

int* maxmin(const int list[], size_t size, int max, int min);
maxmin(list, mid, max, min);
maxmin(list + mid, size - mid, max1, min1);
values = maxmin(list, size, list[0], list[0]);
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;
}

Context

StackExchange Code Review Q#29821, answer score: 5

Revisions (0)

No revisions yet.