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

Алгоритм пирамидальной сортировки предложен Уильямсом и развит Флойдом. Алгоритм основан на бинарном дереве, не требует дополнительной памяти и имеет трудоемкость O(n log₂ n).

Пусть задан массив . (1)

Пирамидой называется непустая последовательность элементов (1) вида

, (2)

для которой выполнено одно из условий .

Из определения вытекают следующие утверждения.

1). Для любой последовательности (1) последовательность является пирамидой.

2). Если последовательность (1) – пирамида, то выполняется условие . (3)

3). Если последовательность (1) – пирамида и представлена в виде бинарного дерева, то значение любого узла в нем будет не меньше значений его левого и правого потомков.

П ример 1. Последовательность чисел:

90 70 11 8 3 9 7 5 6 1 2

является пирамидой. Наглядно это видно из рисунка.

Алгоритм реализуется в два этапа.

Этап 1. Построение пирамиды

Имеем последовательность , являющейся пирамидой. Нарастим ее слева элементом . Тогда получим последовательность , (4)

которую снова преобразуем в пирамиду. Для этого "просеем" по соответствующей веточке двоичного представления (1). Для этого рассмотрим и два его потомка и . Если не меньше потомков, то вычисления прекращаем, так как (4) уже пирамида, в противном случае обмениваем значения и в соответствующих позициях дерева, а "опустившийся" элемент продолжаем просеивать тем же способом, пока (4) не станет пирамидой. Продолжаем наращивать последовательность (4) пока последовательность (1) не станет пирамидой. При этом будет выполнено условие (3). Построенная пирамида объявляется S-текущей.

Этап 2. Сортировка пирамиды

В S-текущей пирамиде первый элемент не меньше остальных. Обменяем значениями концевые элементы массива S и укоротим его справа на 1. Полученная последовательность может и не быть пирамидой. Применяя к ней процесс "просеивания" для элемента , описанный выше, преобразуем последовательность в пирамиду. Повторяя этап (n-1) раз, отсортируем массив S по не возрастанию.

Этап 1. Построение пирамиды								Этап 2. Сортировка пирамиды
23	77	12	7	44	82	16	53	7	77	23	53	44	12	16	82
23	77	12	53	44	82	16	7	16	53	23	7	44	12	77	82
23	77	82	53	44	12	16	7	12	44	23	7	16	53	77	82
23	77	82	53	44	12	16	7	12	16	23	7	44	53	77	82
82	77	23	53	44	12	16	7	7	16	12	23	44	53	77	82
								12	7	16	23	44	53	77	82
								7	12	16	23	44	53	77	82

Пример 2. Для последовательности чисел: 23 77 12 7 44 82 16 53 произвести пирамидальную сортировку, выписывая текущие последовательности в процессе выполнения алгоритма. В строках таблицы показаны значения массива после каждой реализации этапов. При этом в этапе 1 ступенчатая линия отделяет остаток последовательности от наращиваемой слева пирамиды, а в этапе 2 – сокращаемую справа последовательность перед просеиванием ее первого элемента от формируемого с конца отсортированного массива.

А

Dim S() As Integer

Const n As Integer = 8

Sub Пирамидальная_сортировка() 'Отладочный вариант

Dim j As Integer, m As Integer, k As Integer, var As String

ReDim S (1 To n): S(1)=23: S(2)=77: S(3)=12: S(4)=7: S(5)=44: S(6)=82: S(7)=16: S(8)=53

'For j = 1 To n: S(j) = Int(Rnd(Time)*100: Next j

k = n: var = "Исходные:": For j = 1 To n: var = var & " " & Str(S(j)): Next j: MsgBox var

For j = n\2 To 1 Step -1

var = "Пирамида:": For m = 1 To n: var = var & " " & Str(S(m)): Next m: MsgBox var

просеивание j, k

Next j

For k = n - 1 To 1 Step -1: m = S(1): S(1) = S(k+1): S(k+1) = m

var = "Сортировка:": For j = 1 To n: var = var & " " & Str(S(j)): Next j: MsgBox var

просеивание 1, k

Next k

var = "Отсортированные:": For j = 1 To n: var = var & " " & Str(S(j)): Next j: MsgBox var

End Sub

Sub просеивание(x As Integer, k As Integer)

Dim m As Integer, y As Integer

1: y = x + x

If y > k Then Exit Sub

If y = k Then GoTo 2

If S(y) < S(y + 1) Then y = y + 1 ' > - по не возрастанию

2: If S(x) >=S(y) Then Exit Sub '<= - по не возрастанию

m = S(x): S(x) = S(y): S(y) = m: x = y: GoTo 1

End Sub

нализ пирамидальной сортировки показывает, что для ее выполнения требуется не более 3 n log₂ n элементарных операций типа сравнения и обменов. Высокая эффективность обеспечивает популярность алгоритму. Ниже приведена программа сортировки по не убыванию одномерного массива, заполненного случайными числами.