marcomg - 1 year ago 83
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?

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;
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download