Ask 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.

+3
Answers (1)
  1. 18 April, 11:41
    0
    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
Know the Answer?
Not Sure About the Answer?
Find an answer to your 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 ...” in 📗 Computers & Technology if the answers seem to be not correct or there’s no answer. Try a smart search to find answers to similar questions.
Search for Other Answers