Программирование на языке Pascal
Таким образом, стало ясно, что
Таким образом, стало ясно, что t можно вычислить по следующей формуле:
t = trunc(log N))
К сожалению, язык Pascal предоставляет возможность логарифмировать только по основанию е (натуральный логарифм). Поэтому нам придется вспомнить знакомое из курса средней школы правило "превращения" логарифмов:
logmx =logzx/logzm
В нашем случае m = 2, z = e. Таким образом, для начального t получаем:
t:= trunc(ln(N)/ln(2)).
Однако при таком t часть подпоследовательностей будет иметь длину 2, а часть - и вовсе 1. Сортировать такие подпоследовательности незачем, поэтому стоит сразу же отступить еще на 1 шаг:
t:= trunc(ln(N)/ln(2))-1
Расстояние между элементами в любой подпоследовательности вычисляется так:
k:= (1 shl t)-1; {k= 2t-1}
Количество подпоследовательностей будет равно в точности k. В самом деле, каждый из первых k элементов служит началом для очередной подпоследовательности. А дальше, начиная с (k+1)-го, все элементы уже являются членами некоторой, ранее появившейся подпоследовательности, значит, никакая новая подпоследовательность не сможет начаться в середине массива.
Сколько же элементов будет входить в каждую подпоследовательность? Ответ таков: если длину всей сортируемой последовательности (N) можно разделить на шаг k без остатка, тогда все подпоследовательности будут иметь одинаковую длину, а именно:
s:= N div k;
Если же N не делится на шаг k нацело, то первые р подпоследовательностей будут длиннее на 1. Количество таких "удлиненных" подпоследовательностей совпадает с длиной "хвоста" - остатка от деления N на шаг k:
P:= N mod k;
Реализация алгоритма УлШелл
Ради большей наглядности мы пожертвовали эффективностью и воспользовались алгоритмом ПрВст, а не ПрВстБар или БинВст. Дотошному же читателю предоставляется возможность самостоятельно улучшить предлагаемую реализацию:
program shell_sort; const n=18; a:array[1..n] of integer =(18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1); var ii,m,x,s,p,t,k,r,i,j: integer; begin t:= trunc(ln(n)/ln(2)); repeat t:= t-1; k:= (1 shl t)-1; p:= n mod k; s:= n div k; if p=0 then p:= k else s:= s+1;
