Размещение путем поиска места и вставки

В процедуре, реализующей сортировку вставкой с таким вариантом размещения, целесообразно использовать две вспомогательные процедуры:

1) Find_Place — определяющую подходящее место элемента массива с индексом i в предшествующей ему упорядоченной части массива;

2) Insert — которая обеспечивает перемещение в массиве элемента с индексом i на j -го позицию и смещение всех элементов с индексами от j до i—1 на одну позицию вправо.

 

 Процедура, определяющая место j элемента массива с индексом i в предшествующей ему упорядоченной части массива:

procedure Find_Place(a:arrtype; i:integer; var j:integer);

begin

a[0]:=a[i]; { Создаем "барьер" }

{Определяем значение индекса j,}

j:=i;      {идя от элемента а[i] к началу массива}

while a[j-l]>a[i] do j:=j-1

end;

 

Процедура, обеспечивающая перемещение в массиве элемента с индексом i на j-ю позицию и смещение всех элементов с индексами от j до i-1 на одну позицию вправо:

procedure Insert(var a:arrtype; i,j:integer);

var tmp,k:integer;

begin

tmp:=a[i];          {Запоминаем значение элемента a[i]}

for k:=i downto j+1 do a[k]:=a[k-1];{Элементы с индексами от i до j+1}

                                                        {смещаем вправо на 1 позицию}

a[j]:=tmp;          {Размещаем элемент a[i] на j-и позиции}

end;

С использованием этих процедур алгоритм сортировки вставками оформляется следующим образом:

procedure Insert_Sort(var a:arrtype);

var i,j:integer;

begin

for i:=2 to N do

if a[i]<a[i-l] then

  begin

     {Находим место j для элемента а[i]}

     Find_Place(а,i,j);

     {"Вставляем" элемент a[i] на это место}

     Insert(a,i,j)

end

end;

Поскольку в приведенных процедурах использован "барьер", то в основной программе необходимо учесть примечание к подобной процедуре в варианте размещения путем сравнения и обмена.

 

Учитывая, что место для очередного размещаемого элемента с одинаковой вероятностью может находиться как во второй, так и в первой половине упорядоченной части, можно в процедуре Find_Piace определять знамение индекса j, идя от начала массива. Это позволит отказаться от использования "барьера" и всех связанных с ним уточнений программы.

 

Приведем соответствующие процедуры.

procedure Find_Place(a:arrtype;i:integer;var j:integer);

begin

{Определяем значение индекса j,}

j:=1;   {идя от начала массива }

while a[j] < a[i] do j:=j+1;

end;

Данные о времени выполнения процедур сортировки тремя рассмотренными выше вариантами метода вставок приведены в табл. 3.

 

Таблица 3. Сравнительная характеристика вариантов метода вставок (продолжительность сортировки)

Вариант метода (способ размещения очередного элемента)	Количество элементов в массиве
	N=1000	n=2000	n=4000
Сравнение и обмен	1.8	7.5	30.2
Сравнение и обмен с "барьером"	1,0	3,7	15,4
Поиск места и вставка	1,4	5,7	22,5

Примечания

1. Как и в табл. 1, значение, равное 1,0, соответствует минимальному времени сортировки, остальные значения — времени, рассчитанному по отношению к минимальному.

2. В табл. 3 и в других аналогичных таблицах, приведенных ниже, представлены результаты расчетов, полученные без использования в процедурах сортировки вспомогательных процедур (в данном случае Swap, Find_Place и Insert). Такое оформление процедур сортировки приводит к сокращению времени работы программ (хотя вид процедур при этом, естественно, ухудшается).

 

Число сравнений С при вставке в готовую i последовательность составляет самой большое i-1, самое меньшее 1.

Поэтому общее число сравнений: С_min=n-1, C_max==(n²-n)/2-1.

 

Анализ сортировки простыми включениями можно улучшить, пользуясь тем, что последовательность элементов, в которую включают элемент, уже отсортирована. Поэтому место включения рациональнее найти не простым перебором, а методом деления пополам, что будет значительно быстрее.

Procedure InsertBin(var x:vector);

 var j,a,b,s,r, m:integer;

begin

 for j:=2 TO N do

begin

a:= 1; b:= j;

repeat

      s:= (a+b) div 2;

      if x[s]<x[j] then a:=s+1

      else b:=s

until a=b;

r:=x[j];

for m:=j downto a+1 do x[m]:=x[m-1];

x[a]:=r;

end;

 end; {InsertBin}

 

 

Более сложные и более эффективные методы сортировки

При решении более сложных задач приходится обрабатывать большие наборы данных. Применение простых для понимания, но медленно работающих методов сортировки, изложенных выше, становится нецелесообразно. Рассмотрим более эффективные методы сортировки.