marcomg marcomg - 10 days ago 8
C Question

Get the smallest difference of all possible element combinations in an array

I have a very, very long array and I have to get the minimum difference of all possible combinations of 2 elements.

This is my code:

[...]
int diff = 1000000; // a very big difference that i'm sure is too big
int tmpDiff; // swap
//Compare
for (size_t i = 0; i < N; i++) { // I try every combination of 2 elements of array
for (size_t j = i + 1; j < N; j++) { // don't repeat same elements
tmpDiff = abs(array[i] - array[j]); // get the difference
if (diff > tmpDiff) { // if it is smaller is the difference i need
diff = tmpDiff;
}

}
}
[...]


It takes too much time. How could we optimize performances?

Answer

Sort the array first. Then you only need to compare consecutive values. And you don't even need to use abs() as you know which of the two elements it the bigger one.

If the array must not be changed, copy it first (not shown below).

#include <limits.h>
#include <stdlib.h>

// compare function for integer, compatible with qsort
int int_cmp(const void *a, const void *b) 
{ 
    const int *ia = (const int *)a; // casting pointer types 
    const int *ib = (const int *)b;
    return *ia  - *ib; 
} 

...

int diff = INT_MAX;
int d;

// sort
qsort(array, N, sizeof(array[0]), int_cmp);

// compare consecutive elements
for (size_t i = 1; i < N; i++) {
    d = array[i] - array[i - 1];
    if (d < diff)
        diff = d;
}