Контрольная работа: Сравнительное исследование эффективности методов сортировки Флойда и Шелла

5)tmp:= q,

6)перейти к п. 1.

Этот алгоритм в применении к нашему массиву а реализован в этом коде подпрограммы, который выполняет просеивания в пирамиду с максимальным индексом R:

begin

k:=2*t;

if k>i then t:=0

else

begin

if k<i then

if Arr[k]>Arr [k-1] then inc(k); Kol_sravFloud:= Kol_sravFloud +1;

if Arr [t-1]>=Arr [k-1] then begin t:=0; Kol_sravFloud:= Kol_sravFloud +1

end else

begin

Kol_sravFloud:= Kol_sravFloud +1;

Tmp:=Arr [k-1];

Arr [k-1]:=Arr [t-1];

Arr [t-1]:=Tmp; // Переустановка Элементов

t:=k;

Kol_PerFloud:= Kol_PerFloud +1;

end;

Код учитывает индексацию вектора а от нуля.

Теперь рассмотрим процесс создания пирамиды из массива а[0], а[1],…, a[Highlndex]. Элементы этого массива индексируются от 0, а пирамида от 1. Ясно, что элементы a [N/2], a [N/2+1],…, a[Highlndex] уже образуют пирамиду, поскольку не существует двух индексов i (i= N/2+1, N/2+2, …) и j, таких, что, j=2i (или j=2i+l). Эти элементы составляют последовательность, которую можно рассматривать как листья соответствующего двоичного дерева. Теперь пирамида расширяется влево: на каждом шаге добавляется новый элемент и при помощи просеивания помещается на соответствующее место. Этот процесс иллюстрируется следующим примером.

Процесс построения пирамиды

44 55 12 42 94 18 06 67

44 55 12 42 94 18 06 67

44 55 06 42 94 18 12 67

44 42 06 55 94 18 12 67

06 42 12 55 94 18 44 67

Примечание – жирным шрифтом отмечены ключи, образующие пирамиду на текущем шаге ее построения