配列内のすべての可能な要素の組み合わせの最小の差を得る

Question

非常に長い配列を持ち、2つの要素のすべての可能な組み合わせの最小の違いを得なければなりません。

これは私のコードです：

[...] 
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; 
     } 

    } 
} 
[...] 

それは時間がかかりすぎます。どのようにパフォーマンスを最適化できますか？

Answer 1

最初に配列を並べ替えます。次に、連続した値を比較するだけです。また、2つの要素のどちらが大きいかを知っているので、abs()を使用する必要はありません。

アレイを変更してはならない場合は、最初にコピーします（下に表示されていません）。

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

更新

qsortクイックソートアルゴリズムを用いて配列をソート。ループに対して2つのネストされたがある場合、ソートのコストはO（n^2）とは対照的にO（n ln n）のオーダになります。より大きい配列（n> 100）の場合、これは大きな違いをもたらす可能性があります。ちょうど数学をしてください：約。 500対10,000。

qsortに渡される比較関数は、どんなタイプの配列でも機能するように書かれているので、常に厄介です。qsort関数は、配列内の2つの要素のアドレス（ポインタ）に渡されます。整数のような小さな型に対しては、整数を直接渡すと便利です。しかし代わりに、あなたはその住所を扱わなければなりません。それでは、あなたがやっていることは二つある：

1. は、すなわち、任意の型（void*）のポインタから整数（int*）へのポインタを、より具体的な型へのポインタに変換します。ポインタ逆参照

2. 、すなわち、この場合*iaと*ibに、*オペレータを使用して実効値を取得します。

機能は、第二の数が大きい場合、彼らは同じであり、数が0より大きい場合は、最初の整数は、第1、0より小さければ0未満の数で返す必要があります。だから古いトリックが便利です：ちょうど最初と2番目の数字の違いを返します。