Столкнулся с тем, что необходимо реализовать сортировку шелла используя шаг Хиббарда. В википедии увидел формулу 2^k-1, и не понятно как оно зависит от размера сортируемого массива. На другом сайте прочитал, что должно выполнятся условие 2^k < n <= 2^(k+1) Значит, к примеру пусть будет массив из 10 элементов (n=10). Значит максимальное k = 3. Значит возьмём шаг = 2^3 - 1 = 7. После перестановок 2^2 - 1 = 3. И так, пока шаг не станет нулём или меньше. Но поискав в иностранных источниках, нашёл алгоритм Хиббарда и там я увидел уже совершенно другое, оказывается я не правильно думал.
void hibbardsort(int x[], int n)
{
int i, j,k, increment, temp;
int val;
val=(int) log((float)n+1)/log((float) 2);
increment =pow((float) 2,val)-1;
while (increment > 0)
{
for (i=0;i<increment;i++)
{
for(j=0;j<n;j+=increment)
{
temp=x[j];
for(k=j-increment;k>=0&&temp<x[k];k-=increment)
{
x[k+increment]=x[k];
}
x[k+increment]=temp;
}
}
val--;
if(increment!=1)
increment=pow((float) 2,val)-1;
else
increment = 0;
}
}
В этом алгоритме максимальное k (в коде это val) вычисляется по непонятному для меня принципу log(n+1)/log(2). По такому алгоритму для 10 максимальный k - это 1 (у меня 7). Почему так? Почему я не прав? Откуда тот, кто писал этот алгоритм узнал формулу вычисления максимального k ? Как он её вывел? Пожалуйста, подскажите, очень хочу знать.