template<class T>
void swap(T* x, int i, int j) {
T tmp;
tmp = x[i]; x[i] = x[j]; x[j] = tmp;
}
/* Рассчитывает последовательность
приращений по методу Р. Седжвика */
int Dsedj(int d[], long n) {
int p1, p2, p3, i;
p1 = p2 = p3 = 1;
i = -1;
do {
if (++i % 2) {
d[i] = 8*p1 - 6*p2 + 1;
} else {
d[i] = 9*p1 - 9*p3 + 1;
p2 *= 2;
p3 *= 2;
}
p1 *= 2;
} while(3*d[i] < n);
return (i > 0) ? --i : 0;
}
/* Сортировка Шелла */
template<class T>
void BaseShellSortDSedj(T* x) {
/* максимальное количество рассчитываемых
приращений = 20 */
int d, i, j, dseq[20];
int di;
/* Рассчитываем последовательность
приращений */
di = Dsedj(dseq, n);
while (di > 0) {
/* Приращение на данной итерации */
d = dseq[di--];
int i = 0, j = 0;
/* Делает проход пузырька для групп
пока расстояние между сортируемыми
элементами не станет = 1 */
while (j = i + d < n) {
if (x[i] > x[j]) {
swap(x, i, j);
}
i++;
}
}
/* Заключительная элементарная сортировка
полученной последовательности из 2-х
отсортированных групп */
InsertSort(x);
}