Программирование на языке Pascal




Сортировка Шелла - часть 2


Таким образом, стало ясно, что 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;




Содержание  Назад  Вперед