Самая быстрая последовательность разрыва для вида оболочки?
Согласно Оптимальной (самой известной) последовательности Marcin Ciura инкрементов для алгоритма сортировки оболочки, лучшая последовательность для shellsort равняется 1, 4, 10, 23, 57, 132, 301, 701..., но как я могу генерировать такую последовательность? В статье Marcin Ciura он сказал:
И последовательности Knuth и Hibbard относительно плохи, потому что они определяются простыми линейными повторениями.
но большинство книг алгоритма, которые я нашел, имеет тенденцию использовать последовательность Knuth: k = 3k + 1, потому что легко генерировать. Что Ваш способ генерировать последовательность shellsort?
2 ответа
Если ваш набор данных имеет определенную верхнюю границу размера, вы можете жестко запрограммировать последовательность шагов. Вам, вероятно, следует беспокоиться об общности только в том случае, если ваш набор данных, вероятно, будет расти без верхней границы.
Показанная последовательность, кажется, растет примерно как экспоненциальный ряд, хотя и с причудами. Кажется, что большинство простых чисел, но с ними тоже. Я не вижу очевидной формулы поколения.
Правильный вопрос, предполагающий, что вы должны иметь дело с произвольно большими наборами, заключается в том, нужно ли вам делать упор на производительность в наихудшем случае, производительность в среднем случае или производительность с почти сортировкой. В последнем случае вы можете обнаружить, что простая сортировка вставкой с использованием двоичного поиска для шага вставки может быть лучше, чем сортировка оболочки. Если вам нужна хорошая производительность в худшем случае, то вам подойдет последовательность Седжвика. Упомянутая вами последовательность оптимизирована для производительности в среднем случае, когда количество сравнений перевешивает количество ходов.
В статье Чиуры последовательность генерируется эмпирически, то есть он перепробовал множество комбинаций, и это была та, которая сработала лучше всего. Создание оптимальной последовательности шелл-сортировки оказалось сложной задачей, и проблема до сих пор не поддавалась анализу.
Наиболее известным приращением является приращение Седжвика, о котором вы можете прочитать здесь (см. Стр. 7).