Find some better algorithm for finding the smallest difference between the elements of an array

Question

Input: Array of integers A[0..n – 1]

Output: Smallest difference between two elements of a dmin array

dmin = ∞
for i = 0 to n − 1 do
   for j = 0 to n − 1 do
      if i != j &&|A[i] − A[j]| < dmin
        dmin ← |A[i] − A[j]|
return dmin
  

I know the complexity of the above code is O(n^2). I want to find a better algorithm for finding the smallest difference between the elements of an array and find the complexity of it. Then, implement the above code as a single function and your improved algorithm as another function in c. Call the two functions for random arrays of size 60000, 70000, 80000, 90000 and 100000 (for each dimension create ten different random matrices and find the mean).

So, i have done:

int pair1(int A[],int n)
{
    int dmin=INT_MAX,i,j;
   
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if (i != j && abs(A[i] - A[j]) < dmin) 
            {
                dmin = abs(A[i] - A[j]);
            }
        }
    }
    
    return dmin;
}

I thought a better algorithm might be if we sorted the array. Any ideas how to do this in c and how to write it as a pseydocode? I think that the complexity of it would be O(nlogn).

I have tried this code:

int pair2(int A[],int n)
{
    int dmin=INT_MAX,i,j;
    sort(A,A+n);

    for(i=0;i<n-1;i++)
    {
        for(j=0;j<n-1;j++)
        {
            if (i != j && abs(A[i] - A[j]) < dmin) 
            {
                dmin = abs(A[i] - A[j]);
            }
        }
    }
        
    return dmin;
}

Answer 1

The absolute value of the difference between 2 int values may exceed the range of int, one must use unsigned for this and so should the return type be.

Sorting the array is indeed a good way to reduce the time complexity from quadratic to N.log(N).

Here is a solution:

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

int compare_ints(const void *aa, const void *bb)
{
    const int *a = aa;
    const int *b = bb;
    return (*a > *b) - (*a < *b);
}

unsigned pair2(const int A[], size_t n)
{
    // special case the empty set and singletons
    if (n <= 1)
        return 0;

    // sort the array
    qsort(A, n, sizeof(*A), compare_ints);

    unsigned dmin = UINT_MAX;

    // find the smallest difference between successive entries
    for (size_t i = 1; i < n; i++) {
        unsigned diff = (unsigned)A[i] - (unsigned)A[i - 1];
        if (dmin > diff)
            dmin = diff;
    }
    return dmin;
}

Answer 2

Yes, you are correct that the minimum difference can found in O(n*log2(n)) if you sort the array with an O(n*log2(n)) sorting algorithm such as quicksort or mergesort.

Then, finding the minimum difference is a single loop of O(n).

Together the complexity is the greater of the two: O(n*log2(n))

Here is some sample code. It is heavily annotated:

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

int
cmp(const void *vlhs,const void *vrhs)
{
    const int *lhs = vlhs;
    const int *rhs = vrhs;
    return (*lhs > *rhs) - (*lhs < *rhs);
}

int
pair2(int A[],int n)
{

    // sort the array by any O(n*log2(n)) [or better] sort (e.g. quicksort,
    // mergesort)
    qsort(A,n,sizeof(int),cmp);

    int dmin = INT_MAX;

    // get A[i - 1] for first loop iteration
    int old = A[0];

    // loop through all remaining elements (this is O(n))
    for (int i = 1;  i < n;  ++i) {
        // get the current array value
        int cur = A[i];

        // difference between the current and previous values:
        // dif = A[i] - A[i - 1]
        int dif = cur - old;

        // get absolute value
        if (dif < 0)
            dif = -dif;

        // save new/better minimum
        if (dif < dmin) {
            dmin = dif;

            // because we took the absolute value, we can't get any better than
            // this
            if (dif == 0)
                break;
        }

        // remember A[i - 1] for next iteration
        old = cur;
    }

    return dmin;
}