Визуализация алгоритма пирамидальной сортировки

1.

ВИЗУАЛИЗАЦИЯ АЛГОРИТМА
ПИРАМИДАЛЬНОЙ
СОРТИРОВКИ
Выполнил: студент гр. ИНБс-2301-01-00
Никитин Алексей Павлович

2.

ЦЕЛЬ РАБОТЫ:
Исследовать метод пирамидальной сортировки, и
разработать программу, демонстрирующую процесс
пирамидальной сортировки.
ЗАДАЧИ:
1. анализ алгоритма пирамидальной сортировки;
2. сравнение алгоритмов сортировки;
3. описание метода
4. реализация программного модуля визуализации
алгоритма пирамидальной сортировки;
5. оценка результатов.

3.

Введение в алгоритм
пирамидальной сортировки
Пирамидальная сортировка —
это алгоритм сортировки,
основанный на структуре
данных "двоичная куча". Она
использует свойства кучи для
организации данных и
выполнения сортировки. Этот
метод относится к категории
эффективных алгоритмов
сортировки, обеспечивая время
работы O(n log⁡n).

4.

Место метода в многообразии
схожих методов
Алгоритмы сортировки:
• Простые:
пузырьковая сортировка,
сортировка вставками.
• Эффективные:
пирамидальная сортировка,
быстрая сортировка,
сортировка слиянием.
Преимущества пирамидальной
сортировки:
• Стабильное время выполнения
• Отсутствие дополнительной
памяти
• Универсальность
• Устойчивость к порядку
входных данных

5.

Описание метода
Метод можно разделить на два
основных этапа:
• Строится структура данных –
пирамида
• Сортировка

6.

Первый этап –
построение пирамиды
1
Пирамида обладает тем
свойством, что в ее вершине –
находиться максимальный
элемент. Кроме того, вершина –
это элемент в структуре пирамиды
с начальным индексом. Поэтому
чтобы выбрать из пирамиды
максимальный элемент нужно
просто взять начальный элемент
из списка
2
3
4

7.

Второй этап – сортировка
После построения пирамиды можно начинать основные итерации
сортировки:
1) Вынимаем вершину пирамиды
2) На её место вставляем последний в пирамиде элемент
3) “Просеиваем” этот элемент сквозь пирамиду
И так до последней итерации, на которой из всей пирамиды
останется только вершина

8.

Второй этап – сортировка
1
2
3
4
5
6

9.

Результаты
• В результате была реализована программа, которая
визуализирует процесс пирамидальной сортировки
• Данные корректно сортируются, а сам процесс отображается
наглядно
• Было проведено несколько тестов с различными массивами
разной длины

10.

Тест №1

11.

Тест №2

12.

Тест №3

13.

Наглядный пример визуализации

14.

Верификация результатов
• Визуализация совпадает с теоретическими шагами алгоритма
• Время выполнения соответствует ожидаемой сложности
O(n log n)
• Программа успешно прошла проверку тестирования

15.

Заключение
• Была реализована программа реализующая алгоритм
пирамидальной сортировки
• Программа позволяет наглядно продемонстрировать каждый
этап алгоритма

16.

Спасибо за внимание!

17.

Библиографический список
1)Статьи по алгоритмам сортировки: Хабр : офиц. сайт. – URL:
https://habr.com/ru/articles/ (дата обращения: 08.01.2025). – Текст:
электронный
2)Пирамидальная сортировка: Википедия : офиц. сайт. – URL:
https://ru.wikipedia.org (дата обращения: 08.01.2025). – Текст:
электронный
3)Разбор метода пирамидальной сортировки: Кампус : офиц. сайт.
– URL: https://campus.epam.am/ru/blog/462 (дата обращения:
09.01.2025). – Текст: электронный