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

So I'm teaching myself algorithms from this book I purchased, and I have a pseudo-code for Finding the distance between the 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 wanted to make improvements to this algorithmic solution. Change what's already there, or rewrite all together. Can someone help? I wrote the function and class in Java to test the pseudo-code? Is that correct? And once again, how can I make it better from efficiency standpoint.

//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 开发者_开发技巧calling the Math.abs twice. What else can I do improve it. If I was to rewrite it with sort, would it change my for loops at all, or would it be the same just theoretically run 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;
    }

One obvious efficiency improvement: sort the integers first, then you can look at adjacent ones. Any number is going to be closest to its neighbour either up or down.

That changes the complexity from O(n²) to O(n log n). Admittedly for the small value of n shown it's not going to make a significant difference, but in terms of theoretical complexity it's important.

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

Note that you need to be careful of border conditions - if you're permitting negative numbers, your subtraction might overflow.

That's a naive solution of O(n^2).

Better way:

Sort the array, then go over it once more and check the distance between the sorted items.
This will work because they are in ascending order, so the number with the nearest value is adjacent.

That solution will be O(nlogn)

First of all, before making it fast, make it correct. Why is dmin initialized with the length of the array? If the array is [1, 1000], the result of your algorithm will be 2 instead of 999.

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

Finally, you could gain a few nanoseconds by avoiding calling Math.abs() twice.

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

You can theoretically get an O(n) solution by

1. sorting with shell radix sort (edited, thanks to j_random_hacker for pointing it out)
2. one pass to find difference between numbers

Here's a question:

How long would it take to find the min distance if the array was sorted?

You should be able to finish the rest out from here.

Sorting the array first would exempt 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;
    }

  static void MinNumber(int [] nums){

    Arrays.sort(nums);
    int min = nums[1] - nums[0]; 
    int indexOne = 0 , indexTwo = 1;

    for (int i = 1; i < nums.length -1; i++) {
        if (min > (nums[i+1] - nums[i])) {
            min = nums[i+1] - nums[i] ; 
            indexOne = i ; 
            indexTwo = i+1 ; 
        }
    }

    System.out.println("Minimum number between two values is: "+ min + " and the values is "+nums[indexOne]+" , "+nums[indexTwo] );

}

np: sorting the array is a must before executing the algorithm.

static int minDist(int arr[]) {
    int firstPointer, nextPointer;
    int minDistance = arr[1] - arr[0];
    int tempDistance;

    for (firstPointer = 0; firstPointer < arr.length; firstPointer++) {
        for (nextPointer = firstPointer + 1; nextPointer < arr.length; nextPointer++) {
            if (arr[nextPointer] == arr[firstPointer]) {
                return 0;
            } else {
                tempDistance = (arr[nextPointer] - arr[firstPointer]);
                if (minDistance > tempDistance) {
                    minDistance = tempDistance;
                }
            }

        }
    }
    return minDistance;
}

public static void main(String[] args) {
    int[] testArray = {1000, 1007, 3, 9, 21};
    Arrays.sort(testArray);
    int result = minDist(testArray);
    System.out.println(result); 
}