Очень быстрый способ сортировки массива целых чисел?

Question

Я пришел сюда с решением, которое я только что написал, но я определенно не могу найти лучший способ отсортировать мой массив как можно быстрее.

Мне нужен алгоритм, чтобы дать мне ответ менее чем за 1 секунду, на массив, содержащий 100 000 целых чисел.

Вот код:

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 это количество элементов, в нашем случае 100'000, как я сказал.

Дело в том, после того, как мой массив отсортирован, мне нужно цикл через него и рассчитать минимальное расстояние между двумя целыми числами:

Например, с (3, 5, 8, 9), минимальное расстояние 1 (от 8 до 9).

Я такой новичок в Bash, поэтому я даже не знаю, эффективен ли это;

В самом деле, прирост скорости может исходить от второй части кода, а не из сортировочной части ...

Есть идеи?

Спасибо заранее,

Answer 1

я, наконец, пришел с простым и довольно элегантным решением:

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;}' 

И это все. :) Спасибо всем, что нашли время, чтобы помочь мне! ;)

Answer 2

номера варьируются <0,1000000) достаточно мал

• как ваши номера не повторяющиеся (smalest расстояние> = 40)
• тогда вам просто нужно немного за значение (если он присутствует или нет)
• , так что вам нужно до 1 МБ для байт/значение или до 128 КБ для бит/значение
• (поскольку K, M основаны на 1024, поэтому у вас достаточно большое резерв)

так Bucket рода возможность:

1. создать массив флагов для каждого возможного значения

   • bool flag[1000000];

2. четкие флаги O(M)

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

3. вычислительные флаги по обработке вашего массива arr[N] ...O(N)

   • for (int i=0;i<N;i++) flag[arr[i]]=1;
   • для повторения только увеличиваем флаг [], если он не является слишком большим, чтобы избежать переполнения в случае
   • flag[arr[i]] уже 1 затем вернуться distance = 0

4. реконструировать массив O(M)

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

5. Теперь вычислить расстояние O(N)

   • вы можете смешать эти шаги вместе, так что вам не нужно arr[N] в памяти
   • вместо этого просто считать последовательные нули в flag[] ...

[Примечания]

• M=1000000
• N<=M
• если N гораздо гораздо меньше, чем M то это не может быть самым быстрым способом ...

Answer 3

Учитывая эту удивительную страницу на sorting algorithm complexity I использовал бы Radix Sort (here in Python, я не нашел реализацию Bash, но я все еще ищу):

#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))