алгоритм сортировки Шелла
как задать шаг размером: h[t]=1, h[m-1]=2h[m+1]; t=log2(n-1) алгоритму сортировки Шелла? Попробовал самостоятельно, взяв исходник с другим шагом, подставив свой, но не получилось. Как же задать шаг?
void ShellSort(int* a, size_t n, size_t* bc, size_t* ac, size_t* am) /*шаг задается формулой h[t]=1, h[m-1]=2h[m+1]; t=log2(n-1)*/
{
const int t = (int)(log2(n-1));
int i, j, k, m, x;
/* формирование массива шагов*/
int* h = (int*)malloc(t * sizeof(int));
h[t] = 1;
for (m = t - 2; m >= 0; m--)
h[m-1] = 2*h[m + 1];
/*непосредственно сортировка*/
for (m = 0; m < t; m++) /*последовательно перебираем все расстояния*/
{
k = h[m];
for (i = k; i < n; i++) /*до конца цикла метод вставки с учетом шага h[m]*/
{
x = a[i]; j = i - k;
while (j >= 0 && x < a[j])
{
a[j + k] = a[j];
j -= k;
}
a[j + k] = x;
}
}
free(h);
}
Источник: Stack Overflow на русском