Лучшие помощники
- Megamozg 2205 б
- Matalya1 1800 б
- DevAdmin 1720 б
- arkasha_bortnikov 900 б
- Dwayne_Johnson 870 б
15 декабря 2022 23:44
1115
Пирамидальная сортировка
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
Остались вопросы?
Еще вопросы по категории Информатика
Каждый переданный кодовый символ может принят ошибочно с фиксированным вероятностью P Решать задачку по этой формуле P(zj/Uk) = P/N-1 при j≠k I-p при...
Клавиатурный шпион – это:...
Считая что каждый символ кодируется 1 байтом , оцените информационный объем фразы в кодировке Aseii Потемнело, нахмурились небо, побежали черные гроз...
ПОМОГИТЕ ПОЖАЛУЙСТА 1.Составить таблицы сложения и умножения в двоичной системе счисления и выполнить вычисления: а) 1110 + 101; б) 10101 - 11; в) 10...
Положение курсора в слове с ошибкой отмечено чертой: ДИАГРАММ|МА. Чтобы исправить ошибку, следует нажать клавишу: а) Delete б) Backspace в) Delete и...