Пирамидальная сортировка имеет эффективность O(n log2n). Алгоритм использует тот факт, что наименьший элемент находится в корне (индекс 0) и что метод Delete возвращает это значение.
Для осуществления пирамидальной сортировки массива A объявите объект типа Heap с массивом A в качестве параметра. Конструктор преобразует A в пирамиду. Сортировка осуществляется последовательным удалением A[0] и вставкой его в A[N-1], A[N-2], ..., A[1]. Вспомните, что с момента исключения элемента из пирамиды элемент больше не является частью пирамиды, а элемент, бывший до этого хвостовым, замещает корневой. Мы имеем возможность скопировать удаленный элемент в освободившуюся позицию массива. В процессе пирамидальной сортировки очередные наименьшие элементы удаляются и последовательно запоминаются в хвостовой части массива. Таким образом, массив A сортируется по убыванию.
Пирамидальная сортировка пятиэлементного массива A осуществляется посредством следующих действий:
int A[] = {50, 20,75, 35, 25}
Исходная пирамида
Удалить 20 и запомнить в A[4] Удалить 25 и запомнить в A[3]
Удалить 35 и запомнить в A[2] Удалить 50 и запомнить в A[1]
Поскольку единственный оставшийся элемент 75 является корнем, массив отсортирован: A = 75 50 35 25 20.
Ниже приводится реализация алгоритма пирамидальной сортировки.
Функция HeapSort
#include "heap.h" // класс Heap
template <class T> // отсортировать массив A по убыванию
void HeapSort (T A[], int n)
{
// преобразуем A в пирамиду
Heap<T> H(A, n);
T elt;
// цикл заполнения элементов A[n-1] ... A[1]
for (int i=n-1; i>=1; i--)
{
// исключить наименьший элемент из пирамиды
// и запомнить его в A[i]
elt = H.Delete();
A[i] = elt;
}
}
Вычислительная эффективность пирамидальной сортировки. Массив, содержащий n элементов, соответствует законченному бинарному дереву глубиной k = log2n. Начальная фаза преобразования массива в пирамиду требует n/2 операций FilterDown. Каждой из них требуется не более k сравнений. На второй фазе сортировки операция FilterDown выполняется n-1 раз. В худшем случае она требует k сравнений. Объединив обе фазы, получим худший случай сложности пирамидальной сортировки:
k * n/2 + k * (n - 1) = k * (3n/2 - 1) = log2n * (3n/2 - 1)
Итак, сложность алгоритма имеет порядок O(n log2n).
Пирамидальная сортировка не требует никакой дополнительной памяти, поскольку производится на месте. Турнирная сортировка является алгоритмом порядка O(n log2n), но требует создания последовательно представляемого массивом дерева из 2(k+1) узлов, где k наименьшее целое, при котором n < 2k. Некоторые O(n log2n) сложные сортировки дают O(n2) в худшем случае. Пирамидальная сортировка всегда имеет сложность O(n log2n) независимо от исходного распределения данных.
Сравнение методов сортировки
Массив A, содержащий 2000 случайных целых чисел, сортируется с помощью функции HeapSort (пирамидальная сортировка). В целях сравнения массивы B и C заполняются теми же элементами и сортируются с помощью функций TournamentSort (турнирная сортировка) и ExchangeSort (обменная сортировка). Функция обменной сортировки ExchangeSort:
// поменять значения двух переменных целого типа х и у
void Swap(int & х, int & у)
{
int temp == х; // сохранить первоначальное значение х
х = у; // заменить х на у
у = temp; // присвоить переменной у
}
// сортировать целый массив в возрастающем порядке
void ExchangeSort(int a[], int n)
{
int i, j;
// реализовать n — 1 проходов.
//Найти правильные значения в а[],...,a[n-2].
for(i = 0; i < n-1; i++)
// поместить минимум из a[n+l]...а[п-1] в a[i]
for(j = i+1; j < n; j++)
// поменять местами, если a[i] > a[j]
if (a[i] > a[j])
Swap(a[i], a[j]) ;
}
Сортировки хронометрируются функцией TickCount, которая возвращает число 1/60 долей секунды, прошедших с момента старта системы. Сортировка обменом, имеющая сложность O(n2), позволит четко представить быстродействие турнирного и пирамидального методов, имеющих сложность O(n log2n). Функция PrintFirst_Last распечатывает первые и последние пять элементов массива. Код этой функции не включен в листинг программы.
#include <iostream.h>
#include "random.h"
#include "toursort.h"
#include "heapsort.h"
#include "ticks.h"
enum SortType {heap, tournament, exchange};
void TimeSort (int *A, int n, char *sortName, SortType sort)
{
long tcount;
//TickCount системная функция. Возвращает число 1/60 долей
