Сортировка Шелла - C (СИ) (151816)

Формулировка задачи:

Написать функцию сортировки методом Шелла, значения расстояния d в ходе работы функции должны образовывать последовательность Фибоначчи, начиная с максимального числа Фиббоначи, меньшего n(количества элементов последовательности)

Решение задачи: «Сортировка Шелла»

Листинг программы

void ShellsSort(Type *a, unsigned n)
{
    unsigned i, j, *h;
    int t;
 
    t = (unsigned) (log((double) n) / log(3.0) -1);
    t+=1;
    h = (unsigned *) calloc(t, sizeof(unsigned));
    h[0] = 1;
    for (i = 1; i < t+1; i++) h[i] = h[i - 1] * 3 + 1;
    for (; t >= 0; t--)
    {
        for (i = 0; i+h[t] < n; i++)
        {
            for (j = 0; j + h[t] < n ; j++)
            if (a[j] > a[j + h[t]]) Swap(&a[j], &a[j + h[t]]);
        }
    }
}

Объяснение кода листинга программы

В функции ShellsSort определен тип Type (вероятно, это должен быть тип данных, который может хранить значения элементов массива).
Переменная n инициализируется значением размера массива a.
В функции используется переменная t, которая инициализируется значением степени двойки, логарифм которой равен логарифму числа n по основанию 3 (предполагается, что n всегда больше 1).
Переменная h инициализируется значением массива, выделенного динамически с помощью calloc, который будет использоваться для хранения значений, полученных из вычисления h[i] = h[i - 1] * 3 + 1.
Значение первого элемента массива h устанавливается равным 1.
В цикле for с переменной i от 1 до t+1 происходит вычисление значений элементов массива h с помощью формулы h[i] = h[i - 1] * 3 + 1.
В цикле for с переменной t от 0 до log2(n) (предполагается, что n всегда больше 1) происходит сортировка массива a с помощью алгоритма сортировки Шелла.
Внутренний цикл for с переменной i от 0 до n-h[t] выполняется до тех пор, пока не будет выполнено условие i+h[t] < n, т.е. пока не будет достигнут конец массива a.
Во внутреннем цикле for с переменной j от 0 до n-h[t] происходит сравнение элементов массива a и, если элемент a[j] больше элемента a[j+h[t]], выполняется обмен элементов с помощью функции Swap.
Если значение переменной t больше или равно 0, то цикл for завершается.
Если значение переменной t меньше 0, то происходит освобождение памяти, выделенной под массив h, с помощью функции free.