3

Столкнулся с тем, что необходимо реализовать сортировку шелла используя шаг Хиббарда. В википедии увидел формулу 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 ? Как он её вывел? Пожалуйста, подскажите, очень хочу знать.

1 ответ 1

2

эээ у Шелла по определению последний шаг 1.

иначе возможен случай недосортированности

вообще для Шелла вроде ещё пока не открыта формула для общего случая какой набор убывающих шагов оптимален для заданного размера.

есть только частные случаи.

1
  • Просто мне нужно много разных вариантов шелла протестировать на скорость работы. Для этого мне нужно понять как высчитывать первый шаг. Вот например у Хиббарда формула в википедии 2^k-1. Первый шаг люди вычисляют так: k=log(n+1)/log(2); shag=2^k-1. Как они выразили формулу с логарифмами из первой?
    – iproger
    Commented 1 июн. 2014 в 19:56

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.