Find the minimum difference between numbers in a sorted array in bash

Question

I am doing a code challenge, with given numbers, I have to find the minimum difference. For exemple :

[3,5,8,9]

Result : 1 (9-8)

The problem is that the final test to achieve the puzzle use a very large amount of numbers and my code is not optimised enough.

Before finding the minimu difference, I sort the array like that :

IFS=$'\n' sorted=($(sort -n <<<"${array[*]}"))

Then, I do a for loop over the array to find the smallest but it takes too much time so I tried to do i+4 instead of i++ but I don't think that this is the real problem.

Here is my code to find the smallest :

smallest=5000
for (( i=2; i<N; i=$((i+1)) ));do
    diff=$((${sorted[i]}-${sorted[i-1]}))
    if [ $diff -lt $smallest ]; then
        smallest=$diff
    fi
done

Do you have any idea of what I can do to have something optimzed enough to go through the test ? By the way, I know almost nothing about Bash, I usaly code in python.

Answer 1

I doubt this will help; shell simply isn't intended for fast numerical computations. The only difference is that I've cut the number of array indexing operations in half.

# No need to guess at an upper bound
N=${#sorted[@]}
smallest=$((${sorted[N-1]} - ${sorted[0]}))

current=${sorted[0]}
for next in "${sorted[@]:1}"; do
    diff=$(($next - $current))
    if [ $diff -lt $smallest ]; then
        smallest=$diff
    fi
    current=$next
done

I don't think that using a C-style loop will be faster than iterating over the elements of the array, but if it is, here's how to do with:

# Indices run from 0 to N-1
# No need for $((...)); ((...)) is already an arithmetic context
current=${sorted[0]}
for ((i=1; i<N; i++)); do
    next=${sorted[i]}
    diff=$(($next - $current))
    if [ $diff -lt $smallest ]; then
        smallest=$diff
    fi
    current=$next
done

Finally, you might try not using an array at all, instead simply reading the data from standard input.

sort -n <<EOF |
5
3
9
8
EOF
| {
    smallest=5000   # Now you do have to guess again
    read current
    while read next; do
        diff=$((next - current))
        if [ $diff -lt $smallest ]; then
            smallest=$diff
        fi
        current=$next
    done
}