patterncMinor
Maxmin algorithm implementation
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:
Then you call this with:
or from
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:
This is so much simpler! And 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
and
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.
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
mainvalues = 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 thetwo comparisons. I would be looking for an excuse to use these rather than
your combined function. Against my functions is the fact that calling
maxand
min will be slower than just calling yours (but less than 2:1). Intheir 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.