int h = 1; // h starts with gap 1

// 3h+1 increment sequence: 1, 4, 13, 40, 121, 364, 1093, ...It could be one, but since h starts with 1 here, the minimum gap possible is 4

while(h < (int)v.size() / 3) // That's Knuth's formula to choose a gap

h = 3 * h + 1;

// Now starting loop from gap to 1, where the pass is h = (h - 1) / 3;

for(int i = h; i > 0; i = (h = (--h/3))) { // loop responsible to decrease h

for (int j = h; j < (int)v.size(); j+=h) { // loop responsible to specify number in the specific gap position

for(int k = j; k > 0 && v[k] < v[k - h]; k-=h) {

swap(v[k],v[k - h]);

}

}

// h = ((h - 1) / 3)

}

// Starting with a big gap, and the gap is reduced by dividing it by 2

for (int gap = (int)v.size()/2; gap > 0; gap/=2) {

// Gap insertion sort for this "gap" interval:

for(int i = gap; i < (int)v.size(); i+=1) {

int temp = v[i]; // getting value that is going to be compared with other elements gap positions before it

int j;

for (j = i; j >= gap && temp < v[j - gap]; j-=gap) {

v[j] = v[j - gap]; // swapping all to gap position ahead

}

v[j] = temp; // putting temp in its correct location

}

}

{

vector<int>v1 = {3,5,4};

vector<int>v2 = {3,5,4,44,26,2};

cout << "Before ShellSort1: ";

for(auto i : v1)

cout << i << " ";

cout << endl;

shellsort1(v1);

cout << "After ShellSort1: ";

for(auto i : v1)

cout << i << " ";

cout << endl;

return 0;