Просеивание

Пирамидальная сортировка

Попытаемся теперь усовершенствовать другой рассмотренный выше простой алгоритм: сортировку простым выбором ПрВыб.

Р. Флойд предложил перестроить линейный массив в пирамиду - своеобразное бинарное дерево, - а затем искать минимум только среди тех элементов, которые находятся непосредственно "под" текущим вставляемым.

Для начала необходимо перестроить исходный массив так, чтобы он превратился в пирамиду, где каждый элемент "опирается" на два меньших. Этот процесс назвали просеиванием, потому что он очень напоминает процесс разделения некоторой смеси (камней, монет, т.п.) на фракции в соответствии с размерам частиц: на нескольких грохотах3) последовательно задерживаются сначала крупные, а затем все более мелкие частицы.

Итак, будем рассматривать наш линейный массив как пирамидальную структуру:

a[1]

a[2] a[3]

a[4] a[5] a[6] a[7]

a[8] a[9] a[10] a[11] a[12]

Видно, что любой элемент a[i] (1<=i<=N div 2) "опирается" на элементы a[2*i] и a[2*i+1]. И в каждой такой тройке максимальный элемент должен находится "сверху". Конечно, исходный массив может и не удовлетворять этому свойству, поэтому его потребуется немного перестроить.

Начнем процесс просеивания "снизу". Половина элементов (с ((N div 2)+1)-го по N-й) являются основанием пирамиды, их просеивать не нужно. А для всех остальных элементов (двигаясь от конца массива к началу) мы будем проверять тройки a[i], a[2*i] и a[2*i+1] и перемещать максимум "наверх" - в элемент a[i].

При этом, если в результате одного перемещения нарушается пирамидальность в другой (ниже лежащей) тройке элементов, там снова необходимо "навести порядок" - и так до самого "низа" пирамиды:

for i:= (N div 2)downto 1 do

begin j:= i;

while j<=(N div 2) do

begin k:= 2*j;

if (k+1<=N) and (a[k]<a[k+1])

then k:= k+1;

if a[k]>a[j]

then begin x:= a[j];

a[j]:= a[k];

a[k]:= x;

j:= k

end

else break

end

end;

Дата добавления: 2013-12-13