Question

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.

Answer 1

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)

Step-by-step 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