I. ВВЕДЕНИЕ В МАТЕМАТИЧЕСКИЙ АНАЛИЗ

End;

Else

Begin

Var

Сортировка подсчетом

End;

End;

End;

Begin

Var

i,j,k,step: integer;

tmp : integer;

step:=N div 2; // первый шаг

while step>=1 do begin

k:=step;

for i:=k+1 to N do begin

tmp:=a[i]; j:=i-k;

while (j>0) and (tmp<a[j]) do begin

a[j+k]:=a[j]; j:=j-k

a[j+k]:=tmp

step:=3*step div 5; // определение следующего шага

end; // Shell

Анализ сортировки Шелла показывает, что порядок ее алгоритма ~N. Это – значительное улучшение по сравнению с «родительской» сортировкой простыми вставками, порядок которой ~N².

Рассмотренные сортировки производились in situ – на том же месте. При наличии достаточного количества памяти можно переписывать элементы из одного массива в другой сразу в нужном порядке. Тогда число наиболее трудоемких операций – пересылок элементов – будет точно N. Разумеется, для определения номера элемента в новом массиве придется сделать какое-то количество сравнений.

В качестве примера возьмем очень простую сортировку методом подсчета. Ее идея заключается в том очевидном факте, что i-й ключ в упорядоченном массиве превышает ровно i-1 остальных ключей, если никакие два ключа не равны. Таким образом, идея состоит в том, чтобы сравнить попарно все ключи и подсчитать, сколько из них меньше каждого отдельного ключа. Сравнить попарно – означает, что достаточно один раз сравнить a[i] и a[j], причем j # i. Для подсчетов числа ключей, меньших данного, используется вспомогательный массив cnt[1..N] of integer, окончательные значения которого служат для пересылки элементов из исходного массива в новый. Для минимального элемента исходного массива значение соответствующего элемента массива счетчиков равно нулю, а стоять минимальный элемент должен на первом месте. Поэтому массив счетчиков инициализируется единицами.

В листинге 7.8 приведен пример сортировки методом подсчета.

Листинг 7.8. Сортировка подсчетом

procedure SortMove(var a,b: TData);

i,j: integer;

cnt: array[1..N] of integer; // массив счетчиков

for i:=1 to N do cnt[i]:=1; // инициализация массива счетчиков

for i:=1 to N do // сравнение элементов

for j:=i+1 to N do // и заполнение массива счетчиков

if a[i]>a[j] then

cnt[i]:=cnt[i]+1

cnt[j]:= cnt[j]+1;

for i:=1 to N do //пересылка элементов в новый массив

b[cnt[i]]:=a[i];

Число сравнений в сортировке подсчетом C~N², число пересылок (из исходного массива в новый) M=N. Сортировка устойчивая. Алгоритм дает правильный результат независимо от числа равных ключей.