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

ВВЕДЕНИЕ

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

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

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

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

Для решения поставленной цели были поставлены следующие задачи:

- изучить теоретические основы алгоритмов сортировки данных;

- рассмотреть историю алгоритмов сортировки данных;

- провести анализ основных алгоритмов сортировки данных.

Объектом работы является алгоритмизация в программировании.

Предметом работы являются алгоритмы сортировки данных.

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

Глава 1. Теоретические основы алгоритмов сортировки данных

1.1. Понятие и оценка алгоритмов сортировки данных

Алгоритмом сортировки называется алгоритм для упорядочения некоторого множества элементов. Обычно под алгоритмом сортировки подразумевают алгоритм упорядочивания множества элементов по возрастанию или убыванию [4, с. 229].

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

В алгоритмах сортировки лишь часть данных используется в качестве ключа сортировки. Ключом сортировки называется атрибут (или несколько атрибутов), по значению которого определяется порядок элементов. Таким образом, при написании алгоритмов сортировок массивов следует учесть, что ключ полностью или частично совпадает с данными.

Практически каждый алгоритм сортировки можно разбить на 3 части:

- сравнение, определяющее упорядоченность пары элементов;

- перестановку, меняющую местами пару элементов;

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

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

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

Наиболее подробно рассмотрим классификацию алгоритмов сортировки по сфере применения. В данном случае основные типы упорядочивания делятся следующим образом.

- Внутренняя сортировка – это алгоритм сортировки, который в процессе упорядочивания данных использует только оперативную память (ОЗУ) компьютера. То есть оперативной памяти достаточно для помещения в нее сортируемого массива данных с произвольным доступом к любой ячейке и собственно для выполнения алгоритма. Внутренняя сортировка применяется во всех случаях, за исключением однопроходного считывания данных и однопроходной записи отсортированных данных. В зависимости от конкретного алгоритма и его реализации данные могут сортироваться в той же области памяти, либо использовать дополнительную оперативную память.

- Внешняя сортировка – это алгоритм сортировки, который при проведении упорядочивания данных использует внешнюю память, как правило, жесткие диски. Внешняя сортировка разработана для обработки больших списков данных, которые не помещаются в оперативную память. Обращение к различным носителям накладывает некоторые дополнительные ограничения на данный алгоритм: доступ к носителю осуществляется последовательным образом, то есть в каждый момент времени можно считать или записать только элемент, следующий за текущим; объем данных не позволяет им разместиться в ОЗУ.

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

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

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

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

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

Устойчивость (stability) - устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами [3, с. 45].

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

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

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

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

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

Рассмотрение входных данных большого размера и оценка порядка проста времени работы алгоритма приводят к понятию асимптотической сложности алгоритма. При этом алгоритм с меньшей асимптотической сложностью является более эффективным для всех входных данных, за исключением лишь, возможно, данных малого размера. Для записи асимптотической сложности алгоритмов используется обозначение функции ограничения сверху (с точностью до постоянного множества) O-большое. Например, алгоритм имеет сложность O(f(N)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N).

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

1. O(1), константная сложность;

2. lg(lg(N));

3. lg(N), логарифмическая сложность;

4. O(N), линейная сложность;

5. N*lg(N);

6. C^N, C>1;

7. N!.

1.2. История алгоритмов сортировки данных

Серьезное практическое значение проблема сортировки данных в больших массивах впервые приобрела в середине XIX в. в США. В 1840 г. там был создан центральный офис переписи населения, куда стекались первичные данные из всех штатов. В процессе переписи было опрошено 17 069 453 человек, каждая анкета включала 13 вопросов. Объём полученных данных был настолько велик, что их обработка традиционным ручным способом требовала непомерных затрат времени и труда. Ситуация осложнялась необходимостью проведения постоянных пересчетов и сверок вследствие допускаемых при ручной сортировке данных ошибок. С каждой следующей переписью, которая проводилась каждые 10 лет, объём обрабатываемой информации, а вместе с ним длительность и стоимость обработки данных увеличивались [7, с. 135].

Например, ручная обработка данных переписи населения 1880 г. (50 189 209 человек) требовала привлечения сотен служащих и продолжалась 7,5 лет. Перед переписью 1890 г. для решения проблем сортировки данных в очень больших массивах информации по инициативе бюро переписи был проведен конкурс на лучшее электромеханическое сортировочное оборудование, которое делало бы сортировку данных более эффективной — более точной, быстрой и дешевой. Конкурс выиграл американский изобретатель и инженер немецкого происхождения Г. Холлерит, разработавший оборудование для работы с перфокартами — электрическую табулирующую систему [9, с. 25].

Использование данного оборудования при переписях населения США в 1890 и 1900 гг. было признано крайне успешным. Вот как описывались достоинства машины Холлерита в отечественном журнале «Вестник Опытной Физики и Элементарной Математики» в 1895 г.: «Преимущества машины Холлерита заключаются:

а) в серьезном удешевлении и ускорении работы. При ручном методе можно посчитать и разложить за час не больше 400 карточек. Если принять, что в Российской Империи 120 млн. жителей, то для изготовления одной лишь сводной таблицы потребуется не меньше 300 000 часов. Машина уменьшает работу практически в 5 раз.

б) в большей точности результатов и в большей легкости получения сложных сводных таблиц. После немногих пропусков через машину всех счетных карточек получаются столь разнообразные и полные таблицы, составление которых было практически немыслимо при прежнем способе» [9, с. 30].

Использование способа табулирования при сортировке данных оказалось таким эффективным, что предварительные подсчеты результатов переписи заняли лишь 6 недель, а полная статистическая оценка данных заняла 2,5 года. В результате, обработка данных при помощи машины Холлерита требовала в 3 раза меньше времени, чем ручным способом, причем точность сводных таблиц серьезно выросла. Таким образом, в конце XIX в. на смену ручной сортировке данных в массивах пришла сортировка при помощи статистических табуляторов. При этом использовался алгоритм поразрядной сортировки [22, с. 237].

Следующим этапом развития алгоритмов и способов сортировки является начало 1940-х гг. с созданием первых ЭВМ. Немыслимое по тем временам быстродействие ЭВМ вызвало увеличение интереса к новым, приспособленным для машинной обработки алгоритмам сортировки. В 1946 г. появилась первая статья об алгоритмах сортировки данных, автором которой был Дж. У. Мочли — американский инженер и физик, один из создателей первого в мире электронного цифрового компьютера общего назначения ENIAC.