Классификация алгоритмов сортировки

Институтдистанционного образования

Специальность: 230105 Программное обеспечение вычислительной техники и автоматизированных систем

Кафедра Автоматики и компьютерных систем

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА К КУРСОВОЙ РАБОТЕ ПО ДИСЦИПЛИНЕ “Структуры и алгоритмы обработки данных на ЭВМ”

Вариант 4

Студент группы З-8091 «____» _____________ 2012 г. Д.А. Цыбулько

_______________

(подпись)

Руководитель

ассистент. «____» _____________ 2012 г. И.В.Цапко

_______________

(подпись)

Томск 2012

Введение

Целью данной курсовой работы: закрепить освоенный материал и усовершенствовать полученные навыки проектирования и разработки программных комплексов, позволяющих проиллюстрировать работу с иерархическими структурами данных.

Для достижения поставленной цели был использован компилируемый статически типизированный язык программирования общего назначения С++. Являясь одним из самых популярных языков программирования, C++ широко используется для разработки программного обеспечения. Область его применения включает создание операционных систем, разнообразных прикладных программ, драйверов устройств, приложений для встраиваемых систем, высокопроизводительных серверов, а также развлекательных приложений (например, видеоигры). Существует несколько реализаций языка C++ — как бесплатных, так и коммерческих. Инструментария языка программирования C++ достаточно для решения поставленной задачи. В качестве среды разработки была выбрана программа «Terminator» для операционной среды «Linux». Системный терминал в операционной системе «Linux» - это очень удобный и гибкий инструмент. Для большинства Windows-пользователей и начинающих осваивать «Linux», это утверждение покажется не слишком убедительным, но со временем приходит понимание. С помощью терминала можно быстро выполнить одно или несколько действий, выполнение которых в графической системе займет большее время.

Задание на курсовую работу

Отсортировать массив пирамидальной сортировкой.

Общие сведения о алгоритмах сортировки

Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.

Классификация алгоритмов сортировки

Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов.

Естественность поведения — эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет O(n log n), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:

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

В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.

Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов), т. е. в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.

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

Объём данных не позволяет им разместиться в ОЗУ.

Также алгоритмы классифицируются по:

Потребности в дополнительной памяти или её отсутствии

Потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, или отсутствии таковой.