Самая быстрая последовательность зазоров для сортировки оболочки?

Ответ 1

Если ваш набор данных имеет определенную верхнюю границу по размеру, вы можете жестко скопировать последовательность шагов. Вероятно, вы должны только беспокоиться об общности, если ваш набор данных, скорее всего, будет расти без верхней границы.

Показанная последовательность, по-видимому, растет примерно как экспоненциальный ряд, хотя и с причудами. Кажется, что большинство простых чисел, но также и без простых чисел. Я не вижу явной формулы поколения.

Допустимый вопрос, предполагающий, что вы должны иметь дело с произвольно большими наборами, заключается в том, нужно ли подчеркивать наихудшую производительность, среднюю производительность или почти-отсортированную производительность. Если последнее, вы можете обнаружить, что простая сортировка вставки с использованием двоичного поиска для этапа вставки может быть лучше, чем оболочка. Если вам нужна хорошая производительность в худшем случае, то, похоже, предпочтение отдается последовательности Sedgewick. Последовательность, которую вы упомянули, оптимизирована для производительности среднего уровня, где количество сравнений перевешивает количество ходов.

Ответ 2

Бумага Ciura генерирует последовательность эмпирически - то есть, он пробовал кучу комбинаций, и это был тот, который работал лучше всего. Создание оптимальной последовательности оболочек оказалось сложным, и проблема до сих пор была устойчивой к анализу.

Наиболее известным приращением является Sedgewick's, о котором вы можете прочитать здесь здесь (см. стр. 7).

Ответ 3

Мне не стыдно было бы воспользоваться советом, приведенным в Wikipedia Shellsort,

Что касается среднего числа сравнений, то самый известный разрыв последовательности - 1, 4, 10, 23, 57, 132, 301, 701 и аналогичные, с пробелами найденных экспериментально. Оптимальные пробелы за пределами 701 остаются неизвестными, но хорошими результаты могут быть получены путем расширения указанной последовательности согласно рекурсивная формула h_k =\lfloor 2.25 h_ {k-1}\rfloor.

Токуда последовательность [1, 4, 9, 20, 46, 103,...], определяемая простой формулой h_k =\lceil h'_k \ rceil, где h'k = 2,25h'k - 1 + 1, h'1 = 1, можно рекомендовать для практических приложений.

Угадывая из псевдонима, кажется, что Марцин Сьюра сам отредактировал статью WP.

Ответ 4

Последовательность 1, 4, 10, 23, 57, 132, 301, 701, 1750. Для каждого следующего номера после 1750 умножьте предыдущее число на 2.25 и округлите вниз.

Ответ 5

Я нашел эту последовательность, похожую на последовательность Marcin Ciura:

1, 4, 9, 23, 57, 138, 326, 749, 1695, 3785, 8359, 18298, 39744, etc.

Например, последовательность Ciura:

1, 4, 10, 23, 57, 132, 301, 701, 1750

Это среднее из простых чисел. Код Python для поиска среднего числа чисел здесь:

import numpy as np

def isprime(n):
    ''' Check if integer n is a prime '''
    n = abs(int(n))  # n is a positive integer
    if n < 2:  # 0 and 1 are not primes
        return False
    if n == 2:  # 2 is the only even prime number
        return True
    if not n & 1:  # all other even numbers are not primes
        return False
    # Range starts with 3 and only needs to go up the square root
    # of n for all odd numbers
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True

# To apply a function to a numpy array, one have to vectorize the function
vectorized_isprime = np.vectorize(isprime)

a = np.arange(10000000)
primes = a[vectorized_isprime(a)]
#print(primes)
for i in range(2,20):
    print(primes[0:2**i].mean())

Вывод:

4.25
9.625
23.8125
57.84375
138.953125
326.1015625
749.04296875
1695.60742188
3785.09082031
8359.52587891
18298.4733887
39744.887085
85764.6216431
184011.130096
392925.738174
835387.635033
1769455.40302
3735498.24225

Зазор в последовательности медленно уменьшается от 2,5 до 2. Возможно, эта связь может улучшить Shellsort в будущем.