8. Пирамидальная
пирамида сортировка	hi <= h2i
последовательность элементов	hi <= h2i+1
	h1

/\

h2	h3
/ \	/ \
h4	h5	h6	h7
/ \	/ \ / \		/ \
h8 h9 h10 h11			h12 h13 h14 h15

Фаза 1: построение пирамиды

добавляется новый элемент слева и 'просеивается' на место

1. Новый элемент Х помещаем в вершину дерева.

2.Смотрим на элемент слева и справа

– выбираем наименьший.

3. Еслиэтот элемент меньше Х - меняем их местами и идем у шагу 2. Иначе конец процедуры.

Для последовательности 06 42 12 55 94 18 44

12

55

6

12 18

55

94

42

44

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

выполнить n шагов просеивания:

1.после каждого шага очередной элемент берется с вершины пирамиды.

2.Накаждом шаге берем последний

элемент Х, верхний элемент

пирамиды помещается на его место, 3. Х просеивается на свое 'законное'.

6

12 18

55

94

42

44

Анализ

►В 1.5 раза медленнее быстрой.

►среднее число пересылок - (n*logn)/2

►Трудоемкость всегда O(nlog(n)). (наихудшего случая нет)

►Сортировка не требует дополнительной памяти.

►Поведение алгоритма неестественно

Алгоритм	Наихудший	Средний
сортировки	случай	случай
пузырек	n2	n2
выбора	n2	n2
вставок	n2	n2
слиянием	nlog2n	nlog2n
быстрая	n2	nlog n
		2

Самые эффективные методы сортировки:

►распределяющая сортировка Radix sort O(n) ►быстрая сортировка (сравнение) Quicksort ►O(nlogn)

►быстрая сортировка с составными ключами

Multiway Quicksort /MQS /

► Для прикладных задач - пирамидальная сортировка (сравнение).