10
\$\begingroup\$

Another C exercise:

Write a function that takes an array of 'ints' as its input and finds the smallest and largest elements. It should also compute the median and mean. Use a struct holding the result as the return value

I found it quite awkward that there is no function to copy an array into another array, so I wrote one intdup to use it in the median calculation.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>

struct Result {
    int smallest;
    int largest;
    double median;
    double mean;
};

int cmp(void const *lhs, void const *rhs) {
    const int *left = (const int *)lhs; 
    const int *right = (const int *)rhs;
    return *left - *right;
}

int * intdup(const int * source, const size_t len)
{
    assert(source);

    int * p = malloc(len * sizeof(int));

    if (p == NULL)
        exit(1);

    memcpy(p, source, len * sizeof(int));
    return p;
}

int find_smallest(const int* array, const size_t len)
{
    assert(array);

    size_t i = 0;
    int smallest = INT_MAX;

    for (i = 0; i < len; ++i) {
        if (array[i] < smallest)
            smallest = array[i];
    }

    return smallest;
}

int find_largest(const int* array, const size_t len)
{
    assert(array);

    size_t i = 0;
    int largest = INT_MIN;

    for (i = 0; i < len; ++i) {
        if (array[i] > largest)
            largest = array[i];
    }

    return largest;
}

double calculate_median(const int* array, const size_t len)
{
    assert(array);

    int* calc_array = intdup(array, len);   
    int tmp = 0;

    qsort(array, len, sizeof(int), cmp);

    if (len % 2 == 0) { // is even
        // return the arithmetic middle of the two middle values
        return  (array[(len - 1) / 2] + array[len / 2] ) /2.0;
    }
    else {  // is odd
        // return the middle
        return array[len / 2];              
    }
}

double calculate_mean(const int* array, const size_t len)
{
    assert(array);

    double mean = 0;
    size_t i = 0;

    for (i = 0; i < len; ++i)
        mean += array[i];

    return mean / len;
}

struct Result calculate_values(const int* array, const size_t len) 
{
    assert(array);

    struct Result result = { 0 };

    result.smallest = find_smallest(array, len);
    result.largest = find_largest(array, len);
    result.median = calculate_median(array, len);
    result.mean = calculate_mean(array, len);

    return result;
}

void print_result(const struct Result* result)
{
    assert(result);

    printf("smallest: %i\n", result->smallest);
    printf("largest: %i\n", result->largest);
    printf("median: %f\n", result->median);
    printf("mean: %f\n\n", result->mean);
}

int main()
{
    int numbers[] = { 1,7,3,4,5,6,7,8,9 };      // 9 elements  
//  int numbers[] = { 1,7,3,4,5,6,7,8 };        // 8 elements  

    int len = sizeof(numbers) / sizeof(numbers[0]);
    struct Result result = calculate_values(&numbers, len);

    print_result(&result);
    getchar();
    return 0;
}

See the the revised code her: Calculate min, max, mean and median out of array Version 2

\$\endgroup\$
  • \$\begingroup\$ Regarding efficiency, you can find the median of an array without sorting it. But doing so efficiently isn’t trivial. \$\endgroup\$ – Konrad Rudolph Jun 26 '18 at 11:41
  • \$\begingroup\$ @KonradRudolph reference for that: stackoverflow.com/questions/10662013/… \$\endgroup\$ – MD-Tech Jun 26 '18 at 12:55
13
\$\begingroup\$

I see a number of things that may help you improve your program.

Don't violate const

The calculate_median routine takes a const array, makes a duplicate and then sorts the original! I think you meant to sort the duplicated array instead.

Understand pointers

In main there's this line:

int numbers[] = { 1,7,3,4,5,6,7,8,9 }; // 9 elements  
// other stuff
struct Result result = calculate_values(&numbers, len);

The problem is that &numbers is not really what you want. With an array, the name is already effectively a pointer to the array, so you don't need & at the front in this context.

Don't leak memory

The intdup function allocates and copies the passed array, but then that memory is never freed. I'd suggest freeing the memory again as soon as the function is done with the duplicate array.

Think about naming

The variables len and mean are good because they suggest the significance of these variables in the context of the program. However, result and numbers are a little generic. I'd suggest perhaps summaryData and testArray as possible replacement names.

Eliminate unused variables

The tmp variable within calculate_median is never used. Since unused variables are a sign of poor code quality, you should seek to eliminate them. Your compiler is probably smart enough to warn you about such things if you know how to ask it to do so.

Think about efficiency

