Внутренние сортировки. Пирамидальная сортировка

МИНОБРНАУКИ РОССИИ

 ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

(ФГБОУ ВО «ВГУ»)

Факультет прикладной математики, информатики и механики

Кафедра программного обеспечения и администрирования информационных систем

Внутренние сортировки. Пирамидальная сортировка

Курсовая работа

Направление 09.03.03 Прикладная информатика

Профиль Прикладная информатика в юриспруденции

[pic 1] 

Воронеж 2018

Аннотация

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

Содержание

Введение        4

1.        Постановка задачи        5

2.        Анализ задачи        6

2.1.        Описание пирамиды        6

2.2.        Алгоритм пирамидальной сортировки        7

2.3.        Анализ подпрограмм приложения        8

3.        Средства реализации        9

4.        Требования к программному и аппаратному обеспечению        10

5.        Интерфейс пользователя        11

6.        Реализация        14

6.1.        Структура программы        154

6.2.        Описание класса TElem        155

6.3.        Описание класса TMas        17

6.3.        Описание класса TfmMain        19

7.        План тестирования        20

Заключение        21

Список литературы        22

Приложение 1. Модуль для работы с элементом        23

Приложение 2. Модуль для работы с массивом        26

Приложение 3. Модуль главной формы        31

Введение

Одной из наиболее важных задач для программирования является задача сортировки. Под сортировкой обычно понимают перестановки элементов любой последовательности в определенном порядке. Эта задача является одной из важнейших потому, что ее целью является облегчение последующей обработки определенных данных и, в первую очередь, задачи поиска. В любой сфере деятельности, которая использует компьютер для записи, обработки и сохранения информации, все данные сохраняются в базах данных, которые также нуждаются в сортировке. Определенная упорядоченность для них очень важна, ведь пользователю намного легче работать с данными, которые имеют определенный порядок.

Принято выделять два основных вида сортировок: сортировка массивов и сортировка файлов. Эти два вида часто называют внутренней и внешней сортировкой, так как массивы располагаются во «внутренней» (оперативной) памяти, а файлы во «внешней», т.е. на запоминающих устройствах с механическим передвижением. Внутренняя сортировка работает быстрее, чем внешняя, т.к. время обращения к периферийным устройствам значительно выше, чем к оперативной памяти.

Частным случаем внутренней сортировки является пирамидальная сортировка.

Цель работы:

• описать алгоритм пирамидальной сортировки;
• реализовать программу, которая позволяет визуализировать процесс сортировки в виде массива элементов.

1. Постановка задачи

Разработать и реализовать приложение для наглядной визуализации пирамидальной сортировки в виде последовательности элементов. Приложение должно предоставлять следующие функциональные возможности:

• генерация случайной последовательности целых чисел;
• упорядочивание элементов массива с помощью пирамидальной сортировки.

1. Анализ задачи

2.1.   Описание пирамиды

В основе алгоритма пирамидальной сортировки лежит понятие пирамиды.

Пирамида представляет собой бинарное дерево, в котором каждый элемент меньше,  либо равен его родителю (при сортировке по возрастанию). То есть если имеется исходный массив с индексами от 1 до n, то соответствие между структурой пирамиды как дерева и массивом устанавливается по следующей схеме: