Билет №5. Метод вставок.
Метод вставки
Метод основывается на следующем: считается, что перед рассмотрением записи R[j] предыдущие записи R[1],R[2],...,R[j-1] уже упорядочены, и R[j] вставляется в соответствующее место. Сортировка таблицы начинается со второй записи. Ее ключ сравнивается с ключом первой записи, и, если упорядоченность нарушена, то записи R[1] и R[2] переставляются. Затем ключ записи R[3] сравнивается с ключами записей R[2] и R[1]. На j - м шаге К[j] сравнивается по очереди сK[j-1],K[j-2],...(K[1]<=K[2]<=...<=K[j-1]) до тех пор, пока выполняется условие K[j]<K[i] (i=j-1,j-2,...) или достигнут левый конец упорядоченной подтаблицы (i=1, K[j]<K[1]). Выполнение условия K[j]>=K[i] означает, что запись R[j] нужно вставить между R[i] и R[i+1]. Тогда записи R[i+1], R[i+2],...,R[j-1] сдвигаются на одну позицию, и запись R[j] помещается в позицию i+1. Операции сравнения и перемещения записей удобно совмещать,перемежая их друг с другом (этот способ называется "просеиванием"). Ниже показано выполнение j-го шага сортировки ( с "просеиванием" ). 5 8 10 14 6 2 11 ¦ j=5, i=4, 6 < 14 <-~~ ¦ 5 8 10 6 14 2 11 ¦ i=3, 6 < 10 <-~~ ¦ 5 8 6 10 14 2 11 ¦ i=2, 6 < 8 <-~~ ¦ 5 6 8 10 14 2 11 ¦ i=1, 6 > 5
Количество операций сравнения для метода вставки определяется по формуле n * (n - 1) C = ------------ 4 При достаточно большом числе элементов в сортируемой таблице можно принять C = n**2/4 . Максимальное количество перестановок при использовании этого метода примерно равно n**2/4 Метод вставки обычно используется тогда, когда записи вносятся в упорядоченную таблицу. Новая запись должна быть вставлена в таблицу таким образом, чтобы существующая упорядоченность не нарушалась.
Модифицированный метод вставки ( бинарное включение ) Метод прямого включения можно улучшить,если вставлять очередной элемент таблицы в упорядоченную подтаблицу с помощью метода бинарного (дихотомического,двоичного,логарифмического) поиска. j-й шаг сортировки: 5 6 8 10 14 18 9 2 ¦ i = 6/2 = 3; 9 > 8 ~~~~~~ ~~~~~~~~~ ~~ ¦ отбрасывается рассматривается ¦ --¬ ¦ . . . 10 14 18 9 2 ¦ i = (4+6)/2 = 5; ~~ ~~~~~ ¦ 9 < 14 рассм. отбрас. ¦ ¦ . . . 9 10 14 18 2 ¦ i = 4; 9 < 10
Методы вставки. Алгоритм простых вставок.
{сортировка вставкой}
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 (x<item[j]) and (j>0) 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 - неизвестные константы, зависящие от программной реализации алгоритма.