Question

C++

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←∞ 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 Make as many improvements as you can in this algorithmic solution to the problem. If you need to, you may change the algorithm altogether; if not, improve the implementation given. List and explain the improvements you made and then present the improved algorithm.

Answer 1

The algorithm given in the problem takes O(n²) time because two for loops are present (nested).

We can improve the algorithm by reducing its time complexity to O(nlogn).

So we can improve the algorithm by using the idea of sorting.

We are given an array of integers and we have to return the minimum distance between closest elements.

Example-

Input- { 1, 3, 20, 19 , 5, 24}

Output- 1

Minimum difference is between 19 and 20.

Explanation-

we will sort the array int ascending order , it becomes {1, 3, 5, 19, 20, 24}.

set min difference = infinite

now traverse through the array and find difference between adjacent pairs and update min difference.

d=3-1=2 d<min difference , update min difference = 2

d=5-3= 2 d=min difference , no need to update min difference

d=19-5= 14 d>min difference , no need to update min difference

d=20-19=1 d<min difference, update min difference = 1

d=24-20 =4 d> min difference , no need to update min difference

So after traversing the whole array we get min difference = 1.

Steps-

1)Sort the given array by using sort function which takes O(nlogn ) time.

2) Initialize the minimum distance dmin as infinite.

3) Now after sorting compare the adjacent pairs in the sorted array and keep updating minimum difference -

a) if a[i+1] -a[i] < minimum difference then minimum difference = a[i+1] - a[i]

b) else do nothing and continue

this takes O(n) time.

So the overall time taken by the algorithm becomes is O(nlogn) + O(n) whick is equal to O(nlogn).

Algorithm for above steps-

Algorithm MinDistance( A[0........n-1]){

//Input- Array of size n

//Output- Minimum distance between two elements of array

//sort the array using sort function from algorithm library

sort(A, A+n);

dmin <- INT_MAX

for i<-0 to n do

        if A[i+1] - A[i]  <  dmin 

                     dmin = A[i+1] - A[i] ;

return dmin

This above algorithm takes O(nlogn) time.