Лучшие помощники
- Megamozg 2205 б
- Matalya1 1800 б
- DevAdmin 1720 б
- arkasha_bortnikov 900 б
- Dwayne_Johnson 865 б
15 декабря 2022 23:44
1058
Пирамидальная сортировка
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)Для получения на компьютере...
Составьте программу вычисления значения функции: y=5x^2-4/2x+8...