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

Содержание:
1. Бинарные вставки
2. Двухпутевые вставки
3. Вставки одновременно нескольких элементов
4. Вставки с убывающим шагом (метод Шелла)
5. Вставки в связанный список
6. Вставки в несколько связанных списков

Методы вставки. Алгоритм простых вставок.

{сортировка вставкой}
procedure Inser(var item: DataArray; count:integer);
var
i, l: integer;
x: DataItem;
begin
for i := 2 to count do
begin
x := item[i];
j := i-1;
while (x0) do
begin
item[j+1] := item[j];
j := j-1;
end;
item[j+1] := x;
end;
end;

Ниже описан основной алгоритм простых вставок, который порождает несколько модификаций, используемых в заданиях. Алгоритм использует прием, которым пользуются игроки в карты при сортировке только что розданной колоды: очередная карта вставляется между уже упорядоченными ранее. Описание алгоритма простых вставок. Файл, подлежащий сортировке, в общем случае состоит из элементов-записей, включающих информационную часть и ключи, по которым производится упорядочение по возрастанию. Поскольку информационная часть почти не влияет на процесс сортировки, будем предполагать, что файлы, используемые в примерах, состоит только из элементов-ключей, а информационная часть записи отсутствует. Здесь k[1], k[2], ... , k[N] - ключи, по которым производится упорядочение файла. X,i,j - рабочие переменные.

Для примера возьмем файл, состоящий из 8 элементов:
Исх.файл.: 503 87 512 61 908 170 897 275
Алгоритм будет преобразовывать его следующим образом:
j=2. Исх : 503 87 X=87
Рез : °87 503

j=3 : 87 503 °512 X=512
j=4 : °61 87 503 512 X=61
j=5 : 61 87 503 512 °908 X=908
j=6 : 61 87 °170 503 512 908 X=170
j=7 : 61 87 170 503 512 °897 908 X=897
j=8 : 61 87 170 °275 503 512 897 908 X=275
Время работы алгоритма t примерно оценивается формулой:
t=a*N + b*N, где a,b - неизвестные константы, зависящие от программной реализации алгоритма.

Модификации алгоритма простых вставок.

1. Бинарные вставки