This suggestion is last for a reason. It's important to have a correct program first, and then optimize for space/time efficiency. In this case, a productive approach is suggested by the wording of the question itself:

Write a function that takes an array of 'ints' as its input and finds the smallest and largest elements. It should also compute the median and mean. Use a struct holding the result as the return value.

It says to write a function and that's a good strategy for this. Since you're sorting the array anyway to get the median, you could also use the sorted array to easily get the min and max values from that sorted array. The mean could be calculated the same way you're currently doing it, but this would reduce the number of times that the array would need to be traversed.

\$\endgroup\$
  • 2
    \$\begingroup\$ speaking about efficency, all 4 of these things maybe found in O(n). \$\endgroup\$ – RiaD Jun 25 '18 at 22:03
10
\$\begingroup\$

Avoid overflow

*left - *right can readily overflow. Use 2 compares instead. This common idiom is recognized by various compilers to emit efficient code.

int cmp(void const *lhs, void const *rhs) {
    const int *left = (const int *)lhs; 
    const int *right = (const int *)rhs;
    // return *left - *right;
    return (*left > *right) - (*left < *right);
}

Consider sizeof object

Using the correct type is error prone and harder to review and maintain. Using the size of the object is consistently correct.

// qsort(array, len, sizeof(int), cmp);
qsort(array, len, sizeof *array, cmp);

Watch out for corner cases

The below is undefined behavior when len == 0 or if the sum overflows.

if (len % 2 == 0) { // is even
    return  (array[(len - 1) / 2] + array[len / 2] ) /2.0;
}

Alternative

if (len % 2 == 0 && len > 0) { // is even
    long long mid = array[(len - 1) / 2];
    mid += array[len / 2];
    return  mid /2.0;
} else if (len == 0) {
    return NAN;
}

Does output need 6 decimal places?

Consider "%g":

// printf("median: %f\n", result->median);
///printf("mean: %f\n\n", result->mean);
printf("median: %g\n", result->median);
printf("mean: %g\n\n", result->mean);

Use static for local functions

Should this code exists in some other *.c file, no need to have the local cmp() function visible as named.

// int cmp(void const *lhs, void const *rhs) 
static int cmp(void const *lhs, void const *rhs) 
\$\endgroup\$
  • \$\begingroup\$ so by declaring the whole function static it can be only used once in the sort routine? That sounds similar to a lambda function in c++. only declared to use once in a place \$\endgroup\$ – Sandro4912 Jun 26 '18 at 16:37
  • \$\begingroup\$ @Sandro4912 Declaring the function static limits its visibility and name to the compilation of that file. The function can be used many times. \$\endgroup\$ – chux Jun 26 '18 at 16:50
  • \$\begingroup\$ so that means it can only be used by functions in the same .c file? \$\endgroup\$ – Sandro4912 Jun 26 '18 at 16:52
  • \$\begingroup\$ @Sandro4912 Usually. That's the main idea. \$\endgroup\$ – chux Jun 26 '18 at 17:10
5
\$\begingroup\$

This code looks good to me. There are a few things I would do differently.

  • If you restructure things a bit you can compute the minimum and maximum more simply from the sorted array, since you have it.
  • intdup is only called once, which in my opinion is grounds to inline it.
  • You dynamically allocate your array copy and don't free it. Of course in this program it's no big deal, but that's a bad habit to get into. If you're using C99 you could even do this without malloc by using a variable-length array.
  • My favorite technique for handling functions that populate memory (structures, arrays) is to pass the memory to be filled into the function. That way the allocation and deallocation happen in the same place, in the caller. Something to consider.
\$\endgroup\$
  • 2
    \$\begingroup\$ "I don't personally use const in C." is interesting here for const int* array, const size_t len) ... qsort(array, len, sizeof(int), cmp); well could have flagged a const error here via the compiler. Something mentioned in a later answer. \$\endgroup\$ – chux Jun 25 '18 at 22:51
  • \$\begingroup\$ Right. I didn't actually notice the const error and was just making a general remark. \$\endgroup\$ – Jakob Jun 26 '18 at 2:29
  • 1
    \$\begingroup\$ "It doesn't provide immutability" How so? Last time I checked, the compiler will scream if you try to assign to const. \$\endgroup\$ – NieDzejkob Jun 26 '18 at 15:39
  • \$\begingroup\$ @NieDzejkob Oh, you're probably right. Since I don't use it I don't actually have a very good idea of how it works! \$\endgroup\$ – Jakob Jun 26 '18 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.