Анализ HeapSort
На первый взгляд вовсе не очевидно, что такой метод сортировки даёт хорошие результаты. Ведь в конце концов большие элементы, прежде чем попадут на своё место в правой части, сначала сдвигаются влево. И действительно, процедуру не рекомендуется применять для небольшого количества элементов.
В худшем случае нужно n/2 сдвигающих шагов, они сдвигают элементы на log2(n/2), log2(n/2-1), ..., log2(n-1) позиций (двоичные(!) логарифмы округляются везде до следующего меньшего целого). Следовательно, фаза сортировки требует n-1 сдвигов с самое большое log2(n-1), log2(n-2), ..., 1 перемещениями. Кроме того, нужно ещё n-1 перемещений для просачивания сдвинутого элемента на некоторое расстояние вправо. Эти соображения показывают, что даже в самом плохом из возможных случаев пирамидальная сортировка потребует n * log2 n шагов. Великолепная производительность в таких плохих случаях – одно из привлекательных свойств HeapSort.
Совсем не ясно, когда ожидать наихудшей (или наилучшей) производительности. Но вообще-то кажется, что HeapSort хорошо работает на последовательностях, в которых элементы более или менее отсортированы в обратном порядке. Поэтому её поведение несколько неестественно. Если мы имеем дело с обратным порядком, то фаза порождения пирамиды не требует каких-либо перемещений. Среднее число перемещений приблизительно равно n/2 * log2 n, причём отклонения от этого значения относительно невелики.
Интерфейс программы
В соответствии с поставленной задачей, программа имеет интуитивно понятный интерфейс. Главное окно программы при её запуске распахивается на весь экран. Оно имеет меню, все команды которого понятны человеку, имеющему опыт работы с Windows. Два дочерние окна полностью занимают его рабочую область.
Одно из дочерних окон называется "Описание" и в нём отображается содержимое находящегося в каталоге программы файла describe.txt. Данный файл содержит описание рассматриваемого алгоритма. В комплекте поставки программы имеются 2 файла описания алгоритма – по Вирту и по Романовскому. Окно оснащено двумя линейками скроллинга, которые дают возможность просматривать большие тексты.
Второе дочернее окно называется "Визуализатор". В этом окне имеются:
Элементы управления – нажимающиеся кнопки. Динамическое изображение массива в виде ленты. Динамическое изображение массива в виде двоичного дерева (в соответствии с алгоритмом). Инструкции, появляющиеся и исчезающие по мере протекания процесса.Предусмотрены 3 нажимающиеся кнопки. Кнопка "сбросить" служит для немедленного прекращения процесса визуализации. Кнопка "шаг" выполняет один очередной шаг (итерацию) алгоритма. Кнопка "авто" запускает итерации алгоритма друг за другом с определённой задержкой. Задержка задаётся в файле инициализации(см. далее).
Файл инициализации располагается в каталоге программы и называется visual.ini. Файл имеет 2 секции: [Visual] и [Font]. Секция [Visual] содержит следующие параметры. Параметр Number имеет значение количества элементов в сортируемом массиве. Параметр Delay имеет значение величины задержки (промежутка времени между итерациями при нажатии на кнопку "авто"). Секция [Font] имеет 3 параметра. Параметры Width, Height и Font имеют значения соответственно ширины, высоты и названия шрифта, которым выводится текст описания алгоритма в соответствующем окне.
Литература
1. Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1989.
2. Кнут Д. Е. Искусство программирования для ЭВМ, том 3. Сортировка и поиск. – М.: Мир, 1978.
3. Романовский И. В. Дискретный анализ. – СПб.: "Невский диалект", 1999.
Описание алгоритма
Метод сортировки с помощью прямого выбора основан на повторяющихся поисках наименьшего ключа среди n элементов, среди оставшихся n-1 элементов и т. д. Сумма первых n-1 целых равна
Второй этап сортировки – спуск вдоль пути, отмеченного наименьшим элементом, и исключение его из дерева путём замены либо на пустой элемент(дырку) в самом низу, либо на элемент из соседней ветви в промежуточных вершинах. Элемент, передвинувшийся в корень дерева, вновь будет наименьшим(теперь уже вторым) ключом, и его можно исключить. После n таких шагов дерево станет пустым (то есть в нём останутся только дырки), и процесс сортировки заканчивается. Обратим внимание – на каждом из n шагов выбора требуется только log2 n cравнений. Поэтому на весь процесс понадобится порядка n log2 n элементарных операций плюс ещё n шагов на построение дерева. Это весьма существенное улучшение не только прямого метода, требующего n2 шагов, но и даже метода Шелла, где нужно n1,2 шага. Естественно, сохранение дополнительной информации делает задачу более изощрённой, поэтому в сортировке по дереву каждый отдельный шаг усложняется. Ведь в конце концов для сохранения избыточной информации, получаемой при начальном проходе, создаётся некоторая древообразная структура. Наша следующая задача – найти приёмы эффективной организации этой информации.
Конечно, хотелось бы, в частности, избавиться от дырок, которыми в конечном итоге будет заполнено всё дерево и которые порождают много ненужных сравнений. Кроме того, надо было бы поискать такое представление дерева из n элементов, которое требует лишь n единиц памяти, а не 2n-1, как это было раньше.
Этих целей действительно удалось добиться в рассматриваемом методе Heapsort
(пирамидальная сортировка), изобретённом Д. Уилльямсом, где было получено, очевидно, существенное улучшение традиционных сортировок с помощью деревьев. Пирамида определяется как последовательность ключей h[L], h[L+1], ..., h[R], такая, что
h[i] <= h[2*i] and h[i] <= h[2*i+1] для i = L ... R/2. (1)
Если любое двоичное дерево рассматривать как массив, то можно говорить, что h[1] – наименьший элемент данного массива. Предположим, есть некоторая пирамида с заданными элементами h[L+1], ..., h[R] для некоторых значений L и R и нужно добавить новый элемент х, образуя расширенную пирамиду h[L], ..., h[R]. Новая пирамида получается так: сначала х ставится наверх древовидной структуры, а затем он постепенно опускается вниз каждый раз по направлению наименьшего из примыкающих к нему элементов, а сам этот элемент передвигается вверх. Как нетрудно заметить, данный способ не нарушает условий (1), определяющих пирамиду.
Р. Флойдом был предложен некий "лаконичный" способ построения пирамиды "на том же месте". Его процедура сдвига представлена как листинг 1. Здесь h[1]...h[n] – некий массив, причём h[m]...h[n] (m = n div 2 + 1) уже образуют пирамиду, поскольку индексов i, j, удовлетворяющих соотношениям j = 2i и j = 2i+1 просто не существует. То есть эти элементы образуют нижний слой соответствующего двоичного дерева, для них никакой упорядоченности не требуется.
Листинг 1. Sift.
procedure Swap(var a, b : item);
{ меняет значения переменных}
var c : item;
begin
c := a;
a := b;
b := c;
end;
procedure sift(L, R : index);
var
i, j : index;
x : item;
begin
i := L;
j := 2*L;
x := a[L];
if (j < R) and (a[j+1] < a[j]) then
j := j + 1;
while (j <= R) and (a[j] < x) do
begin
Swap(a[i], a[j]);
i := j;
j := 2 * j;
if (j < R) and (a[j+1] < a[j]) then
j := j + 1;
end;
end;
Теперь пирамида расширяется влево; каждый раз добавляется и сдвигами ставится в надлежащую позицию новый элемент. Следовательно, процесс формирования пирамиды из n элементов h[1]...h[n] на том же самом месте описывается так:
L := (n div 2) + 1;
while L > 1 do
begin
L := L - 1;
sift(L, n);
end;
Для того, чтобы получиь не только частичную, но и полную упорядоченность среди элементов, нужно проделать n сдвигающих шагов, причём после каждого шага на вершину дерева выталкивается очередной(наименьший) элемент. И вновь возникает вопрос: где хранить "всплывающие" верхние элементы и можно ли или нельзя проводить обращение на том же месте? Существует, конечно, такой выход: каждый раз брать последнюю компоненту пирамиды (скажем, это будет х), прятать верхний элемент в освободившемся теперь месте, а х сдвигать в нужное место. Процесс описывается с помощью процедуры sift таким образом:
R := n;
while R > 1 do
begin
Swap(a[1], a[R]);
R := R - 1;
sift(1, R);
end;
Однако получившийся порядок фактически является обратным. Это можно легко исправить, изменив направление "упорядочивающего отношения" в процедуре sift. В конце концов получаем процедуру HeapSort
Листинг 2. HeapSort
procedure HeapSort;
var
L, R : index;
x : item;
procedure Swap(var a, b : item);
{ меняет значения переменных}
var c : item;
begin
c := a;
a := b;
b := c;
end;
procedure sift(L, R : index);
var
i, j : index;
x : item;
begin
i := j;
j := 2 * j;
if (j < R) and (a[j+1] > a[j]) then
j := j + 1;
end;
end;
begin
L := (n div 2) + 1;
R := n;
while (L > 1) do
begin
L := L - 1;
sift(L, R);
end;
while R > 1 do
begin
Swap(a[1], a[R]);
R := R - 1;
sift(L, R);
end;
end;
Постановка задачи
Написать программу, представляющую в удобной для восприятия форме механизм работы алгоритма пирамидальной сортировки, – визуализатор данного алгоритма. Программа должна иметь современный интуитивно понятный интерфейс и, следовательно, должна быть написана в среде Windows.
Системные требования
Для использования данной программы необходимо иметь: процессор 486 DX2-66, 2 мегабайта оперативной памяти, 400 килобайт на жёстком диске, Windows '95.
