Лучшие помощники
14 декабря 2022 20:59
496

Пирамидальная сортировка
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 элементную пирамиду. Затем берем предпоследний элемент и т.д.

Объяснение:

0
·
Хороший ответ
16 декабря 2022 20:59
Ответ:
451...................
0
16 декабря 2022 20:59
Остались вопросы?
Найти нужный