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

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

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

• Выбираем в массиве некоторый элемент, который будем называть опорным элементом.
• Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него.
• Рекурсивно сортируем подсписки, лежащие слева и справа от опорного элемента.

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

2.2. Сравнение эффективности применения различных алгоритмов сортировки данных в массивах

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

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

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

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

Устойчивость – это параметр, который отвечает за то, что сортировка не меняет взаимного расположения равных элементов.

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

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

В своей статье “Сравнительный анализ алгоритмов сортировки данных в массивах” А. Дупленко проводит колоссальную работу, сравнивая различные методы сортировки. ^[7]

Исследователем была выбрана следующая классификация:

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

Таким образом, устойчивая сортировка не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи. К числу алгоритмов устойчивой сортировки относятся сортировка пузырьком (Bubble sort), сортировка перемешиванием (шейкерная, Cocktail sort, Bidirectional bubble sort), гномья сортировка (Gnome sort), сортировка вставками (Insertion sort), сортировка слиянием (Merge sort), сортировка с помощью двоичного дерева (Tree sort), алгоритм сортировки Тима Петерса (Timsort), сортировка подсчётом (Counting sort), блочная сортировка (корзинная сортировка, Bucket sort) и ряд других. К числу общих преимуществ алгоритмов устойчивой сортировки относится то, что сохранение взаимного расположения равных элементов важно при сортировке по одному полю данных, состоящих из нескольких полей. Следует отметить, однако, что этого можно добиться и путем удлинения исходных ключей за счёт дополнительной информации об их первоначальном порядке. Общим недостатком алгоритмов устойчивой сортировки является то, что они не гарантируют, что для обеспечения устойчивости практически всегда необходимы дополнительная память и время (таблица 1).

2. Алгоритмы неустойчивой сортировки. При использовании алгоритмов неустойчивой сортировки могут меняться местами данные с одинаковыми значениями. Это является недостатком в том случае, когда при сортировке по одному полю данных, состоящих из нескольких полей, важно сохранение взаимного расположения равных элементов важно при сортировке по одному полю данных. В то же время большинство алгоритмов неустойчивой сортировки требуют меньшей памяти и времени, чем алгоритмы устойчивой сортировки. Наиболее известными алгоритмами неустойчивой сортировки являются сортировка Шелла (Shell sort), сортировка расчёской (Comb sort), пирамидальная сортировка (сортировка кучи, Heapsort), плавная сортировка (Smoothsort), быстрая сортировка (Quicksort), интроспективная сортировка (Introsort), терпеливая сортировка (Patience sorting), сортировка по частям (блуждающая сортировка, Stooge sort) и поразрядная сортировка (цифровая сортировка, Radix sort).

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

4. Алгоритмы, не основанные на сравнениях. Алгоритмы, не основанные на сравнениях, как следует из самого их названия, совсем не используют сравнений сортируемых элементов. Наиболее известными из данных алгоритмов являются блочная сортировка (корзинная сортировка, Bucket sort), лексикографическая сортировка (поразрядная сортировка, Radix sort) и сортировка подсчётом (Counting sort). При блочной сортировке требуются знания о природе сортируемых данных, выходящих за рамки функций «сравнить» и «поменять местами», достаточных для сортировки с использованием других элементов. Лексикографическая сортировка пригодна для сортировки любых элементов, состоящих из цепочек над фиксированным алфавитом, на котором задано отношение сравнения. При сортировке подсчетом используется диапазон чисел сортируемого массива для подсчёта совпадающих элементов. Достоинством алгоритмов, не основанных на сравнениях, является их быстрота при условии использования подходящего типа входных данных. Если массив входных данных не соответствует предъявляемым требованиям, эффективность данных методов значительно снижается.

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

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

Среди рассмотренных нами алгоритмов сортировки большинство входит в три группы, которые условно можно назвать «Быстрая устойчивая сортировка» (сортировка слиянием и алгоритм сортировки Тима Петерса), «Быстрая неустойчивая сортировка» (сортировка Шелла, быстрая сортировка, пирамидальная сортировка, интроспективная сортировка, терпеливая сортировка, плавная сортировка), а также «Медленная устойчивая сортировка» (сортировка пузырьковым методом, сортировка вставками, сортировка выбором, сортировка перемешиванием, гномья сортировка).

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Дональд Кнут. Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720.
2. Дональд Кнут. Искусство программирования, т.3. Сортировка и поиск. — М.: Издательский дом «Вильямс», 2010
3. Дупленко А. Г. Эволюция способов и алгоритмов сортировки данных в массивах // Молодой ученый. — 2013. — №9. — С. 17-19. — URL https://moluch.ru/archive/56/7702/
4. Дупленко А. Г. Сравнительный анализ алгоритмов сортировки данных в массивах // Молодой ученый. — 2013. — №8. — С. 50-53. — URL https://moluch.ru/archive/55/7474/
5. Коварцев А. Н., Попова-Коварцева Д. А. Структурная оптимизация управляющего графа на основе алгоритма топологической сортировки // Программная инженерия. — 2013. — № 5.
6. Мартынов В. А., Миронов В. В. Параллельные алгоритмы сортировки данных с использованием технологии MPI // Вестник Сыктывкарского университета. Серия 1: Математика. Механика. Информатика. — 2012. — № 16. — С. 130–135.
7. Овчинникова И. Г., Сахнова Т. Н. Алгоритмы сортировки при решении задач по программированию // Информатика и образование. — 2011. — № 2. — С. 53–56.
8. Экономико-математический словарь: Словарь современной экономической науки. — М.: Дело. Л. И. Лопатников. 2003.
9. Электрическая машина Голлерита для подсчета статистических данных // В. О. Ф.Э.М. — 1895. — № 225. — С. 193–201.
10. United States Census // Sources of U. S. Census Data, from MIT Libraries, 2011. URL: http://libraries.mit.edu/guides/types/census/sources.html
11. Интернет-ресурс studepedia.org. URL: http://studepedia.org/index.php?vol=1&post=60498