Учебное пособие: Основы дискретной математики

begin (*заданиеэлементовмассива*)

for i: – l to N do begin write ('введитеэлементa [', i, ']= ');

readln (a[i]);

end;

for i:=1 to N do begin write (a[i], ' ');

end;

writeln;

(*алгоритм сортировки двоичным включением*)

for i:=2 to n do

begin

x:=a[i]; L:=l; R:^i;

while L<R do

begin

m:=(L+R) div 2; if a [m] <=x then L:=m+1 else R:=m;

end;

for j:=i downto R+l do a[j]:=a [j‑1];

a[R]:=x; end;

(* вывод отсортированного массива*)

for i: – l to N do

begin write (a[i], ' ');

end;

readln;

end.

Сортировка Шелла

Метод, предложенный Дональдом Л. Шеллом, является неустойчивой сортировкой по месту. Эффективность метода Шелла объясняется тем, что сдвигаемые элементы быстро попадают на нужные места. Среднее время для сортировки Шелла равняется O (n ^1.25 ), для худшего случая оценкой является O (n ^1.5 ). Дальнейшие ссылки см. в книге Кнута [4].

На рисунке 1.8 приведен пример сортировки вставками. Мы сначала вынимали 1, затем сдвигали 3 и 5 на одну позицию вниз, после чего вставляли 1. Таким образом, нам требовались два сдвига. В следующий раз нам требовалось два сдвига, чтобы вставить на нужное место 2. На весь процесс нам требовалось 2+2+1=5 сдвигов.

На рисунке 1.9 иллюстрируется сортировка Шелла. Мы начинаем, производя сортировку вставками с шагом 2. Сначала мы рассматриваем числа 3 и 1: извлекаем 2, сдвигаем 3 на 1 позицию с шагом 2, вставляем 2. Затем повторяем то же для чисел 5 и 2: извлекаем 2, сдвигаем вниз 5, вставляем 2 и т. д. Закончив сортировку с шагом 2, производим ее с шагом 1, т. е. выполняем обычную сортировку вставками. Всего при этом нам понадобится 1 + 1+ 1 = 3 сдвига. Таким образом, использовав вначале шаг, больший 1, мы добились меньшего числа сдвигов.

Рис унок 1.9 – Сортировка Шелла