marcomg - 6 months ago 45

C Question

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;
}
```

Source (Stackoverflow)