#include "ShellSortSedj1.h"
 
ShellSortSedj1::ShellSortSedj1(int n, int* x, int maxIncNum, bool getIncs) : ShellSort(n, x) {
    this->algName = "Shell Sort [Sejvick, Without InsertSort]";
 
    // Рассчитываем таблицу приращений
    if (getIncs) {
        this->dseq = new int[maxIncNum];
        this->di   = this->GetIncrements();
    }
}
 
int ShellSortSedj1::GetIncrements(void) {
    int p1, p2, p3, i;
 
    p1 = p2 = p3 = 1;
    i = -1;
    do {
        if (++i % 2) {
            this->dseq[i] = 8*p1 - 6*p2 + 1;
        } else {
            this->dseq[i] = 9*p1 - 9*p3 + 1;
            p2 *= 2;
            p3 *= 2;
        }
        p1 *= 2;
    } while(3*this->dseq[i] < this->n);  
 
    return (i > 0) ? --i : 0;
}
 
void ShellSortSedj1::Run(void) {
    /* максимальное количество рассчитываемых
       приращений = 20(хватит более чем достаточно) */
    int d, i, j;
    int _di = this->di;
    while (_di >= 0) {
        /* Приращение на данном шаге */
        d = this->dseq[ _di-- ];
 
        /* этот цикл делает проход "пузырька" в том числе и
           для последней последовательности, когда d=1, поэтому
           вызывать в конце InsertSort или какую-либо другую
           элементарную сортировку - не требуется */
        for (i = d; i < this->n; i++) {
            int tmp = this->x[i];
            for (j = i-d; (j >= 0) && (this->x[j] > tmp); j -= d) {
                this->x[j+d] = this->x[j];
                this->CountSwap();
            }
            x[j+d] = tmp;
            this->CountSwap();
        }
    }
    /* Не требуется вызывать InsertSort или BubbleSort
       т.е. ко всей последовательности во вложенном цикле
       уже был применен метод пузырька */
}
 
int ShellSortSedj1::GetInc(int incNum) {
    return this->dseq[ incNum ];
}
 
ShellSortSedj1::~ShellSortSedj1(void)
{
}