алгоритм сортировки Шелла

Рейтинг: -1Ответов: 1Опубликовано: 06.06.2023

как задать шаг размером: 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);
}

Ответы

▲ 0Принят

Так (с удвоением) задать шаги можно, но это невыгодный метод, например, четные и нечетные элементы не сравниваются до последнего шага (шаг 1), т.е. часто будет получаться квадратичная сложность. Тем не менее метод должен быть рабочим.

У вас несогласованность в размере массива и задании самого последнего шага - в массиве размером t последний элемент имеет индекс t-1, а вы задаёте t-й, и в предыдущих у вас что попало, и шаг размером 1 не используется. Исправьте

h[t-1] = 1;

И ещё одно заметил:

h[m] = 2*h[m + 1];