Сортировка

| 06 | 12 I 18 | 42 | 44 | 55 | 67 | эЦ

Рис. 3.5. Пример сортировки Шелла

Приводимая программа не ориентирована на некую определенную последовательность расстояний. Все t расстояний обозначаются соответственно hi, hi, ..., h_t, для них выполняются условия:

h_t=;

h_i+i < h_t.

Каждая /ьсортировка программируется как сортировка с помощью прямого включения.

Анализ алгоритма.При анализе алгоритма возникают очень сложные математические задачи, многие из которых ещё не решены [3, 9]. В частности, не известно, какие расстояния дают наилучшие результаты. Однако выявлен удивительный факт, что они не должны быть множителями друг другу. Дональд Кнут рекомендует такую последовательность [9]:

1 3 7 15 31 где

h_k_x=2h_k+ l;

h_t= 1 и r=[log₂«]-l. В этом случае затраты на сортировку п элементов пропорциональны п ' .