Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19

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

4. 
   Сортировка вставками
   

На первом шаге упорядочиваются один относительно друго— го два первых элемента структуры данных (массива или списка). Затем в упорядочивании участвуют три первых элемента (третий элемент вставляется в соответствующую позицию относительно первых двух элементов), потом — четыре и т. д., пока вся струк- тура данных не будет упорядочена.

Ниже приведен пример алгоритма сортировки простыми вставками (просеиванием или погружением).

177
Hpouepypa copTripOBKH BGTIIBKIIMH HH R3hIKé HIlCKIlJIh.

procedure insert(item: array of char; n: in— teger);

var
a, b: integer; t: char;
begin
for a:=1 to n — 1 do begin
t := item[a];
b := a - 1;
while (b >= 0) and (t < item[b]) do begin
item[bsl] := item[b]; b b-1
end;
item[b + 1] := t end
end;

Hpouepypa cO]3TH]3OBKH BGT£tBKiIMH HH II3hIK£tX CH CH+‘.

void insert sort(char* item, int n) int a, b;
char buf;
for(a=l; a

buf = item[a]:

for(b = a— l; b >= 0 && buf < item[b]; --b) item[b + 1] = item[b];
item[b + 1] = buf;

B OTJIHUHH OT H]3eQsIpyu1 x anro]3HTMOB, UHCJIO C]3lIBHéHH 3II-

BHCHT OT riCxOnHoii ynopxpoUéHHOGTH MI1CCHBI1. EcJIH MllCcriB yme OTCO]3TH]3OBIIH B Tpe6yeMoM nOpspKé, TO 311 BCS B]3eMs pa6oTI›I H]3O- ueqypsI BI›IHOJIHIIéTCII N — 1 oHepillJH C]3lIBHéHHII, éCJIH He OTCO]3TH-
178
рован, то (N ² Щ/2 сравнений. Количество операций присваива- ния при перестановках определяется следующим образом [22]:
в лучшем случае — 2(N— 1);
^{в худшем случае оценивается в общем как} (3^{2 2Щ/2.}
Для среднего случая точную оценку дать достаточно сложно, но в общем виде время работы действительно оказывается средним между лучшим и худшим случаями.
В исходном массиве данный алгоритм произведет переста- новки, показанные на рисунке 13.4.
c---э•d f---e•b

Рис. 13.4 — Обработка массива при сортировке вставками

Этот алгоритм в среднем лишь немного лучше предыдущих (также за счёт разнесения операций присваивания, выполняющих обмен, по разным циклам), но обладает несколькими преимуще- ствами:

• 
  его поведение естественно: если массив уже отсортирован в нужном порядке, алгоритм проводит минимальное количество вычислений, и максимальное, если массив отсортирован в поряд- ке, обратном требуемому. Происходит быстрая обработка почти упорядоченных массивов;
  
• 
  порядок следования одинаковых ключей не изменяется. Если список отсортирован по двум ключам, то после сортировки вставками он остается отсортированным по обоим ключам;
  
• 
  одна из самых коротких процедур среди основных алго- ритмов сортировки.
  

179
Недостаток: при каждой вставке производится сдвиг масси- ва, следовательно даже при относительно малом числе сравнений число перестановок может быть довольно значительным.

Существуют варианты этого алгоритма: бинарные вставки, двухпутевые вставки.
Сортировка вставками хорошо подходит для связных спи- сков, т.к. в этом случае не требуется перенос данных между раз- личными элементами, в отличие от массива.


13.5 Алгоритм Шелла

Разработан Дональдом Л. Шеллом в 1959 году.

Этот алгоритм классифицируется как сортировка вставка- ми с убы вающим шагом.
В первом проходе попарно переставляются элементы, нахо- дящиеся друг от друга на некотором расстоянии, например, 9 по- зиций. Во втором проходе переставляются элементы, отстоящие на меньшее число позиций, например, 5. И т. д. На последнем шаге сортируются соседние элементы. На ранних этапах изуче- ния алгоритма его исследователи отмечали: «Непонятно, как ал- горитм работает».
Принцип убывающих шагов может быть применён для раз- личных базовых сортировок, в том числе для пузырьковой сорти- ровки. В результате такой модификации получается сортировка расчёской.
Эффективность алгоритма заключается в том, что на каж- дом из промежуточных шагов сортируется либо небольшое число элементов, либо уже достаточно хорошо упорядоченные наборы элементов. Упорядоченность массива возрастает после каждого прохода.
Поведение алгоритма Шелла до конца не исследовано до сих пор, в частности, не найдено универсальное решение про- блемы выбора последовательности изменения шага. Исследова- ние алгоритма привело к формулированию нескольких теорем.
Эффективность алгоритма проявляется даже в случае всего двух проходов с шагами h и 1. Время работы в этом случае зави- сит от размера массива как
180


(13.7)
А лучшее значение шага h оказывается равным