Consider the following algorithm for finding the distance be

Consider the following algorithm for finding the distance between the two closest elements in an array of numbers. ALGORITHM MinDistance(A[0..n - 1])//Input: Array A[0..n - 1] of numbers//Output: Minimum distance between two of its elements dmin leftarrow infinity for i leftarrow 0 to n - 1 do for j leftarrow 0 to n - 1 do if i notequalto j and |A[i] - A[y]|

Solution

current algorithm is O(n^2)

There\'s better algorithm possible by sorting elements using quicksort then comparing adjacent elements only to find min distance. That will work in O(nlogn) time for quicksort.

sort(arr, arr+n);

int diff = INT_MAX;

for (int i=0; i<n-1; i++)

   if (arr[i+1] - arr[i] < diff)

      diff = arr[i+1] - arr[i];