Лучшие помощники
- Megamozg 2200 б
- Matalya1 1800 б
- DevAdmin 1700 б
- arkasha_bortnikov 890 б
- Dwayne_Johnson 860 б
15 декабря 2022 23:44
1001
Пирамидальная сортировка
34 31 22 16 29 28 11 27 17 28 38 33 17 29 10
2
ответа
Ответ:
Метод пирамидальной сортировки, изобретенный Д. Уилльямсом, является улучшением традиционных сортировок с помощью дерева.
Пирамидой (кучей) называется двоичное дерево такое, что
a[i] ≤ a[2i+1];
a[i] ≤ a[2i+2].
Подробнее
Пирамидальная сортировка
a[0] — минимальный элемент пирамиды.
Общая идея пирамидальной сортировки заключается в том, что сначала строится пирамида из элементов исходного массива, а затем осуществляется сортировка элементов.
Выполнение алгоритма разбивается на два этапа.
1 этап Построение пирамиды. Определяем правую часть дерева, начиная с n/2-1 (нижний уровень дерева). Берем элемент левее этой части массива и просеиваем его сквозь пирамиду по пути, где находятся меньшие его элементы, которые одновременно поднимаются вверх; из двух возможных путей выбираете путь через меньший элемент.
Например, массив для сортировки
24, 31, 15, 20, 52, 6
Расположим элементы в виде исходной пирамиды; номер элемента правой части (6/2-1)=2 — это элемент 15.
Построение пирамиды
Результат просеивания элемента 15 через пирамиду.
Просеивание элемента через пирамиду
Следующий просеиваемый элемент – 1, равный 31.
Просеивание элемента через пирамиду
Затем – элемент 0, равный 24.
Просеивание элемента через пирамиду
Разумеется, полученный массив еще не упорядочен. Однако процедура просеивания является основой для пирамидальной сортировки. В итоге просеивания наименьший элемент оказывается на вершине пирамиды.
2 этап Сортировка на построенной пирамиде. Берем последний элемент массива в качестве текущего. Меняем верхний (наименьший) элемент массива и текущий местами. Текущий элемент (он теперь верхний) просеиваем сквозь n-1 элементную пирамиду. Затем берем предпоследний элемент и т.д.
Объяснение:
Метод пирамидальной сортировки, изобретенный Д. Уилльямсом, является улучшением традиционных сортировок с помощью дерева.
Пирамидой (кучей) называется двоичное дерево такое, что
a[i] ≤ a[2i+1];
a[i] ≤ a[2i+2].
Подробнее
Пирамидальная сортировка
a[0] — минимальный элемент пирамиды.
Общая идея пирамидальной сортировки заключается в том, что сначала строится пирамида из элементов исходного массива, а затем осуществляется сортировка элементов.
Выполнение алгоритма разбивается на два этапа.
1 этап Построение пирамиды. Определяем правую часть дерева, начиная с n/2-1 (нижний уровень дерева). Берем элемент левее этой части массива и просеиваем его сквозь пирамиду по пути, где находятся меньшие его элементы, которые одновременно поднимаются вверх; из двух возможных путей выбираете путь через меньший элемент.
Например, массив для сортировки
24, 31, 15, 20, 52, 6
Расположим элементы в виде исходной пирамиды; номер элемента правой части (6/2-1)=2 — это элемент 15.
Построение пирамиды
Результат просеивания элемента 15 через пирамиду.
Просеивание элемента через пирамиду
Следующий просеиваемый элемент – 1, равный 31.
Просеивание элемента через пирамиду
Затем – элемент 0, равный 24.
Просеивание элемента через пирамиду
Разумеется, полученный массив еще не упорядочен. Однако процедура просеивания является основой для пирамидальной сортировки. В итоге просеивания наименьший элемент оказывается на вершине пирамиды.
2 этап Сортировка на построенной пирамиде. Берем последний элемент массива в качестве текущего. Меняем верхний (наименьший) элемент массива и текущий местами. Текущий элемент (он теперь верхний) просеиваем сквозь n-1 элементную пирамиду. Затем берем предпоследний элемент и т.д.
Объяснение:
0
·
Хороший ответ
17 декабря 2022 23:44
Остались вопросы?
Еще вопросы по категории Информатика
Составьте программу, по которой компьютер десять раз запросит ввод любых чисел и в результате выведет среднее арифметическое значение введенных чисел...
Как нарисовать цилиндр в паскале при том Что ввод высоты и радиуса окружности вводится с клавиатуры(обязательно!)...
Помогите срочно...
Какое утверждение относится к функциональной философской концепции?...
Отгадайте слово , обозначающее некое понятие информатики . 1)Секретная , научная , ложная , техническая , массовая . 2)Текстовый , графический , сист...
Все предметы