Данный метод сортировки был предложен Дж. У. Дж. Уильямсом и Р.У. Флойдом в 1964 году. Пирамидальная сортировка в некотором роде является модификацией такого подхода, как сортировка выбором, с тем лишь отличием, что минимальный (или максимальный) элемент из неотсортированной последовательности выбирается за меньшее количество операций. Для такого быстрого выбора из этой неотсортированной последовательности строится некоторая структура. Именно суть данного метода и состоит в построении такой структуры, которая называется пирамидой.
Пирамида (сортирующее дерево, двоичная куча) – двоичное дерево с упорядоченными листьями (корень дерева – наименьший или наибольший элемент). Пирамиду можно представить в виде массива. Первый элемент пирамиды является наименьшим или наибольшим, что зависит от ключа сортировки.
Просеивание – это построение новой пирамиды по следующему алгоритму: новый элемент помещается в вершину дерева, далее он перемещается ("просеивается") по пути вниз на основе сравнения с дочерними элементами. Спуск завершается, если результат сравнения с дочерними элементами соответствует ключу сортировки.
Последовательность чисел xi,xi+1,...,xn формирует пирамиду, если для всех k=i, i+1,...,n/2 выполняются неравенстваxk > x2k, xk > xi (или xk < x2k, xk < x2k+1 ). Элементы x2i и x2i+1 называются потомками элемента xi.
Массив чисел 12 10 7 5 8 7 3 является пирамидой. Такой массив удобно изображать в виде дерева. Первый элемент массива, элементы которого образуют собой пирамиду, является наибольшим (или наименьшим). Если массив представлен в видепирамиды, то массив легко отсортировать.
Алгоритм пирамидальной сортировки.
Шаг 1. Преобразовать массив в пирамиду (рис. 42.1. А).
Шаг 2. Использовать алгоритм сортировки пирамиды (рис. 42.1. В – H).
Алгоритм преобразования массива в пирамиду (построение пирамиды). Пусть дан массив x[1],x[2],...,x[n].
Шаг 1. Устанавливаем k=n/2.
Шаг 2. Перебираем элементы массива в цикле справа налево для i=k,k-1,...,1. Если неравенства xi > x2i, xi > x2i+1 не выполняются, то повторяем перестановки xi с наибольшим из потомков. Перестановки завершаются при выполнении неравенствxi > x2i, xi > x2i+1.
Алгоритм сортировки пирамиды.
Рассмотрим массив размерности n, который представляет пирамиду x[1],x[2],...,x[n].
Шаг 1. Переставляем элементы x[1] и x[n].
Шаг 2. Определяем n=n-1. Это эквивалентно тому, что в массиве из дальнейшего рассмотрения исключается элемент x[n].
Шаг 3. Рассматриваем массив x[1],x[2],...,x[n-1], который получается из исходного за счет исключения последнего элемента. Данный массив из-за перестановки элементов уже не является пирамидой. Но такой массив легко преобразовать впирамиду. Это достигается повторением перестановки значения элемента из x[1] с наибольшим из потомков. Такая перестановка продолжается до тех пор, пока элемент из x[1] не окажется на месте элемента x[i] и при этом будут выполняться неравенства x[i] > x[2i], x[i] > x[2i+1]. Тем самым определяется новое место для значения первого элемента из x[1] (рис. 1. С).
Шаг 4. Повторяем шаги 2, 3, 4 до тех пор, пока не получим n=1. Произвольный массив можно преобразовать в пирамиду (рис. 1. ).
Рис. 1.Демонстрация бинарной пирамидальной сортировки по неубыванию
Построение пирамиды, ее сортировка и "просеивание" элементов реализуются с помощью рекурсии. Базой рекурсии при этом выступает пирамида из одного элемента, а сортировка и просеивание элементов сводятся посредством декомпозиции к аналогичным действиям с пирамидой из n-1 элемента.
//Описание функции бинарной пирамидальной сортировкиvoid Binary_Pyramidal_Sort (int k,int *x){ Build_Pyramid(k/2+1,k-1,x); Sort_Piramid(k-1,x);} //Построение пирамидыvoid Build_Pyramid (int k, int r, int *x){ Sifting(k,r,x); if (k > 0) Build_Pyramid(k-1,r,x);} //Сортировка пирамидыvoid Sort_Piramid (int k, int *x){ Exchange (0,k,x); Sifting(0,k-1,x); if (k > 1) Sort_Piramid(k-1,x);} //"Просеивание" элементовvoid Sifting (int left, int right, int *x){ int q, p, h; q=2*left+1; p=q+1; if (q <= right){ if (p <= right && x[p] > x[q]) q = p; if (x[left] < x[q]){ Exchange (left, q, x); Sifting(q, right, x); } }}//процедура обмена двух элементовvoid Exchange (int i, int j, int *x){ int tmp; tmp = x[i]; x[i] = x[j]; x[j] = tmp;}
Теоретическое время работы этого алгоритма можно оценить, учитывая, что пирамидальная сортировка аналогична построениюпирамиды методом просеивания (при этом не учитывается начальное построение пирамиды). Поэтому время работы алгоритма пирамидальной сортировки без учета времени построения пирамиды будет определяться по формуле T1(n)=O(nxlog n).
Построение пирамиды занимает T2(n)=O(n) операций за счет того, что реальное время выполнения функции построения зависит от высоты уже созданной части пирамиды.
Тогда общее время сортировки (с учетом построения пирамиды) будет равно: T(n)=T1(n)+T2(n)=O(n)+O(nxlog n)=O(nxlog n).
Пирамидальная сортировка не использует дополнительной памяти. Метод не является устойчивым: по ходу работы массив так "перетряхивается", что исходный порядок элементов может измениться случайным образом. Поведение неестественно: частичная упорядоченность массива никак не учитывается. Данная сортировка на почти отсортированных массивах работает также долго, выигрыш ее получается только на больших n.
