Курсовой проект

Hачать построение пирамиды можно с a[k]. .a[n], k = [size/2]. Эта часть массива удовлетворяет свойству пирамиды, так как не существует индексов i, j: i = 2i+1 (или j = 2i+2)… Просто потому, что такие i, j находятся за границей массива.

Следует заметить, что неправильно говорить о том, что a[k]. .a[n] является пирамидой как самостоятельный массив. Это, вообще говоря, не верно: его элементы могут быть любыми. Свойство пирамиды сохраняется лишь в рамках исходного, основного массива a[0]. .a[n].

Далее будем расширять часть массива, обладающую столь полезным свойством, добавляя по одному элементу за шаг. Следующий элемент на каждом шаге добавления — тот, который стоит перед уже готовой частью.

Чтобы при добавлении элемента сохранялась пирамидальность, будем использовать следующую процедуру расширения пирамиды a[i+1]. .a[n] на элемент a[i] влево:

1. Смотрим на сыновей слева и справа — в массиве это a[2i+1] и a[2i+2] и выбираем наибольшего из них.

2. Если этот элемент больше a[i] - меняем его с a[i] местами и идем к шагу 2, имея в виду новое положение a[i] в массиве. Иначе конец процедуры.

Новый элемент «просеивается» сквозь пирамиду.

Ниже дана иллюстрация процесса для пирамиды из 8-и элементов:

44 55 12 42 // 94 18 06 67 Справа — часть массива, удовлетворяющая

44 55 12 // 67 94 18 06 42 свойству пирамиды,

44 55 // 18 67 94 12 06 42

44 // 94 18 67 55 12 06 42 остальные элементы добавляются

// 94 67 18 44 55 12 06 42 один за другим, справа налево.

В геометрической интерпретации ключи из начального отрезка a[size/2]. .a[n] является листьями в бинарном дереве, как изображено ниже. Один за другим остальные элементы продвигаются на свои места, и так — пока не будет построена вся пирамида.

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

Фаза 2: собственно сортировка

Итак, задача построения пирамиды из массива успешно решена. Как видно из свойств пирамиды, в корне всегда находится максимальный элемент. Отсюда вытекает алгоритм фазы 2:

1. Берем верхний элемент пирамиды a[0]. .a[n] (первый в массиве) и меняем с последним местами. Теперь «забываем» об этом элементе и далее рассматриваем массив a[0]. .a[n-1]. Для превращения его в пирамиду достаточно просеять лишь новый первый элемент.

2. Повторяем шаг 1, пока обрабатываемая часть массива не уменьшится до одного элемента.

Очевидно, в конец массива каждый раз попадает максимальный элемент из текущей пирамиды, поэтому в правой части постепенно возникает упорядоченная последовательность.

94 67 18 44 55 12 06 42 // иллюстрация 2-й фазы сортировки

67 55 44 06 42 18 12 // 94 во внутреннем представлении пирамиды

55 42 44 06 12 18 // 67 94

44 42 18 06 12 // 55 67 94

42 12 18 06 // 44 55 67 94

18 12 06 // 42 44 55 67 94

12 06 // 18 42 44 55 67 94

06 // 12 18 42 44 55 67 94

Каково быстродействие получившегося алгоритма ?

Построение пирамиды занимает O (n log n) операций, причем более точная оценка дает даже O (n) за счет того, что реальное время выполнения зависит от высоты уже созданной части пирамиды.

Вторая фаза занимает O (n log n) времени: O (n) раз берется максимум и происходит просеивание бывшего последнего элемента. Плюсом является стабильность метода: среднее число пересылок (n log n)/2, и отклонения от этого значения сравнительно малы.

Пирамидальная сортировка не использует дополнительной памяти.

Метод не является устойчивым: по ходу работы массив так «перетряхивается», что исходный порядок элементов может измениться случайным образом.

Поведение неестественно: частичная упорядоченность массива никак не учитывается.