Пирамидальная сортировка является улучшенным вариантом сортировки выбором, в которой на каждом шаге должен определяться наименьший элемент в необработанном наборе данных. Поиск наименьшего элемента можно совместить с выполнением некоторых дополнительных действий, облегчающих поиск на последующих шагах. Для этого исходный набор данных представляется особым образом – в виде так называемой пирамиды. Пирамида – это специальная разновидность двоичного дерева, построенная по особым правилам и имеющая особые свойства.
Пусть имеется исходный массив n элементов а1 а2, а3,..., аn. Расположим эти элементы в виде двоичного дерева следующего вида (здесь важен порядок следования индексов элементов):
 |
Подобное дерево называется пирамидой, если для всех элементов с индексами от 1 до n/2 выполняются следующие условия:
аi <= а2i и аi <= а2i+1
В частности, эти условия означают: а1 <= а2 и а1 <= а3; а2 <= а4 и а2 <= а5; а3 <= а6 и а3 <= а7; а4 <= а8 и а4 <= а9, и т.д.
Другими словами, в каждом элементарном поддереве значение в вершине этого поддерева меньше или равно значений в вершинах-потомках.
Пример двоичного дерева-пирамиды с 15-ю элементами:
       |          | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Это – пирамида. Соответствующий массив: 15-25-20-30-40-22-33-50-60-45-47-44-28-55-66 | Это – не пирамида (вершина 12 меньше 20) |
Такие пирамиды иногда называют минимальными, в отличие от максимальных, где правило упорядоченности прямо противоположное.
Из примера видно, что пирамида НЕ является деревом поиска, т.к. строится по другим правилам.
Можно отметить следующие полезные свойства пирамиды:
· на вершине пирамиды всегда находится наименьший элемент во всем массиве (элемент а1), элемент а2 является наименьшим для левого поддерева, элемент а3 является наименьшим для правого поддерева и т.д.
· вершины, лежащие на самом нижнем уровне пирамиды всегда образуют из себя элементарные пирамиды, поскольку у них нет никаких потомков и их сравнивать не с кем
Пирамидальная сортировка включает два больших этапа:
· представление исходного массива в виде пирамиды
· последовательные удаления минимального элемента с вершины пирамиды с заменой его другим элементом
Реализация 1 этапа включает следующие шаги:
· условно разделяем исходный массив на две половины: левую с индексами от 1 до [n/2], и правую с индексами от [n/2]+1 до n (здесь [ ] обозначает целую часть); считаем пока, что левая половина образует верхнюю часть строящейся пирамиды, а правая – нижний слой терминальных вершин
· выбираем в левой половине последний элемент (его индекс m=[n/2]), а в правой половине – его непосредственных потомков (одного или двух, но хотя бы один будет обязательно) с индексом 2m и, возможно, 2m+1
· если потомков два, то выбираем из них наименьшего
· сравниваем элемент аm с наименьшим из потомков: если он больше, то меняем эти элементы в массиве местами для получения фрагмента пирамиды; в противном случае оставляем все без изменений, поскольку эти элементы уже образуют фрагмент пирамиды
· повторяем все описанные действия последовательно для оставшихся в левой части элементов справа налево, т.е. для аm-1, аm-2, аm-3,..., а1, при этом если происходит обмен между родительской вершиной и одним из потомков, выполняется проверка для новой вершины-потомка, т.к. она может иметь своих потомков, с которыми возможно потребуется ее обменять для выполнения условия пирамиды.
Тем самым, для каждого элемента массива находится его новое расположение в массиве таким образом, чтобы выполнялись условия пирамиды. Процесс определения нужного положения элемента в массиве-пирамиде называют просеиванием элемента через пирамиду. Построение пирамиды заканчивается после просеивания первого элемента а1. Пример для 15 элементов приведен в таблице (символ ~ обозначает перестановку элементов)
| а1 | а2 | а3 | а4 | а5 | а6 | а7 | а8 | а9 | а10 | а11 | а12 | а13 | а14 | а15 | сравнение и обмен |
 33
| 33> min(20, 50), 33~20 | ||||||||||||||
| 44< min(47, 66), нет | |||||||||||||||
 30
| 30> min(15, 55), 30~15 | ||||||||||||||
 25
| 25> min(22, 60), 25~22 | ||||||||||||||
 28
| 28>min(44, 20), 28~20 | ||||||||||||||
| 28<min(33, 50), нет | |||||||||||||||
 40
| 40>min(22, 15), 40~15 | ||||||||||||||
 40
| 40>min(30, 55), 40~30 | ||||||||||||||
 45
| 45>min(15, 20), 45~15 | ||||||||||||||
 45
| 45>min(22, 30), 45~22 | ||||||||||||||
 45
