Хочу себя проверить

[Andrey173]

Мой ответ не совпадает с учебником.
Язык - паскаль, алгоритм сортировки методом прямых вставок с барьером, по возрастанию.

for i:= 2 to N do
 if a[i-1]>a[i] then    {Если новое число меньше предыдущего}
  begin a[0]:= a[i];   {Выносим его в 0 элемент, "барьер"}
      j:= i-1;
       while a[j]>a[0] do       {И до тех пор пока не найдем место куда поставить новое число}    
     begin a[j+1]:= a[j];       {Сдвигаем старые числа вперед, по массиву}
      j:= j-1;
         end;
  a[j+1]:= a[0];       {Ставим новое число в освободившиеся место}
 end; 

Какое максимальное кол-во сравнений?
Самый плохой случай это когда значения вводят по убыанию.
Тогда во первых будет $n-1$ сравнений в операторе if, и каждый раз его условие будет истинно, значит $n-1$ раз будет выполнятся оператор while. Кол-во сравнений в операторе while-i, для каждой итерации. Например для $i=2$ будет идти сравнение $a[1]>a[0]$ и $a[0]>a[0]$. Т.е. за все итерации $2+3+4+...+n=(n+2)(n-1)/2$
И всего $ n-1+(n+2)(n-1)/2=(2n-2 +n^2 +2n-n -2)/2=(n^2+3n-4)/2$.

[Circiter]

А в книжке что? Мож ($n^2+n-2)/2$?

[Andrey173]

Не, там $(N+1)*N/2$
Я Ваш вариант тоже рассматривал, но сравнения a[0] и a[0] он все же проводит.
И при этом написано что алгоритм имеет сложность кратную $N^2$ по сравнениям. По словам автора это означает, то что при сортировке массивов алгоритм будет выполнять $C*N^2$ действий, где C некоторая константа. Это в среднем или что?
http://www.intuit.ru/department/pl/plpa ... ss/free/4/ - источник

[Circiter]

2Andrey173

Цитата:

Это в среднем или что?

Это асимтотическая сложность, что-то вроде поведения на бесконечности. Например для квадратичной сложности пишут $\mathcal{O}(N^2)$, что характеризует скорость роста числа шагов (времени) в зависимости от размера исходных данных. Посмотрите например в wiki/Big_O_notation.

-- Вт янв 25, 2011 00:38:43 --

Кстати, попробуйте проверить алгоритм на плохих тестовых данных. Каково будет фактическое число сравнений?

Да, что-то я запутался...

[Circiter]

Извините, но там точно в книжке написано $N+1$, а не $N-1$? Просто если убрать вашу лишнюю проверку из второй строки, а также считать, что сравнения нулевого элемента с самим собой не происходит (это легко достигается проверкой самого индекса), то получается именно $(N^2-N)/2$ сравнений.

[Andrey173]

Проверку индекса там специально убрали, поэтому метод "с барьером", до этого алгоритм был без него с проверкой индекса и дополнительной переменной для входящих значений, однако формула именно к этому алгоритму.
Все на сайте книги написано другое (я брал из книги), наверно нашли опечатку.

[Circiter]

2Andrey173

Цитата:

Все на сайте книги написано другое

И что там написано?

Цитата:

поэтому метод "с барьером"

Просто вот интересно, а что это дает? То есть, пытаемся на ранних стадиях избежать лишних проверок или как? В чем преимущество?

Цитата:

Проверку индекса там специально убрали

Я имел ввиду проверку из пятой строки. Убрали/не убрали, это не имеет значения, компилятор и/или run-time среда всё равно могут распознавать тавтологичные сравнения, так что с алгоритмической точки зрения проверка типа a[0] > a[0] не должна учитываться при подсчете числа сравнений. А может и должна. :)

[Lazy]

Circiter в сообщении #405867 писал(а):

Убрали/не убрали, это не имеет значения, компилятор и/или run-time среда всё равно могут распознавать тавтологичные сравнения, так что с алгоритмической точки зрения проверка типа a[0] > a[0] не должна учитываться при подсчете числа сравнений. А может и должна. :)

Вообще-то должна. Однако, насколько мне известно, число сравнений сложность алгоритма не увеличивают. На сложность алгоритма влияют: цикломатическая сложность (циклы while, for, а также копирование объектов классов и т.п.), операции умножения (а также возведения в степень, ну и всякие экспоненты и корни, которые еще "тяжеловеснее"), операции сложения (в большинстве случаев НЕ учитываются, в силу двоичной организации памяти регистров).

Ну и далее "в таком вот акцепте"...

P.S.: Кстати, надежды на компилятор и среду выполнения - безосновательны. Это работает только в достаточно развитых средах, что вряд ли распространяется на Turbo Pascal (хотя это мои личные домыслы - легко могу ошибаться).

[Xaositect]

Lazy в сообщении #406448 писал(а):

Вообще-то должна. Однако, насколько мне известно, число сравнений сложность алгоритма не увеличивают. На сложность алгоритма влияют: цикломатическая сложность (циклы while, for, а также копирование объектов классов и т.п.), операции умножения (а также возведения в степень, ну и всякие экспоненты и корни, которые еще "тяжеловеснее"), операции сложения (в большинстве случаев НЕ учитываются, в силу двоичной организации памяти регистров).

Ну и далее "в таком вот акцепте"...

Сложность алгоритма можно измерять по-разному, а на практике любая инструкция имеет некоторую временную цену, которая зависит в том числе от контекста(напр., окружающих инструкций). В теории сложности обычно для простоты считают, что каждая операция имеют фиксированную цену, причем для некоторых эта цена может быть нулевой - например, считаем только умножения, не рассматривая сложений (кстати, в современных процессорах время выполнения "среднего" умножения не сильно больше времени сложения).
Цикломатическая сложность - это несколько другая концепция. Это статическая сложность, т.е. характеристика программы, а не алгоритма. В общем случае она слабо связана с временем выполнения, но в некоторых довольно типичных случаях может говорить что-то об экспоненте времени выполнения. Но вообще она является не оценкой временной сложности, а оценкой сложности тестирования.

В задачах поиска в массиве и сортировки массива обычно во временной сложности учитываются операции сравнения и/или присваивания элементов массива, поскольку другие операции в классических алгоритмах сортировки и не используются.

[Lazy]

Xaositect, ну как же. По-моему, как раз количество циклов, в основном, и определяет эффективность любого алгоритма сортировки.

А вообще, большое спасибо Вам Вы мне, может быть, больше, чем автору темы помогли

[Xaositect]

Lazy в сообщении #406512 писал(а):

Xaositect, ну как же. По-моему, как раз количество циклов, в основном, и определяет эффективность любого алгоритма сортировки.

Я не уверен, что если написать mergesort без рекурсии, в нем будет меньше 2 циклов.
А если мера сложность не позволяет отличить $n^2$-ные алгоритмы от $n\log n$-ых, то она в этом контексте вряд ли чем-то еще поможет.

Lazy в сообщении #406512 писал(а):

А вообще, большое спасибо Вам Вы мне, может быть, больше, чем автору темы помогли

Ну я Вам и писал, над вопросом автора мне, честно говоря, лень думать. Вряд ли что-нибудь точнее "примерно $n^2/2$" нужно здесь.