Minimum Absolute Difference in a List of Integers

Question

Finding the minimum absolute difference in a list of integers by comparing each possible pair in the list is inefficient due to the number of comparisons required. If we sort the list first, then apparently the minimum can be found by simply comparing each integer with its neighbour.

Why is it the case that after sorting, the minimum absolute difference will be found comparing each item only with its neighbour please?

Answer 1

Let $S = \{s_1. s_2, \ldots, s_n\}$ be your set of integers ordered so that $s_1 \le s_2\le \cdots \le s_n$.

Let $k$ be arbitrary.

Then $(s_k - s_{k - 1}) + (s_{k-1} - s_{k-2}) = s_k - s_{k-2}$.

So $s_k - s_{k - 1} \le s_k - s_{k-2}$

As $k$ is arbitrary, it follows (after a few moments thought) that the difference between $s_k$ and its adjacent elements is never greater than the difference between $s_k$ and any other elements of $S$.

So the minimum distance is bound to be one of those differences between adjacent elements.