Сортировка Шелла, оптимальный выбор приращений

[Если вы не знакомы с сортировкой Шелла как таковой, то быстрей прочитайте задачу сортировка Шелла, общий принцип]

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

Очевидно, что программист может выбрать любой алгоритм уменьшения этого приращения на каждом шаге, главное, чтобы в конце оно приняло значение 1. Существует немало стратегий рассчета приращения на каждом проходе алгоритма Шелла.

Например, Р. Седжвик, предложил такую схему вычисления прирашений:
d[i] = 9*2ⁱ - 9*2^i/2 + 1, если i четно
d[i] = 8*2ⁱ - 6*2^(i+1)/2 + 1, если i нечетно

Было доказано, что используя эту схему производительность алгоритма возрастает ~ O(n^7/6) в среднем и до ~ O(n^4/3) в худшем случае. При расчете приращений по этому методу останавливаться следует на значении d[i-1], если 3*d[i] > n. Обычно расчет начинается с нулевых значений i(=[0,1,2...]) и продолжается до такого i, когда 3*d[i+1] > n, как было сказано ранее. Т.о. данная процедура рассчета запускается перед самой сортировкой Шелла и затем хранит полученную таблицу приращений в памяти, а алгоритм сортировки на каждом шаге к ней обращается за очередным значением.

Например, пусть имеем последовательность из n=35 элементов. Тогда:
Dsedj[0] = 1, Dsedj[1] = 5, Dsedj[2] = 19. Поскольку 3*19 > 35, останавливаемся на значении 5, получая последовательность приращений для данного n=35:[1,5]. Т.е. всего лишь 1 и 5. В базовой реализации мы бы имели:[17, 8, 4, 2, 1].

Алгоритм расчета приращений Седжвика будет иметь вид:

p1 = p2 = p3 = 1
i = -1;
loop
  if (++i % 2) 
    d[i] = 8*p1 - 6*p2 + 1
  else
    d[i] = 9*p1 - 9*p3 + 1
    p2 *= 2
    p3 *= 2
 
  p1 *= 2
  if 3*d[i] >= n
    break
 
if i > 0
  return --i
 
return 0

Cуществует другое мнение: для достаточно больших массивов рекомендуемой можно считать последовательность таких d_i, что:
d_i+1 = 3d_i + 1;
т.е., последовательность включает по порядку приращения: ..., 364, 121, 40, 13, 4, 1. Начинается процесс с d_m-2, где m - наименьшее целое, такое, что d_m >= n;

Для нашего случая с n=35 получим: d=[1,4], поскольку h₃=40 > n=35 => i_max = 3-1 = 1

Алгоритм рассчета таких приращений имеет вид:

i    = 0
d[0] = 1
 
while (d[i] < n)
  i++
  d[i] = 3*d[i-1] + 1
 
if i < 2
  return 0
 
return i-2

Реализации:

заполните необходимые поля!

название:
uri-имя*:
заголовок окна:
ЯП:	[другой...] pseudojavajavascriptpythonC++C#CphpGoqbasicrailsrubysmartytsqlvbnetvisualfoxproxmlactionscriptplsqlpascaloracle8sqlvbfortransmalltalkasmcssdelphigroovylispperlmysqlmatlab
код (double click - редактирование) (Esc - предпросмотр)
описание:
автор:	email:
пароль:	[для последующего редактирования]
	подписаться на комментарии**

*	можно кириллицей (недопустимые символы:?&+=\/%#)
**	только для зарегистрированных пользователей