Файл: Алгоритмы сортировки данных (Типы и структуры данных).pdf

Введение

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

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

Цель и задачи курсовой работы изучить и понять работу существующих на данный момент алгоритмов сортировок данных, выполнить небольшие сравнения некоторых алгоритмов и также дать оценку их эффективности (сортировка включением (метод Шелла), обменая сортировка (метод Пузырька и Шейкерная сортировка), сортировка выбором, сортировка разделением (quicksort), сортировка при помощи дерева (heapsort), пирамидальная сортировка, сортировка Хоара, сортировка слиянием, многофазная сортировка).

1. Типы и структуры данных

Типы и структуры данных представляют собой фундамент, на котором строится вся современная технология программирования. Программирования в широком смысле, включая не только непосредственно написание и отладку программ, но и проектирование программных систем разной сложности; проектирование, реализацию и использование баз данных и информационных систем и т.д. Сегодня только большие любители обходятся без использования безтиповых языков программирования (например, языков ассемблера) или неструктурированных или нетипизированных хранилищ данных во внешней памяти.

1.1. Понятие типа данных

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

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

Следующим исключительно важным свойством типа данных является инкапсуляция внутреннего представления его значений. К значению типа данных (значения констант, переменных, выражений и функций) можно обращаться только с помощью операций, предопределенных в описании этого типа. Эти операции могут быть явными (например, арифметические операции "+", "-", "?" и "/" для числовых типов) или неявными (например, операция преобразования значения целого типа к значению плавающего типа; заметим, что в некоторых языках, в частности, в Си и Си++, допускаются и явные преобразования типов).

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

Один из характерных примеров преимущества использования типизированных языков программирования представляет история операционной системы UNIX. Как известно, система первоначально была написана на языке ассемблера PDP-7. При переходе к использованию PDP-11 ОС UNIX была переписана на языке более высокого уровня B, который являлся прямым наследником безтипового языка программирования BCPL. В очень скором времени по мере роста размеров системы ее разработчикам стало понятно, что бесчисленные проверки времени выполнения очень усложняют отладку и замедляют работу системы. Это явилось исходным толчком к внедрению в язык B системы типов и созданию типизированного языка Си, опора на который обеспечила более чем 25-летнюю плодотворную жизнь системы.

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

Выделим следующие категории типов:

• Встроенные типы данных, т.е. типы, предопределенные в языке программирования или языке баз данных. Обычно в языке фиксируются внешнее представление значений этих типов (вид литеральных констант) и набор операций с описанием их семантики. Внутреннее представление и реализация операций выбираются в конкретных компиляторах и подсистемах поддержки выполнения программ.
• Под термином "уточняемый тип данных" мы понимаем возможность определения типа на основе встроенного типа данных, значения которого упорядочены. В частности, к категории уточняемых типов относится тип поддиапазона целых чисел в языках линии Паскаль.
• Категорию перечисляемых типов данных составляют явно определяемые целые типы с конечным числом именованных значений. Это очень простой и легко реализуемый механизм, часто являющийся очень полезным. 
  Замечание: использование уточняемых и перечисляемых типов порождает потребность в динамической проверке корректности значений - выхода значения за пределы явно (в случае уточняемых типов) или неявно (в случае перечисляемых типов) диапазона.