| 45>min(25, 60), 45~25 | ||||||||||||||
| Пирамида построена |
В худшем случае каждый шаг в просеивании очередного элемента требует двух сравнений: сначала сравниваются два потомка текущего элемента, а потом наименьший из них сравнивается с самим элементом. В примере для построения пирамиды потребовалось 11*2=22 сравнения и 9 пересылок.
Реализация второго этапа состоит в (n-1)-кратном повторении следующих действий:
· с вершины пирамиды забирается минимальный элемент а1
· на его место в вершину пирамиды помещается последний элемент в массиве, причем индекс этого последнего элемента на каждом шаге будет уменьшаться от аn до а2
· помещенный в вершину элемент просеивается через пирамиду обычным образом, при этом он встает на свое место, а в вершину пирамиды выталкивается минимальный из оставшихся в массиве элементов
· на последнем шаге в пирамиде останется один элемент (самый большой) и сортировка будет закончена
При этом возникает вопрос – куда девать снимаемые с вершины пирамиды элементы? Можно просто помещать их в конец массива на место элемента, размещаемого в вершине. В результате на месте исходного массива создается упорядоченный ПО УБЫВАНИЮ набор данных. При необходимости, алгоритм легко можно изменить для получения возрастающих последовательностей, если вместо минимальных использовать максимальные пирамиды.
| а1 | а2 | а3 | а4 | а5 | а6 | а7 | а8 | а9 | а10 | а11 | а12 | а13 | а14 | а15 | сравнение и обмен |
| 15 = min, 15~50 | |||||||||||||||
| 50>min(22, 20), 50~20 | |||||||||||||||
| 50>min(44, 28), 50~28 | |||||||||||||||
| 50>33, 50~33 | |||||||||||||||
| 20 = min, 20~50 | |||||||||||||||
| 50>min(22, 28), 50~22 | |||||||||||||||
| 50>min(25, 30), 50~25 | |||||||||||||||
| 50>min(45, 60), 50~45 | |||||||||||||||
| 22 = min, 22~66 | |||||||||||||||
| 66>min(25, 28), 66~25 | |||||||||||||||
| 66>min(45, 30), 66~30 | |||||||||||||||
| 66>min(40, 55), 66~40 | |||||||||||||||
| 25 = min, 25~47 | |||||||||||||||
| 47>min(30, 28), 47~28 | |||||||||||||||
| 47>min(44, 33), 47~33 | |||||||||||||||
| 28 = min, 28~55 | |||||||||||||||
| 55>min(30, 33), 55~30 | |||||||||||||||
| 55>min(45, 40), 55~40 | |||||||||||||||
| 55<66, 30 = min, 30~66 | |||||||||||||||
| 66>min(40, 33), 66~33 | |||||||||||||||
| 66>min(44, 47), 66~44 | |||||||||||||||
| 33 = min, 33~60 | |||||||||||||||
| 60>min(40, 44), 60~40 | |||||||||||||||
| 60>min(45, 55), 60~45 | |||||||||||||||
| 60>50, 60~50 | |||||||||||||||
| 40 = min, 40~60 | |||||||||||||||
| 60>min(45, 44), 60~44 | |||||||||||||||
| 60>min(66, 47), 60~47 | |||||||||||||||
| 44 = min, 44~60 | |||||||||||||||
| 60>min(45, 47), 60~45 | |||||||||||||||
| 60>min(50, 55), 60~50 | |||||||||||||||
| 45 = min, 45~66 | |||||||||||||||
| 66>min(50, 47), 66~47 | |||||||||||||||
| 47 = min, 47~55 | |||||||||||||||
| 55>min(50, 66), 55~50 | |||||||||||||||
| 55<60, 50 = min, 50~60 | |||||||||||||||
| 60>min(55, 66), 60~55 | |||||||||||||||
| 55 = min, 55~66 | |||||||||||||||
| 66>60, 66~60 | |||||||||||||||
| 60 = min, 60~66 | |||||||||||||||
| сортировка закончена |
В данном примере выполнено 51 сравнение и 40 пересылок, что вместе с этапом построения пирамиды дает 73 сравнения и 49 пересылок.
В целом, данный метод с точки зрения трудоемкости имеет типичное для улучшенных методов поведение: довольно высокая трудоемкость для небольших n, но с ростом n эффективность метода растет. При больших n метод в среднем немного уступает быстрой сортировке и имеет оценку порядка (n*log 2 n)/2. Единственное, в чем он превосходит быструю сортировку, так это поведение на аномальных входных данных, когда быстрая сортировка перестает быть “быстрой”, а пирамидальная сохраняет свою трудоемкость порядка O(n*log 2 n). В [4] указывается, что пирамидальную сортировку выгодно использовать в том случае, когда требуется не провести полную сортировку большого набора данных, а лишь найти несколько (причем – немного) первых наименьших элементов.
Необходимо отметить, что понятие пирамидального дерева имеет и самостоятельное значение, и часто используется для решения других задач, не связанных с сортировкой массивов, например – для эффективной реализации приоритетных очередей [4].
В заключение рассмотрим вопросы программной реализации пирамидальной сортировки. Поскольку оба этапа алгоритма основаны на повторении одинаковых действий по просеиванию элементов, удобно оформить просеивание в виде вспомогательной процедуры.
Procedure Sito (al, ar: word);
var i, j: word;
x: <описание элемента массива>;
Begin
i:= al; j:= 2*al; x:= mas[al];
if (j < ar) and (mas[j + 1] < mas [j]) then j:= j + 1;
while (j <=ar) and (mas[j] < x) do
Begin
mas [i]:= mas [j]; i:=j; j:=2*j;
if (j < ar) and (mas[j + 1] < mas[j]) then j:= j + 1;
end;
mas[i]:= x;
end;
Тогда основная программа будет лишь включать два последовательных цикла – один для построения пирамиды, второй – для снятия с вершины наименьшего элемента и просеивания нового вершинного элемента.
left:= (n div 2) + 1; right:= n;
{определение границ правой половины массива}
while left > 1 do
begin {цикл построения пирамиды}
left:= left – 1; Sito (left, right);
end;
while right > 1 do (цикл сортировки}
Begin
temp:= mas[1]; mas[1]:= mas[right]; mas[right]:= temp;
right:= right – 1; Sito (left, right);
end;
Практическое задание
Добавить в ранее созданную программу с простейшими методами сортировки подпрограммы, реализующие все три улучшенных метода сортировки массивов.
Каждый метод реализуется своей подпрограммой, добавляемой в основную программу по мере разработки. Каждый исходный массив должен обрабатываться всеми программами сортировки с подсчетом и выводом фактического числа выполненных сравнений и пересылок. После завершения разработки программы необходимо выполнить всеми методами сортировку нескольких массивов с разным числом элементов (10, 100, 1.000, 10.000) и провести сравнительный анализ эффективности рассматриваемых методов.
Главная программа должна реализовать диалог с пользователем для выбора метода сортировки.
Рекомендации по реализации метода Шелла. Для хранения шагов группировки можно ввести вспомогательный массив. После генерации исходного массива надо организовать цикл, в котором запросить и ввести количество шагов и величины самих шагов. Выполнить сортировку исходного массива для нескольких разных наборов шагов и найти среди этих наборов наилучший по числу выполненных сравнений.
2.5. Контрольные вопросы по теме
1. В чем состоит суть сортировки методом Шелла?
2. За счет чего метод Шелла дает лучшие показатели по сравнению с простейшими методами?
3. Приведите практический пример сортировки массива методом Шелла.
4. Какой фактор оказывает наибольшее влияние на эффективность сортировки методом Шелла?
5. Какие последовательности шагов группировки рекомендуются для практического использования в методе Шелла?
6. Как программно реализуется сортировка методом Шелла?
7. В чем состоит суть метода быстрой сортировки?
8. За счет чего метод быстрой сортировки дает лучшие показатели по сравнению с простейшими методами?
9. Что такое опорный элемент в методе быстрой сортировки и как он используется?
10. Приведите практический пример быстрой сортировки массива.
11. Что можно сказать о применимости метода быстрой сортировки с точки зрения его эффективности?
12. Какой фактор оказывает решающее влияние на эффективность метода быстрой сортировки?
13. Почему выбор серединного элемента в качестве опорного в методе быстрой сортировки может резко ухудшать эффективность метода?
14. Какое правило выбора опорного элемента в методе быстрой сортировки является наилучшим и почему его сложно использовать?
15. Какое простое правило выбора опорного элемента в методе быстрой сортировки рекомендуется использовать на практике?
16. Какие усовершенствования имеет базовый алгоритм метода быстрой сортировки?
17. Почему быстрая сортировка проще всего программно реализуется с помощью рекурсии?
18. Как программно реализуется рекурсивный вариант метода быстрой сортировки?
19. Какие особенности имеет не рекурсивная программная реализация метода быстрой сортировки?
20. В чем состоит суть метода пирамидальной сортировки?
21. Какой набор данных имеет пирамидальную организацию?
22. Чем отличаются друг от друга дерево поиска и пирамидальное дерево?
23. Приведите пример пирамидального дерева с целочисленными ключами.
24. Какие полезные свойства имеет пирамидальное дерево?
25. Какие шаги выполняются при построении пирамидального дерева?
26. Что такое просеивание элемента через пирамиду?
27. Приведите практический пример построения пирамидального дерева.
28. Какие шаги выполняются на втором этапе пирамидальной сортировки?
29. Приведите практический пример реализации второго этапа пирамидальной сортировки.
30. Что можно сказать о трудоемкости метода пирамидальной сортировки?
Тема 3. Специальные методы сортировки