Статья посвящена проблеме выбора оптимального алгоритма сортировки данных в массивах, что предполагает сравнительный анализ алгоритмов. Рассмотрены алгоритмы устойчивой и неустойчивой сортировки; непрактичные алгоритмы; алгоритмы, не основанные на сравнениях; алгоритмы топологической сортировки. Представлены результаты сравнительного анализа достоинств и недостатков данных видов сортировки, а также сравнения отдельных алгоритмов по параметрам «устойчивость» и «скорость» с помощью матричного метода.
Ключевые слова: алгоритм сортировки, сравнение алгоритмов сортировки.
Используемые в настоящее время объемы массивов данных достигают размеров, которые еще десятилетие назад казались почти невероятными. Чем большими становятся объемы перерабатываемых данных, тем актуальнее становится задача оптимизации используемых алгоритмов, в том числе и сортировки. В то же время по-прежнему важными остаются задачи, не требующие повышения скорости алгоритмов. Например, для образовательных целей часто более важной является их простота.
Рост требований к скорости алгоритмов сортировки и расширение круга задач, для которых они используются, приводит к тому, что по-прежнему важной и актуальной остается задача сравнительного анализа алгоритмов сортировки.
Целью проведенного исследования было сопоставление преимуществ и недостатков наиболее распространенных алгоритмов сортировки данных в массивах.
Для достижения поставленной цели были поставлены и решены следующие задачи:
1. Определить наиболее распространенные алгоритмы сортировки данных;
2. Выявить достоинства и недостатки данных алгоритмов;
3. Сопоставить достоинства и недостатки алгоритмов сортировки.
При определении наиболее распространенных алгоритмов мы пользовались следующей классификаций: алгоритмы устойчивой сортировки; алгоритмы неустойчивой сортировки; непрактичные алгоритмы сортировки; алгоритмы, не основанные на сравнениях и алгоритмы топологической сортировки.
При использовании алгоритмов устойчивой (стабильной) сортировки при наличии в наборе данных нескольких равных элементов в отсортированном наборе они сохраняются в том же порядке, в котором были в исходном наборе. Таким образом, устойчивая сортировка не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи.К числу алгоритмов устойчивой сортировки относятся сортировка пузырьком (Bubble sort), сортировка перемешиванием (шейкерная, Cocktail sort, Bidirectional bubble sort), гномья сортировка (Gnome sort), сортировка вставками (Insertion sort), сортировка слиянием (Merge sort), сортировка с помощью двоичного дерева (Tree sort), алгоритм сортировки Тима Петерса (Timsort), сортировка подсчётом (Counting sort), блочная сортиров-ка (корзинная сортировка, Bucket sort) и ряд других.
К числу общих преимуществ алгоритмов устойчивой сортировки относится то, что сохранение взаимного расположения равных элементов важно при сортировке по одному полю данных, состоящих из нескольких полей. Следует отметить, однако, что этого можно добиться и путем удлинения исходных ключей за счёт дополнительной информации об их первоначальном порядке [1, с. 54]. Общим недостатком алгоритмов устойчивой сортировки является то, что они не гарантируют, что для обеспечения устойчивости практически всегда необходимы дополнительная память и время (таблица 1).
Таблица 1
Сравнение преимуществ и недостатков основных видов алгоритмов сортировки
|
№ п/п |
Виды алгоритмов сортировки |
Преимущества |
Недостатки |
|
1. |
Алгоритмы устойчивой сортировки |
Сохранение взаимного расположения равных элементов важно при сортировке по одному полю данных, состоящих из нескольких полей |
Для обеспечения устойчивости практически всегда необходимы дополнительная память и время. |
|
2. |
Алгоритмы неустойчивой сортировки |
Как правило, для сортировки требуется меньше памяти и времени, чем при использовании алгоритмов устойчивой сортировки. |
При сортировке по одному полю данных, состоящих из нескольких полей, не сохраняется взаимное расположение равных элементов. |
|
3. |
Непрактичные алгоритмы сортировки |
Эффективны для специфических целей, например, обучения или для сортировки с особыми условиями. |
По сравнению с другими алгоритмами требуют значительно большего времени, значительно большей памяти или специализированного аппаратного обеспечения. |
|
4. |
Алгоритмы, не основанные на сравнениях |
Быстрота при условии использования подходящего массива входных данных. |
Низкая эффективность, если массив входных данных не является удачным для соответствующего алгоритма сортировки. |
|
5. |
Алгоритмы топологической сортировки |
Позволяют построить корректную последовательность выполнения действий, каждое из которых может зависеть от другого. |
Сравнительно узкая сфера возможного использования. |
При использовании алгоритмов неустойчивой сортировки могут меняться местами данные с одинаковыми значениями. Это является недостатком в том случае, когда при сортировке по одному полю данных, состоящих из нескольких полей, важно сохранение взаимного расположения равных элементов важно при сортировке по одному полю данных. В то же время большинство алгоритмов неустойчивой сортировки требуют меньшей памяти и времени, чем алгоритмы устойчивой сортировки. Наиболее известными алгоритмами неустойчивой сортировки являются сортировка Шелла (Shell sort), сортировка расчёской (Comb sort), пирамидальная сортировка (сортировка кучи, Heapsort), плавная сортировка (Smoothsort), быстрая сортировка (Quicksort), интроспективная сортировка (Introsort), терпеливая сортировка (Patience sorting), сортировка по частям (блуждающая сортировка, Stooge sort) и поразрядная сортировка (цифровая сортировка, Radix sort).
Непрактичные алгоритмы сортировки требуют значительно большего времени, значительно большей памяти или специализированного аппаратного обеспечения.
Наиболее известными непрактичными алгоритмами сортировки являются алгоритмы, представленные в таблице 2.
Таблица 2
Непрактичные алгоритмы сортировки
|
№ п/п |
Название |
Недостаток |
Сфера использования |
|
1. |
Случайная сортировка (обезьянья сортировка, Bogosort) |
Время сортировки значительно больше, чем у других алгоритмов |
В образовательных целях, для сравнения с другими, более эффективными алгоритмами |
|
2. |
Глупая сортировка (Stupid sort) |
Эффективен лишь для небольших массивов данных. При увеличении массива требует значительных объемов дополнительной памяти. |
В образовательных целях, самый простейший алгоритм для понимания и реализации. |
|
3. |
Бисерная сортировка (бусинная сортировка, Bead Sort) |
Очень медленный алгоритм, который к тому же требует много дополнительной памяти и может быть использован только для сортировки списков целых положительных чисел. |
В образовательных целях. |
|
4. |
Блинная сортировка (Pancake sorting) |
Требуется специализированное аппаратное обеспечение |
Используется в тех случаях, когда единственной операцией, допустимой в алгоритме, является переворот элементов последовательности до какого-либо индекса. |
Таким образом, недостатки непрактичных сортировок очевидны и видны уже из их названия. Их достоинства заключаются в том, что они могут быть использованы для определенных целей, чаще образовательных.
Алгоритмы, не основанные на сравнениях, как следует из самого их названия, совсем не используют сравнений сортируемых элементов. Наиболее известными из данных алгоритмов являются блочная сортировка (корзинная сортировка, Bucket sort), лексикографическая сортировка (поразрядная сортировка, Radix sort) и сортировка подсчётом (Counting sort). При блочной сортировке требуются знания о природе сортируемых данных, выходящих за рамки функций «сравнить» и «поменять местами», достаточных для сортировки с использованием других элементов. Лексикографическая сортировка пригодна для сортировки любых элементов, состоящих из цепочек над фиксированным алфавитом, на котором задано отношение сравнения. При сортировке подсчетом используется диапазон чисел сортируемого массива для подсчёта совпадающих элементов [2, с. 24]..
Достоинством алгоритмов, не основанных на сравнениях, является их быстрота при условии использования подходящего типа входных данных. Если массив входных данных не соответствует предъявляемым требованиям, эффективность данных методов значительно снижается [3, с. 132]..
Алгоритмы топологической сортировки включают алгоритмы, которые нельзя отнести ни к одной другой группе. К ним относятся алгоритм Демукрона, алгоритм сортировки для представления графа в виде нескольких уровней, а также алгоритм топологической сортировки с помощью обхода в глубину. Все они основаны на упорядочивании вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин [4, с. 35]..
Достоинством топологической сортировки является то, что при ее помощи строится корректная последовательность выполнения действий, всякое из которых может зависеть от другого. Недостаток — сравнительно узкая сфера использования.
Для сравнения алгоритмов сортировки удобно использовать матричный метод, который предполагает сравнение по двум параметрам. Так, в зависимости от устойчивости и скорости алгоритмы сортировки можно разделить на шесть групп (рис. 1).
Рис. 1. Группировка алгоритмов сортировки по скорости и устойчивости
Среди рассмотренных нами алгоритмов сортировки большинство входит в три группы, которые условно можно назвать «Быстрая устойчивая сортировка» (сортировка слиянием и алгоритм сортировки Тима Петерса), «Быстрая неустойчивая сортировка» (сортировка Шелла, быстрая сортировка, пирамидальная сортировка, интроспективная сортировка, терпеливая сортировка, плавная сортировка), а также «Медленная устойчивая сортировка» (сортировка пузырьковым методом, сортировка вставками, сортировка выбором, сортировка перемешиванием, гномья сортировка).
Таким образом, существующие алгоритмы сортировки массивов значительно различаются по уровню сложности, скорости, устойчивости, требованиям к памяти и другим параметрам. Однако практически каждый алгоритм оказывается наиболее удобным в какой-либо конкретной ситуации. Востребованными являются даже очень медленные алгоритмы, которые из-за своей простоты находят применение в образовательных целях. Если сравнивать алгоритмы сортировки по скорости и устойчивости, то для большинства устойчивых алгоритмов характерно среднее число операций n2, а большинство алгоритмов неустойчивой сортировки являются более быстрыми. Среднее число операций здесь меньше n2 (n log n для большинства алгоритмов).
Литература:
1. Овчинникова И. Г., Сахнова Т. Н. Алгоритмы сортировки при решении задач по программированию // Информатика и образование. — 2011. — № 2. — С. 53–56.
2. Антонова И. И., Карих О. А. Оценка эффективности параллельных алгоритмов задачи сортировки данных // Промышленные АСУ и контроллеры. — 2010. — № 3. — С. 23–25.
3. Мартынов В. А., Миронов В. В. Параллельные алгоритмы сортировки данных с использованием технологии MPI // Вестник Сыктывкарского университета. Серия 1: Математика. Механика. Информатика. — 2012. — № 16. — С. 130–135.
4. Коварцев А. Н., Попова-Коварцева Д. А. Структурная оптимизация управляющего графа на основе алгоритма топологической сортировки // Программная инженерия. — 2013. — № 5. — С. 31–36.
