Obtenir la plus petite différence de toutes les combinaisons d'éléments possibles dans un tableau

Question

J'ai un tableau très, très long et je dois obtenir la différence minimale de toutes les combinaisons possibles de 2 éléments.

Ceci est mon 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; 
     } 

    } 
} 
[...] 

Il prend trop de temps. Comment pourrions-nous optimiser les performances?

Answer 1

Triez d'abord le tableau. Ensuite, vous avez seulement besoin de comparer des valeurs consécutives. Et vous n'avez même pas besoin d'utiliser abs() car vous savez lequel des deux éléments le plus grand.

Si le tableau ne doit pas être modifié, copiez-le en premier (non illustré ci-dessous).

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

Mise à jour

qsort trie un tableau en utilisant l'algorithme Quicksort. Le coût du tri est de l'ordre O (n ln n) par opposition à O (n^2) si vous avez deux imbriquées pour les boucles. Pour les tableaux plus grands (n> 100), cela peut faire une énorme différence. Faites juste les calculs: approx. 500 contre 10 000.

La fonction de comparaison transmise à qsort est toujours délicate car qsort est écrite de manière à fonctionner avec des tableaux de tout type. La fonction passe l'adresse de (pointeur vers) deux éléments dans le tableau. Pour les petits types tels que nombre entier, il serait utile s'il passait les entiers directement. Mais à la place, vous devez faire face à l'adresse. Alors ce que vous faites est deux choses:

1. Convertir le pointeur vers un type plus spécifique, à savoir d'un pointeur de tout type (void*) à un pointeur vers un entier (int*).

2. déréférencement le pointeur, à savoir obtenir la valeur efficace en utilisant l'opérateur *, dans ce cas *ia et *ib.

Les fonctions doit retourner un nombre inférieur à 0 si le premier nombre entier est inférieur à la seconde, 0 si elles sont égales et un nombre supérieur à 0 si le second nombre est plus grand. Donc, un vieux truc est pratique: il suffit de retourner la différence entre le premier et le deuxième nombre.