- •Саод, семестр 1
- •Абстрактные типы данных
- •Типы, структуры данных и атд
- •Время выполнения программы
- •Асимптотические отношения
- •Ограниченность показателя функции роста
- •Анализ программы на псевдоязыке
- •Абстрактный тип данных в списках
- •Реализация атд (Абстрактный тип данных). Линейный список
- •Сравнение последовательного и связанного распределения
- •Структуры данных на основе линейных списков Стек, очередь, дек
- •Реализация стека, дека и очереди на основе лсс (Линейного связанного списка)
- •Реализация дека
- •Не линейная структура данных атд дерево
- •Порядок узлов
- •Прямой, обратный и симметричный обход дерева
- •Помеченные деревья или деревья выражений
- •Сортировка
- •Классификация алгоритмов сортировки
- •Постановка задачи сортировки
- •Методы сортировок
- •Типы сортировок
- •Критерии оценки сортировок
- •Простые схемы сортировок
- •Простая вставка
- •Алгоритм Шелла
- •Быстрая сортировка Хоару
- •Оценка эффективности быстрой сортировки
- •Пирамидальная сортировка. Выбор из дерева
- •Сортировка подсчетом
- •Распределяющий подсчет
- •Класс сортировок слиянием
- •Естественное двухпутевое слияние – едс
- •Фиксированное двухпутевое слияние
- •Пример выполнения расчетов по практическому занятию
Пирамидальная сортировка. Выбор из дерева
Чтобы найти самого самого, минимального и максимального и т.д. из некоторого множества, воспользуемся алгоритмом олимпийской системы.
(олимпийская система, попарно)
4 5 20 7 6 7 14 40
20
40 20 7 14 14
7
40 14 7
40
Такая организация в виде дерева обеспечивает минимальное сравнение ключей. В корне располагается наибольший или наименьший элемент, который затем извлекается из множества. На его место претендует наибольший (наименьший) из заместителей. Замещение вакантного места происходит до листа (дерева). А лист заменяется на – ∞, т.е. наименьшее число.
В 1968 году был предложен алгоритм, в котором отсутствовал элемент – ∞, а элементы располагались внутри самой последовательности. Такой алгоритм получил название пирамидально сортировки. Пирамидой называется последовательность Ключей к1 к2 кn, в которой выполняется Kjdiv 2 >= Kj ; ,1 <= j div 2 <= N , причем ключи занумерованы в следующем порядке
1 K1
K 2 2 3 K3
2 j 4 2j+1 5 2j 6 7 2j+1
8 9 10 11 12 13 14 15
, то у узла K[j] сыновья будут с индексами 2j и 2j+1. Таким образом, в соответствии с формулой 1 пирамиды любой отец в пирамиде не превышает наименьшего из сыновей из своих сыновей, тогда корнем будет наименьший во всей последовательности. Алгоритм пирамидальной сортировки состоит из двух этапов:
1. Располагает произвольную последовательность в виде пирамиды
2. Последовательно исключаем вершину пирамиды и восстанавливаем условие j1 внутри последовательности.
На обоих этапах используется один и тот же алгоритм, называемый алгоритмом протаскивания, который заключается объединении двух уже сформированных пирамид так, чтобы прежние пирамиды оказались под деревьями в корне, а в корне расположился наименьший элемент. Последовательность из одного элемента является пирамидой, поэтому создание большой пирамиды первого этапа будем начинать с элемента, имеющего хотя бы одного сына (двигаясь, справа налево в массиве).
15 7 5 14 40 6 7 20 -2
II -2 4 5 14 7 6 7 15
40 4 5 20 7 6 7 14
1 2 3 4 5 6 7 8
40
5
10 -2 6 7
14 15 7
В отличие от Хоару, трудоемкость (быстродействие) пирамидальной сортировки не зависит от частного случая взаимного расположения элементов: даже уже упорядоченную последовательность, первый этап переразместит в виде пирамиды по трудоемкости максимально возможного количества обменов (протаскивания) элементов, которая равна высоте дерева, высота сбалансированного дерева равна двоичному логарифму.
1
Z log 2(n-i)
I N div 2
Log2(N(N-1))
0(f параметр) = const n log2N