Алгоритмы сортировки вставками

Алгоритмы сортировки вставками отличаются от приведенных выше алгоритмов тем, что ищутся не «элементы для мест», а «места для элементов». Из семейства этих алгоритмов рассмотрим алгоритм прямых вставок. В массиве выделяем две части: отсортированную и нет. Сначала отсортированная часть содержит только первый элемент (сам по себе благоустроенный). Дальше каждый раз берем

[smszamok]

первое значение и «перетягиваем» его к отсортированной так, чтобы она не потеряла благоустроенности. Для этого передвигаем текущее значение по левую сторону до тех пор, пока оно не займет свое правильное место в отсортированной части массива, т.е. когда значение по левую сторону и по правую сторону текущего будут стоять «правильно» относительно него. Итак, элемент «вставляется» в отсортированную часть массива (откуда и название метода).

procedure insertSort(var A:alnt; n:word);
var и, k : word; begin
for k:=2 to n do begin и : =k; while (A[i]<A[i-l])and(i>l) do begin
swap(A[i], A[i-1]); dec(i); end; end; end;

Поскольку сдвиг элемента на одну позицию по левую сторону «стоит» три команды присваивания, рекомендуем запомнить эталонный элемент (тот, для которого ищется место в отсортированной части) в дополнительной сменной. Тогда сдвиг можно выполнить одним присваиваниям, а запам’ятований элемент потом одним присваиваниям поставить на уволенное место.

procedure insertSort (var A:alnt; n-.word);
var i, k : word; etalon : integer; begin
for k:=2 to n do begin etalon:=A[k]; i:=k;
while (i>l) and (A[i-1]>etalon) do begin A[i]:=A[i-l]; dec(i);
end;
А[и] :=etalon; end; end;

Сложность этого метода также имеет оценку Щп2). В нем, как и в сортировке «пузырьком», выполняется много обменов соседних элементов. В 1959 году Д.Шелл предложил усовершенствование алгоритма прямых вставок. Его идея — сравнивать элементы, которые находятся на определенном расстоянии один от другого и уменьшать это расстояние.

Рассмотрим пример. Пусть массив имеет такой вид: 44 55 12 42 94 18 06 67 Сначала отдельно сгруппируем и упорядочим с помощью прямых вставок элементы, которые находятся на расстоянии 4 (четвертное упорядочение). В этом примере восемь элементов, поэтому группы содержат по два элемента.

1
1
55
94
f
67
44 18 06 42
Теперь сгруппируем элементы на расстоянии 2 [двойное упорядочение). Имеем две группы по четыре элемента.
J и І \
Об 18 12 42 44 55 94 67
t и t t
В конце концов, выполним обычное (одинарное) упорядочение, сравнивая соседние элементы.
06 12 18 42 44 55 67 94 З описанного понятно, что начальное расстояние h = и/2. После каждого прохода она уменьшается вдвое.
procedure ShellSort(var A:alnt; n:word); var и, j, h : word; temp integer; begin
h := n div 2; while h>0 do begin , for и := h to n-h+1 do
begin
j:=i; temp:=А[и];
while (j>=h)and(temp<A[j-h]) do begin A[j]:=A[j-h]; dec(j,h); end;
A[j] := temp; end;
h := h div 2; end; end;

[/smszamok]

Итак, идея метода Шелла: изменить массив так, чтобы каждая группа элементов на расстоянии h была благоустроенной. Это разрешает за некоторого ряда расстояний сравнения h, последняя из которых равняется единице, получить упорядоченный массив. Но какую последовательность шагов следует избрать? Было изобретено много рядов расстояний h, которые хорошо зарекомендовали себя, но наилучшей среди них нет. Доказано лишь, что лучшие результаты дают расстояния, которые не являются делителями одна одной. В основном используют нисходящие геометрические прогрессии, поскольку в этой ситуации количество шагов близкое к log г.