алгоритм Шелла

[rostik123]

как увеличить скорость этого алгоритма Шелла в 2 раза ....


Где-то читал про Сортировку методом Шелла-Кнута.
Кнут просто подобрал номера h для увеличения скорости сортровкы.
Но я не знаю сделать методом Шелла-Кнута.


/ * Метод Кнута h (k-1) = 3 * h (k) +1, h (t) = 1, где
h (i) - шаг сортировки,
t = ln (n) / ln (3) -1 - число шагов сортировки,
n - длина списка * /



void sort_Shell(int *mass, int SIZE)
{
int step = SIZE / 2;//инициализируем шаг.
while (step > 0)//пока шаг не 0
{
for (int i = 0; i < (SIZE - step); i++)
{
int j = i;
while (j >= 0 && mass[j] > mass[j + step])
{
int temp = mass[j];
mass[j] = mass[j + step];
mass[j + step] = temp;
j--;
}
}
step = step / 2;
}
}

[rostik123]

void ShellSort(int *a, int n)
{
int h;
for(h=1; h<(n-1)/9; h=3*h+1);
for(... ; h>0; h/=3) //а что здесь написать не знаю
for(int s=0; s<h; s++)
{
for(int i=s; i<n-h; i+=h)
{
int z=i;
for(int j=i+h; j<n; j+=h)
if(a[j]<a[z])
z=j;
int r=a[i];
a[i]=a[z];
a[z]=r;
}
}
}

[rostik123]

сделал, сортирует быстрее, но надо еще быстрее ...


void sort_Shell(int *mass, int SIZE)
{
int step = SIZE / 2, i, j, tmp;
while (step > 0) {

for(i = step; i < SIZE; ++i) {
tmp = mass[i];

for(j = i - step; j >= 0 && mass[j] > tmp; j -= step) {
mass[j+step] = mass[j];

}
mass[j+step] = tmp;
}
step /= 2;
}
}