• Конструируемые типы (иногда их называют составными) обладают той особенностью, что в языке предопределены средства спецификации таких типов и некоторый набор операций, дающих возможность доступа к компонентам составных значений. Мы обсудим наиболее распространенные разновидности конструируемых типов: типы массивов, записей и множеств, а также различия в понимании этих типов в разных языках.
• Указательные типы дают возможность работы с типизированными множествами абстрактных адресов переменных, содержащих значения некоторого типа. В сильно типизированных языках (Паскаль, Модула, Ада и т.д.) работа с указателями сильно ограничена. В частности, невозможно получить значение указателя явно определенной переменной и/или применять к известным значениям указателей адресную арифметику. В языках с более слабой типизацией (например, Си/Си++) допускаются практически неограниченные манипуляции указателями.
• Вообще говоря, упоминавшиеся выше уточняемые, перечисляемые и конструируемые типы данных являются типами, определяемыми пользователями. Но эти определения не могут включать спецификацию операций над значениями типов. Допустимые операции либо предопределены, либо наследуются от некоторого определенного ранее или встроенного типа. Под термином "определяемый пользователем тип данных" (ранее был больше распространен термин "абстрактный тип данных", однако мы не будем здесь его использовать, поскольку, на наш взгляд, он не точно отражает смысл понятия) мы будем понимать возможность полного определения нового типа, включая явную или неявную спецификацию множества значений, спецификацию внутреннего представления значений типа и спецификацию набора операций над значениями определяемого типа.

Наконец, под термином "полнотиповая система" мы понимаем систему типов, в которых типы, определяемые пользователем, равноправны с предопределенными типами, т.е. можно, например, определить тип массива с элементами любого определенного типа, можно использовать определяемый пользователем тип на основе любого определенного типа и т.д.

2. Понятие алгоритма

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

Ранее в русском языке писали «алгорифм», сейчас такое написание используется редко, но, тем не менее, имеет место исключение (нормальный алгорифм Маркова).

Часто в качестве исполнителя выступает компьютер, но понятие алгоритма необязательно относится к компьютерным программам, так, например, чётко описанный рецепт приготовления блюда также является алгоритмом, в таком случае исполнителем является человек (а может быть и некоторый механизм, ткацкий станок, и пр.).

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

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

2.1. Свойства алгоритмов

Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:

• Дискретность - алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.
• Детерминированность (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных» вероятностный алгоритм становится подвидом обычного.
• Понятность - алгоритм должен включать только те команды, которые доступны исполнителю и входят в его систему команд.
• Завершаемость (конечность) - в более узком понимании алгоритма как математической функции, при правильно заданных начальных данных алгоритм должен завершать работу и выдавать результат за определённое число шагов. Дональд Кнут процедуру, которая удовлетворяет всем свойствам алгоритма, кроме, возможно, конечности, называет методом вычисления. Однако довольно часто определение алгоритма не включает завершаемость за конечное время. В этом случае алгоритм (метод вычисления) определяет частичную функцию. Для вероятностных алгоритмов завершаемость как правило означает, что алгоритм выдаёт результат с вероятностью 1 для любых правильно заданных начальных данных (то есть может в некоторых случаях не завершиться, но вероятность этого должна быть равна 0).
• Массовость (универсальность) - алгоритм должен быть применим к разным наборам начальных данных.
• Результативность - завершение алгоритма определёнными результатами.

2.2. Виды алгоритмов

Виды алгоритмов как логико-математических средств отражают указанные компоненты человеческой деятельности и тенденции, а сами алгоритмы в зависимости от цели, начальных условий задачи, путей её решения. Следует подчеркнуть принципиальную разницу между алгоритмами вычислительного характера, преобразующими некоторые входные данные в выходные (именно их формализацией являются упомянутые выше машины Тьюринга, Поста, РАМ, нормальные алгорифмы Маркова и рекурсивные функции), и интерактивными алгоритмами (уже у Тьюринга встречается C-машина, ожидающая внешнего воздействия, в отличие от классической A-машины, где все начальные данные заданы до начала вычисления и выходные данные недоступны до окончания вычисления). Последние предназначены для взаимодействия с некоторым объектом управления и призваны обеспечить корректную выдачу управляющих воздействий в зависимости от складывающейся ситуации, отражаемой поступающими от объекта управления сигналами. В некоторых случаях алгоритм управления вообще не предусматривает окончания работы (например, поддерживает бесконечный цикл ожидания событий, на которые выдается соответствующая реакция), несмотря на это, являясь полностью правильным.