Количество размещений "кактуса" по n (комбинаторная задача)

[Mihaylo]

Подвожу итог:

1) Я как-то не обратил внимание, что в алгоритме ENTROPY-SORT вторая часть алгоритма является модификацией пузырьковой сортировки. Вместо обмена (swap) двух элементов массива в ENTROPY-SORT обмениваются целые поддеревья (функция SWAP_TREE).

2) Алгоритм сортировки посредством вставок и слияний является родственником алгоритма ENTROPY-SORT. Первая часть алгоритмов совпадает. Вторая часть алгоритма сортировки посредством вставок и слияний является модификацией алгоритма сортировки методом бинарных вставок: также вместо обмена отдельных элементов осуществляется обмен поддеревьев. По-крайней мере я так понял алгоритм из описания Д.Кнута.


Д.Кнут пишет про сортировку методом бинарных вставок: алгоритм опубликован Гуго Штейнхаузом (Hugo Steinhaus) в 1950-м году. Тогда он предположил, что его алгоритм идеален по количеству сравнений, но в 1959 году он сам сообщил, что найдены более оптимальные варианты сортировки для числа элементов от 2 до 11. Так был открыт алгоритм сортировки посредством вставок и слияний двумя учеными - С. Трибулой и П. Чженом.
При различном размере массива $n$ худшее число сравнений алгоритма сортировки посредством вставок и слияний очень часто совпадает с теоретическим минимумом $\log n$. В 1979 году было доказано, что существует бесконечное число значений $n$, при которых число сравнений не равно идеалу $\log n$. То есть алгоритм неидеален.

Я вот думаю, что если придумать переборный алгоритм, который будет подсчитывать математическое ожидание энтропии с тем, чтобы в конце концов реализовать тот самый жадный алгоритм, о котором я уже много раз говорил. Ведь ENTROPY-SORT таковым не является!

[Mihaylo]

Алгоритм сортировки посредством вставок и слияний (merge insertion sort), описанный Кнутом в 5.3.1, "Искусство программирования", том 3, называется FJA (Ford-Johnson sorting alogorithm). В некоторых статьях его называют 4FJ.
Задачей оптимальной сортировки является достижение минимального числа сравнений $S(n)$ для данного числа элементов массива $n$ в наихудшем случае (минимаксная оптимизация).
Алгоритм FJA является лучшим известным таким алгоритмом, Glenn K. Manacher в статье "The Ford-Johnson Sorting Algorithm Is Not Optimal" (1979) показал, что минимальное число сравнений $F(n)$ алгоритма FJA отклоняется от $S(n)$: $F(n)-S(n)=K\cdot n - O(\log n)$, для $n\geqslant 189$.

Итак, $\left\lceil\log n!\right\rceil\leqslant S(n)\leqslant F(n)$,
где $\left\lceil\log n!\right\rceil$ - теоретический предел количества сравнений в наихудшем случае;
$S(n)$ - "практический" предел количества сравнений в наихудшем случае;
$F(n)$ - результат алгоритма FJA в наихудшем случае.

Алгоритм FJA, также как алгоритм ENTROPY-SORT, сначала осуществляет сравнения в соответствии со структурой жадного дерева сравнения. Чтобы не быть голословным, покажу это дерево картинкой для $n=16$.

$T$ - это число вершин, которые входят в поддерево данной вершины (обозначение было принято ранее в этой теме).
Сравнения осуществляются снизу вверх: сначала получаются листья ($T=1$), затем $T=2$ и самым последним сравнением строится дуга между $T=16$ и $T=8$ - всего $(n-1)$ жадных сравнений.
После построения жадного дерева алгоритм FJA, пытаясь сортировать $n$ элементов, сводит эту задачу к задаче сортировки меньшего числа элементов $\left\lfloor\frac{n}{2}\right\rfloor$ путем отбрасывания листьев дерева (вершины с $T=1$) и затем рекурсивно вызывая самого себя. Надо обратить внимание, что в результате отбрасывания листьев получается дерево, повторяющее структуру жадного дерева (исходного дерева).
Как только рекурсия дойдет до самого верха, начинается собственно сортировка, характеризующая FJA. При возврате из рекурсии приходится сортировать дерево вида

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

[Mihaylo]

Hosam M. Mahmoud в своей книге "Sorting: A Distribution Theory" (с. 293) пишет, что G.K.Manacher не просто доказал несовершенство алгоритма FJA, но и сделал это конструктивно. Он заменил метод бинарных вставок на более гибкий алгоритм слияния HWANG-LIN. Усовершенствованный алгоритм, начиная с $n=189$, использует меньше сравнений.

P.S. Поправка: 4FJ - это обозначение не самого алгоритма FJA, а его усовершенствованной модификации, использующей меньше памяти.