Finding The Two Closest Numbers In A List Using Sorting

If I am given a list of integers/floats, how would I find the two closest numbers using sorting?

Solution 1:

Such a method will do what you want:

>>> defminDistance(lst):
    lst = sorted(lst)
    index = -1
    distance = max(lst) - min(lst)
    for i inrange(len(lst)-1):
        if lst[i+1] - lst[i] < distance:
            distance = lst[i+1] - lst[i] 
            index = i
    for i inrange(len(lst)-1):
        if lst[i+1] - lst[i] == distance:
            print lst[i],lst[i+1]

In the first for loop we find out the minimum distance, and in the second loop, we print all the pairs with this distance. Works as below:

>>>lst = (1,2,3,6,12,9,1.4,145,12,83,53,12,3.4,2,7.5)>>>minDistance(lst)
2 2
12 12
12 12
>>>

Solution 2:

It could be more than one possibilities. Consider this list

[0,1, 20, 25, 30, 200, 201]

[0,1] and [200, 201] are equal closest.

Solution 3:

Jose has a valid point. However, you could just consider these cases equal and not care about returning one or the other.

I don't think you need a sorting algorithm, per say, but maybe just a sort of 'champion' algorithm like this one:

def smallestDistance(self, arr):
    championI =-1
    championJ = -1
    champDistance = sys.maxint
    i = 0while i < arr.length:
        j = i + 1while j < arr.length:
            if math.fabs(arr[i] - arr[j]) < champDistance:
                championI = i
                championJ = j
                champDistance = math.fabs(arr[i] - arr[j])
            j += 1
        i += 1
    r = [arr[championI], arr[championJ]]
    return r

This function will return a sub array with the two values that are closest together. Note that this will only work given an array of at least two long. Otherwise, you will throw some error.

I think the popular sorting algorithm known as bubble sort would do this quite well. Though running at possible O(n^2) time if that kind of thing matters to you...

Here is standard bubble sort based on the sorting of arrays by integer size.

defbubblesort( A ):
  for i inrange( len( A ) ):
    for k inrange( len( A ) - 1, i, -1 ):
      if ( A[k] < A[k - 1] ):
        swap( A, k, k - 1 )

defswap( A, x, y ):
  tmp = A[x]
  A[x] = A[y]
  A[y] = tmp

You can just modify the algorithm slightly to fit your purposes if you insist on doing this using a sorting algorithm. However, I think the initial function works as well...

hope that helps.