Consider the problem of finding the distance between the two closest numbers in an array of n numbers. (The distance between two numbers 'x 'and 'y' is computed as $|x - y|$.) Design a presorting-based algorithm in * *pseudo code* * for solving this problem and determine its efficiency class.

The minimum distance between two closest number in an array is |$x-$y|

Algorithm: Pseudo code

minimum_distance (arr[0 ... n-1])

merge_sort (arr[0 ... n-1])

min_dist←∞

for i=0 to i=n-2 do

if (|arr[i+1]-arr[i]) | < min_dist do

min_dist = |arr[i+1]-arr[i]) |

return min_dist

Efficiency class:

The running time for worst case of merge sort is O (n logn) and for traversing the array is O (n) so total time will be:

T (n) = O (n logn) + O (n)

the term O (n logn) is dominating in above equation so the total running time will be T (n) = O (n logn)

Explanation:

minimum_distance (arr[0 ... n-1])

merge_sort (arr[0 ... n-1]) / /merge sort is used to sort the array

min_dist←∞

for i=0 to i=n-2 do

if (|arr[i+1]-arr[i]) | < min_dist do

min_dist = |arr[i+1]-arr[i]) |

return min_dist

/ / above loop calculates the least distance between the two elements of pre-sorted array then keeps the track of the all possible least distances at different position where the elements available and then return the least distance