3.2. Сортировка с помощью дерева (пирамиды)
 

Этот метод является совершенствованием метода сортировки с помощью прямого выбора, основанного на повторяющихся поисках наименьшего элемента среди n элементов, затем среди оставшихся (n - 1) элементов и т.д. Таким образом, за один проход мы находим только один элемент и никакой другой информации не запоминаем. Рассматриваемый ниже алгоритм лишен этого недостатка.

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

1) каждая конечная вершина имеет высоту h или h - 1;
2) каждая конечная вершина высоты h находится слева от любой конечной вершины высоты h - 1;
3) ключ любой вершины больше ключа следующей за ней вершины (потомка). Отсюда следует, что ключ корня является наибольшим ключом дерева.

Используя свойства 1) и 2), любой массив из n элементов мысленно можно представить в виде двоичного дерева, которое затем можно преобразовать в пирамиду.

Пусть элементы массива А имеют значения a_i, i = 1,2, ..., n: 5, 3, 7, 27, 9, 11, 14, 2, 8. Из них построим дерево следующим образом. Первый элемент (5) образует корень дерева (нулевой уровень), следующие два элемента (3, 7) образуют 1-й уровень, за тем следующие четыре элемента (27, 9, 11, 14) образуют 2-й yровень и т.д. На каждом уровне элементы массива размещаются слева направо. Тогда из исходного массива образуется следующее дерево:

Исходное дерево для построения пирамиды

Из полученного дерева пирамида строится с учетом того, ключ любой вершины пирамиды больше ключей потомков (свойство 3 двоичного дерева высоты h). Начиная с самой последней нелистовой вершины i = n mod 2, проверяем, выполняется ли : свойство. Если оно нарушено, то ключи вершины и потомка меняем местами. Затем это же проделываем с вершиной i =i – 1 и т.д., пока не достигнем корня дерева.

В нашем примере i = 9 mod 2 = 4, а₄ > а₈ и а₄ > а₉ (27 >2 и 27>8) поэтому перестановок не требуется. При i = 3 а₃ (7) меньше a₆, и a₇ (11 и 14), a a₇ > а₆, поэтому а₃ и а₇ меняем местами. В дальнейшем при i = 2 меняем местами a₂ и а₄, затем а₄ и а₉, наконец, при i = 1 последовательно меняем местами а₁ и а₂, а₂ и а₅.
j:   1   2   3   4    5   6   7   8   9
i=4:5   3   7   27   9   11   14   2   8   перестановок нет
i=3:5   3   14   27   9   11   7   2   8       a₃↔a₇, a₇ -- лист
i=2:5   27   14   3   9   11   7   2   8   a₂↔a₄, a₄ -- не лист
      5   27   14   8   9   11   7   2   3   a₄↔a₉
i=1:27   5   14   8   9   11   7   2   3   a₁↔a₂, a₂ -- не лист
      27   9   14   8   5   11   7   2   3   a₂↔a₅

В результате получили пирамиду

Таким образом, на первом этапе исходный массив преобразовали в структуру пирамиды, где а₁ — наибольший элемент.

На втором этапе, используя эту структуру, упорядочиваем элементы массива. Поменяем местами первый и последний элементы: а₁↔ а_n, n = 9 (27 ↔ 3). Получаем новое дерево, которое теперь уже не является пирамидой .

Мысленно исключим из рассмотрения последний элемент дерева a₉ = 27, получим новое дерево с (n - 1) элементами. В этом дереве только корневая вершина нарушает свойство 3 пирамиды. Последовательно переставляя ее: а₁↔ а₃ ↔ a₆. получаем новую пирамиду с вершиной а₁=14. Поменяв местами а₁=14 а_n-1 = 2 и исключив а_n-1 из рассмотрения, получаем новое дерево с (n - 2) элементами. Повторяем операции по преобразованию, пока не получим упорядоченный по возрастанию массив.

Для упорядочения массива по убыванию необходимо использовать пирамиду, обладающую измененным свойством: ключ любой вершины меньше ключа следующей за ней вершины (потомка), следовательно, ключ корня является наименьшим ключом дерева.

Пример.
/* СОРТИРОВКА ПИРАМИДОЙ ПО ВОЗРАСТАНИЮ, ВАРИАНТ 1 */
#include
#define n 9
int A[n]={5,3,7,27,9,11,14,2,8};
main()
{ void HeapSort(int A[],int nn);
void Sift(int A[],int L, int R);
int j;
printf("\n Сортировка пирамидой, вариант первый");
printf("\n Исходный массив \n\t");
for (j=0; j<n;j++)
printf("%d ",A[j]);
printf("\n Отладочная печать");
HeapSort(A,n);
printf("\n Отсортированный массив \n\t");
for (j=0; j<nn; j++)
printf("%d ",A[j]);
printf("\n");
getch(); return 0;
}
void HeapSort(int A[],int nn)
{ int L,R,x,i;
L=nn/2; R=nn-1;
/* Построение пирамиды из исходного массива */
while (L>n0)
{L=L-1;
Sift(A,L,R);
/* Отладочная печать */
printf("\nL=%d: ",L);
for (i=0;i<nnn;i++)
printf("%d ",a[i]);
/* Сортировка: пирамида=> отсортированный массив */
while (R>0)
{ x=A[0]; A[0]=A[R]; A[R]=x;
R--;
/* Отладочная печать */
printf("\nR=%d: ",R);
for (i=0;i<nnn;i++)
printf("%d ",A[i]);
Sift(A,L,R);
}
}
/* ФУНКЦИЯ ПОСТРОЕНИЯ ПИРАМИДЫ */
void Sift(int A[],int L,int R)
{ int i,j,x,k;
i=L; j=2*L+1;
x=A[L];
if ((j<nR) && (A[j]<nA[j+1]))
j++;
while (j≤nR) && (x<nA[j]))
{ k=A[i]; A[i]=A[j]; А[j]=к;
i=j;
j=2*j+1;
if ((j<nR) && (A[j]<nA[j+1]))
j++;
}
}

Сортировка пирамидой, вариант первый.
Исходный массив:
5 3 7 27 9 11 14 2 8.
Отладочная печать:
L = 3: 5 3 7 27 9 11 14 2 8
L = 2: 5 3 14 27 9 11 7 2 8
L = 1: 5 27 14 8 9 11 7 2 3