Лучшие помощники
- Megamozg 2190 б
- Matalya1 1800 б
- DevAdmin 1690 б
- arkasha_bortnikov 860 б
- Dwayne_Johnson 845 б
15 декабря 2022 23:44
987
Пирамидальная сортировка
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
Остались вопросы?
Еще вопросы по категории Информатика
Сочинение по литературе написано на 5 страницах, на каждой странице 32 строки по 48 символов. Использовалась кодировка Unicode, где один символ кодиру...
1)Определите значение переменной c после выполнения следующего фрагмента программы, в котором a, b и с – переменные вещественного (действительного) ти...
Старший помощник лом оказался старательным учеником чтобы порадовать капитана Врунгеля он выучил морскую Семафорная Азбука которой каждая буква кодиру...
Объём сообщения, содержащего 2048 символов, составил 1/512 Мбайта. Каков размер алфавита, с помощью которого записано сообщение?...
На рисунке приведен фрагмент электронной таблицы. Определите, чему будет равно значение, вычисленное по следующей формуле =СУММ(B1:C4)+F2*E4-A3 СРОЧНО...
Все предметы