Very fast way to sort array of integers?

Question

I come here with a solution I just wrote but I definitely can't find a better way to sort my array as fast as possible.

I actually need the algorithm to give me the answer in less than 1 sec, on an array containing 100'000 integers.

Here's the code :

read N
for (( i=0; i<N; i++ )); do
    read arr[i]
done

sorted=($(printf '%s\n' "${arr[@]}"|sort -n))

min=$(( sorted[1]-sorted[0] ))

for (( i=1; i<N-1; i++ )); do
    diff=$(( sorted[i+1] - sorted[i] ))
    if [ "$diff" -lt "$min" ]; then
        min=$diff
    fi
done

echo $min

N is the number of elements, in our case 100'000 as I said.

The thing is, after my array is sorted, I need to loop through it and calculate the minimum distance between two integers :

For example, with (3, 5, 8, 9), the minimum distance is 1 (between 8 and 9).

I'm such a newbie in Bash, so I don't even know if this is an efficient way;

In fact, the gain of speed could come from the second part of the code, and not from the sorting part...

Any ideas ?

Thanks in advance,

Answer 1

numbers range <0,1000000) is small enough

• as your numbers are not repetitive (smalest distance is>=40)
• then you just need a bit per value (if it is present or not)
• so you need up to 1MB for Byte/value or up to 128KB for bit/value
• (as the K,M are based on 1024 so you have large enough reserve)

so Bucket sort is a possibility:

1. create array of flags for each possible value

   • bool flag[1000000];

2. clear the flags O(M)

   • for (int i=0;i<1000000;i++) flag[i]=0;

3. compute flags by processing your array arr[N] ... O(N)

   • for (int i=0;i<N;i++) flag[arr[i]]=1;
   • for repetition just increment flag[] unless it is too big to avoid overflow
   • in case the flag[arr[i]] is already 1 then return distance = 0

4. reconstruct the array O(M)

   • for (int i=0,j=0;i<1000000;i++) if (flag[i]) { arr[j]=i; j++; } N=j;

5. now compute the distance O(N)

   • you can mix these steps together so you do not need the arr[N] in memory
   • instead just count the consequent zeroes in flag[] ...

[Notes]

• M=1000000
• N<=M
• if N is much much smaller then M then this may not be the fastest way ...

Answer 2

I finally came with a simple and pretty elegant solution :

read N

for (( i=0; i<N; i++ )); do
    read tab[i]
done

printf "%i\n" ${tab[@]} | sort -n | awk 'BEGIN{dmin=1000000;} (NR>1){d=$1-prec; if (d<dmin) dmin=d;} {prec=$1;} END{print dmin;}'

And that's it. :) Thanks to all of you for taking the time to help me ! ;)

Answer 3

Given this awesome page on sorting algorithm complexity I would use the Radix Sort (here in Python, I didn't find a Bash implementation but I'm still looking):

#python2.6 <
from math import log

def getDigit(num, base, digit_num):
    # pulls the selected digit
    return (num // base ** digit_num) % base  

def makeBlanks(size):
    # create a list of empty lists to hold the split by digit
    return [ [] for i in range(size) ]  

def split(a_list, base, digit_num):
    buckets = makeBlanks(base)
    for num in a_list:
        # append the number to the list selected by the digit
        buckets[getDigit(num, base, digit_num)].append(num)  
    return buckets

# concatenate the lists back in order for the next step
def merge(a_list):
    new_list = []
    for sublist in a_list:
       new_list.extend(sublist)
    return new_list

def maxAbs(a_list):
    # largest abs value element of a list
    return max(abs(num) for num in a_list)

def split_by_sign(a_list):
    # splits values by sign - negative values go to the first bucket,
    # non-negative ones into the second
    buckets = [[], []]
    for num in a_list:
        if num < 0:
            buckets[0].append(num)
        else:
            buckets[1].append(num)
    return buckets

def radixSort(a_list, base):
    # there are as many passes as there are digits in the longest number
    passes = int(round(log(maxAbs(a_list), base)) + 1) 
    new_list = list(a_list)
    for digit_num in range(passes):
        new_list = merge(split(new_list, base, digit_num))
    return merge(split_by_sign(new_list))