Finding the distance between two nearest elements in an array of numbers

Question

So, I study the algorithms from this book that I acquired, and I have pseudo code to determine the distance between two closetst elements in an array of numbers

MinDistance(a[0...n-1]) Input: Array A of numbers Output: Minimum Distance between two of its elements dMin <- maximum integer for i=0 to n-1 do for j=0 to n-1 do if i!=j and | A[i] - A[j] | < dMin dMin = | A[i]-A[j] | return dMin 

However, I would like to improve this algorithmic solution. Change what you already have, or rewrite everything together. Can anyone help? I wrote a function and class in Java to check pseudocode? It's right? And once again, how can I do it better in terms of efficiency.

 //Scanner library allowing the user to input data import java.lang.Math.*; public class ArrayTester{ //algorithm for finding the distance between the two closest elements in an array of numbers public int MinDistance(int [] ar){ int [] a = ar; int aSize = a.length; int dMin = 0;//MaxInt for(int i=0; i< aSize; i++) { for(int j=i+1; j< aSize;j++) { dMin = Math.min(dMin, Math.abs( a[i]-a[j] ); } } return dMin; } //MAIN public static void main(String[] args){ ArrayTester at = new ArrayTester(); int [] someArray = {9,1,2,3,16}; System.out.println("NOT-OPTIMIZED METHOD"); System.out.println("Array length = "+ someArray.length); System.out.println("The distance between the two closest elements: " + at.MinDistance(someArray)); } //end MAIN } //END CLASS 

SO I updated the function to minimize the call to Math.abs twice. What else can I improve? If I were to rewrite its varieties, change it for cycles in general or it would be just as theoretically faster.

 public int MinDistance(int [] ar){ int [] a = ar; int aSize = a.length; int dMin = 0;//MaxInt for(int i=0; i< aSize; i++) { for(int j=i+1; j< aSize;j++) { dMin = Math.min(dMin, Math.abs( a[i]-a[j] ); } } return dMin; } 

Answer 1

One obvious increase in efficiency: first collect integers, then you can look at the neighboring ones. Any number will be closest to its neighbor up or down.

This changes complexity from O (n ² ) to O (n log n). It is clear that for a small value of n it is shown that this will not have a significant difference, but from the point of view of theoretical complexity this is important.

One micro optimization you might want to do: use a local variable to store the result of Math.abs , then you won’t need to compromise it if it turns out to be less than the minimum. Alternatively, you can use dMin = Math.min(dMin, Math.abs(a[i] - a[j])) .

Note that you need to be careful with the boundary conditions - if you allow negative numbers, your subtraction may overflow.

Answer 2

This is a naive solution O (n ^ 2).

The best way:

Sort the array, then go through it again and check the distance between the sorted elements.
This will work because they are in ascending order, so the number with the closest value is adjacent.

This solution will be O (nlogn)

Answer 3

First of all, before you do it quickly, do it right. Why is dmin initialized by array length? If the array is [1, 1000] , the result of your algorithm will be 2 instead of 999.

Then, why are you doing j from 0 to the length of the array? You compare each pair of elements twice. You must make j go from i + 1 to the length of the array (which will also avoid the comparison i! = J).

Finally, you can get a few nanoseconds by avoiding double calling Math.abs ().

And then you can completely change your algorithm by first sorting the array, as indicated in other answers.

Answer 4

Here is the question:

How long will it take to find the minimum distance if the array has been sorted?

You should be able to complete the rest from here.

Answer 5

Theoretically, you can get O (n) solution on

• sorting with shell radix sorting (edited, thanks to j_random_hacker for specifying it)
• one pass to find the difference between the numbers

Answer 6

At first, sorting the array would free us from using another FOR loop.

  public static int distclosest(int numbers[]) { Arrays.sort(numbers); int aSize = numbers.length; int dMin = numbers[aSize-1]; for(int i=0; i<aSize-1; i++) { dMin = Math.min(dMin, numbers[i+1]-numbers[i]); } return dMin; }