{сортировка бинарными вставками}
for i:=2 to n do
begin
r:=i;
l:=i;
while (lbegin
k:=(l+r) div 2;
if a[k]>a[i] then l:=k+1;
else r:=k;
end;
k:=r;
x:=a[i];
for m:=i downto k+1 do
a[m]:=a[m-1];
a[k]:=x;
end;

Для ускорения числа сравнений при поиске места, в которое нужно вставить элемент X, можно использовать логарифмический поиск. Это означает, что сначала Х сравнивается с элементом k[j/2], затем, в зависимости от результата сравнения, с элементом, лежащим посередине между 1 и j/2 или посередине между j/2+1 и j и т.д. . При этом число сравнений для каждого j равно примерно log(j). Число пересылок элементов при этом не изменяется и остается примерно равным N/4. Время работы алгоритма t примерно оценивается формулой:
t=a*N + b*N + c*N*logN, где a,b,c - неизвестные константы, зависящие от программной реализации алгоритма, log - логарифм по основанию 2.

2. Двухпутевые вставки

Число пересылок можно сократить примерно в 2 раза до N/8, если допустить сдвиги элементов не только вправо, но и влево. Для выходного файла резервируется место в памяти, равное 2N+1 ,где N - число элементов в исходном файле. Первый элемент пересылается в середину выходного файла. В дальнейшем элементы выходного файла сдвигаются вправо или влево в зависимости от того, в какую сторону нужно сдвигать меньше элементов. Файл из предыдущего примера будет сортироваться следующим образом.
Исх.файл.: 503 87 512 61 908 170 897 275
503 нач. состояние
°87 503 Х=87
87 503 °512 Х=512
°61 87 503 512 Х=61
61 87 503 512 °908 Х=908
61 87 °170 503 512 908 Х=170
61 87 170 503 512 °897 908 Х=897
61 87 170 °275 503 512 897 908 Х=275

Из таблицы видно, что присоединение новых элементов к выходному файлу происходит как справа, так и слева от центрального элемента 503 с возможным сдвигом вправо или влево. Время работы алгоритма t примерно оценивается формулой:
t=a*N + b*N
где a,b - неизвестные константы, зависящие от программной реализации алгоритма.

3. Вставки одновременно нескольких элементов.

Модификация метода простых вставок заключается в том, что вместо одной переменной Х можно использовать несколько переменных Х1, Х2, ... Xm, которые имеют значения элементов, подлежащих вставке в уже упорядоченную часть файла. Х1, X2, ... Xm упорядочены по возрастанию, поэтому сравнивая Xm в цикле по переменной i с элементами упорядоченной части, мы можем гарантировать, что, если очередной элемент k[i] больше Xm, то он больше и остальных элементов. Перенос элементов исходного файла вперед в цикле по i выполняется на m элементов, то есть вместо k[i+1]=k[i] в исходном алгоритме в модифицированном алгоритме записывается k[i+m]=k[i]. При нахождении k[i] такого, что он меньше Хm, Хm ставится на место k[i+m] и m уменьшается на 1. Далее цикл по i продолжается с новым m. Экономия числа переносов элементов достигается за счет переносов сразу на m элементов. Время работы алгоритма t примерно оценивается формулой:
t=a*N + b*N + c*N*logN, где a,b,c - неизвестные константы, зависящие от программной реализации алгоритма.

4. Вставки с убывающим шагом (метод Шелла)

{сортировка Шелла}
procedure Shell(var item: DataArray; count:integer);
const
t = 5;
var
i, j, k, s, m: integer;
h: array[1..t] of integer;
x: DataItem;
begin
h[1]:=9; h[2]:=5; h[3]:=3; h[4]:=2; h[5]:=1;
for m := 1 to t do
begin
k:=h[m];
s:=-k;
for i := k+1 to count do
begin
x := item[i];
j := i-k;
if s=0 then
begin
s := -k;
s := s+1;
item[s] := x;
end;
while (xbegin
item[j+k] := item[j];
j := j-k;
end;
item[j+k] := x;
end;
end;
end;

Идея алгоритма состоит в обмене элементов, расположенных не только рядом, как в алгоритме простых вставок, но и далеко друг от друга, что значительно сокращает общее число операций перемещения элементов. Для примера возьмем файл из 16 элементов. Сначала просматриваются пары с шагом 8. Это пары элементов 1-9, 2-10, 3-11, 4-12, 5-13, 6-4, 7-15, 8-16. Если значения элементов в паре не упорядочены по возрастанию, то элементы меняются местами. Назовем этот этап 8-сортировкой. Следующий этап - 4-сортировка, на котором элементы в файле делятся на четверки: 1-5-9-13, 2-6-10-14, 3-7-11-15, 4-8-12-16. Выполняется сортировка в каждой четверке. Сортировка может выполняться методом простых вставок. Следующий этап - 2-сортировка, когда элементы в файле делятся на 2 группы по 8:
1-3-5-7-9-11-13-15 и 2-4-6-8-10-12-14-16. Выполняется сортировка в каждой восьмерке. Наконец весь файл упорядочивается методом простых вставок. Поскольку дальние элементы уже переместились на свое место или находятся вблизи от него, этот этап будет значительно менее трудоемким, чем при сортировке вставками без предварительных "дальних" обменов. Для данного примера результаты представлены в следующей таблице. Исходный файл. На нем выполняется 8-сортировка.Пары для возможного обмена соединены одинарными или двойными линиями .Двойными линиями обозначены пары, в которых произошел обмен.

Файл после 8-сортировки. Линиями соединены четверки для следующего этапа.

Файл после 4-сортировки. Линиями соединены восьмерки для следующего этапа.

Файл после 2-сортировки:
154 61 503 87 512 170 612 275 653 426 765 509 897 677 908 703
Файл после окончательной сортировки (1-сортировки):
61 87 154 170 275 426 503 509 512 612 653 677 703 765 897 908
Время работы алгоритма t примерно оценивается формулой:
t=a*N**b, где a и b - неизвестные константы, зависящие от программной реализации алгоритма.

5. Вставки в связанный список

Среди общих способов улучшения алгоритма простых вставок можно рассмотреть способ, основанный на изменении структуры данных. Сортировка простыми вставками состоит из двух основных операций: - просмотра исходного файла со сравнением переменной Х с элементами K[i] файла; - вставки нового элемента путем сдвига оставшихся элементов вправо. Файл до сих пор рассматривался как линейный список и для выполнения операции вставки в нем необходимо переместить в среднем половину элементов . Известно, что для операций вставки идеально подходит связанный список, так как в этом случае вставка требует всего лишь изменения нескольких связей. Операция последовательного просмотра для связанного списка почти так же проста, как и для линейного списка. Поскольку файл всегда просматривается в одном направлении, то достаточно иметь список только с одной связью. С другой стороны связанное распределение делает невозможным бинарный поиск, поэтому приобретая преимущество в выполнении операции вставки, мы теряем по сравнению с бинарным поиском в эффективности операции просмотра и сравнения. Рассмотрим алгоритм простых вставок на связанном вперед списке.
Дан файл в виде связанного списка, каждый элемент которого содержит кроме ключа K[i] еще и указатель на следующий элемент L[i]. Кроме того есть еще дополнительная переменная L[0], содержащая указатель на последний N-й элемент файла. Указатель L[N] равен нулю, что является признаком конца списка элементов.

Упорядоченная часть файла формируется в конце списка и L[0] всегда указывает на начало упорядоченной части, в конце алгоритма - на логическое начало списка.

Алгоритм имеет следующий вид:

Переменные p и q служат указателями на текущий элемент, причем p=l[q] (q всегда на один шаг отстает от p). Если p=0, то Х - наибольший элемент и должен попасть в конец списка. Время работы алгоритма t примерно оценивается формулой:
t=a*N + b*N, где a,b - неизвестные константы, зависящие от программной реализации алгоритма.

6. Вставки в несколько связанных списков

Идея метода основывается на предположении, что ключи в исходном файле имеют значения в некотором известном диапазоне MAX и в этом диапазоне они распределены довольно равномерно. Тогда по аналогии с методом вставки в один связанный список можно организовать несколько, например, Q списков. Величина Q зависит от ожидаемого среднего количества элементов M в каждом списке то есть Q=N/M, N - количество ключей. При разработке программы нужно проанализировать зависимость времени работы метода от параметра М для различных исходных файлов и дать рекомендации по выбору оптимального значения.
Схема алгоритма имеет следующий вид. Через Q обозначено количество списков, массив B[1]...B[Q] служит для хранения указателей на начала отдельных списков. Перед началом работы алгоритма элементы массива В предполагаются равными 0.Каждый i-й элемент исходного файла содержит ключ K[i] и указатель L[i] на следующий элемент списка. Значение L[i]=0 соответствует последнему элементу в списке, указатель B[1] указывает на начало первого подсписка и одновременно на начало всего списка. Через minK обозначено минимальное значение ключа в файле, через М - среднее выбранное значение количества элементов в подсписке. d - номер текущего списка, в который должен быть вставлен элемент K[j]. Величина R=MAX/Q есть диапазон значений ключей, приходящийся на один список.

Время работы алгоритма t примерно оценивается формулой:
t=a*N + b*N, где a,b - неизвестные константы, зависящие от программной реализации алгоритма .