Сортировка массивов - часть 8

каждая конечная вершина имеет высоту h или h-1;

каждая конечная вершина высоты h нажщится слева от любой конечной вершины высоты h-1;

метка любой вершины больше метки любой следующей за ней вершины.

На Рисунок 2.3 изображено несколько деревьев, из которых лишь одно Т4 является пирамидой.

Рисунок 2.3. Примеры деревьев (Т4 — пирамида)

Такая структура пирамид позволяет компактно располагать их в памяти. Например, пирамида, показанная на рисунке, в памяти будет представлена следующим массивом: 27, 9, 14, 8, 5, 11, 7, 2, 3. Оказывается, что такая последовательность чисел легко подвергается сортировке.

Таким образом, сортировка массива в соответствии с алгоритмом пирамидальной сортировки осуществляется в два этапа: на первом этапе массив преобразуется в отображение пирамиды; на втором — осуществляется собственно сортировка. Соответственно нами должны быть разработаны две процедуры для выполнения задач каждого из этих двух этапов.

ПРОЦЕДУРА insert_item_in_tree (i. mas. N) //

//insert_item_in_tree - процедура на псевдоязыке вставки элемента на свое место

в пирамиду //Вход: mas[n] - сформированная не до конца пирамида: 1 - номер добавляемого элемента

в пирамиду из mas[n] (с конца): n - длина пирамиды //Выход:действие - элемент добавлен в пирамиду.

НАЧ_ПРОГ

j:=i @@ml: k:=2*j: h-k+1

ЕСЛИ (1=<N И (mas[j]<mas[k] ИЛИ mas[j]<mas[l]) TO ПЕРЕЙТИ_НА @йп6

ИНАЧЕ ПЕРЕЙТИ_НА @@m2

КОН_ЕСЛИ @@m6: ЕСЛИ tnas[k]>mas[l] TO ПЕРЕЙТИ_НА @@т4

ИНАЧЕ ПЕРЕЙТИ_НА @@тЗ

КОН_ЕСЛИ @@т4: x:=mas[j]

mas[j]:=mas[k]

j:=k

mas[k]:=x ПЕРЕЙТИ_НА (a0ml (а@тЗ: x:=mas[j]

mas[j]:=mas[l]

mas[l]:=x

ПЕРЕЙТИ_НА @@ml*

@@m2: ЕСЛИ (k==n И mas[j]<mas[k]) TO ПЕРЕЙТИ_НА @@m7

ИНАЧЕ ПЕРЕЙТИ_НА @@m8

КОН_ЕСЛИ @@m7: x:=mas[j]

mas[j]:=mas[n]

;m-n/2 - значение, равное половине числа элементов массива mas

push si push ex

movj.si :j\»1 @@m4:

movsi.j :i->si

movax.j :k:=2*j; l:-k+l

shlax.l :j*2

movk.ax : k :=j*2

inc ax

movl.ax :l:»k+l

cmpax.m :l<m

ja @@m2

moval ,raas[si-l] ;ax:-mas[j]

Содержание Назад Вперед