Сравнительный анализ алгоритмов сортировки данных в массивах | Статья в журнале «Молодой ученый»

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

Опубликовать статью в журнале

Автор:

Рубрика: Информационные технологии

Опубликовано в Молодой учёный №8 (55) август 2013 г.

Статья просмотрена: 16971 раз

Библиографическое описание:

Дупленко, А. Г. Сравнительный анализ алгоритмов сортировки данных в массивах / А. Г. Дупленко. — Текст : непосредственный // Молодой ученый. — 2013. — № 8 (55). — С. 50-53. — URL: https://moluch.ru/archive/55/7474/ (дата обращения: 16.11.2024).

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

Ключевые слова: алгоритм сортировки, сравнение алгоритмов сортировки.

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

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

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

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

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.

Основные термины (генерируются автоматически): алгоритм, устойчивая сортировка, неустойчивая сортировка, сортировка, топологическая сортировка, алгоритм сортировки, Непрактичный алгоритм сортировки, взаимное расположение, данные, дополнительная память.


Ключевые слова

алгоритм сортировки, сравнение алгоритмов сортировки., сравнение алгоритмов сортировки

Похожие статьи

Эволюция способов и алгоритмов сортировки данных в массивах

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

Алгоритмы оптимальной структуры компьютерной сети

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

Анализ поисковых алгоритмов при решении задач идентификации объектов в слабоструктурированных базах данных

В статье рассмотрены проблемы идентификации объектов в слабоструктуриро-ванной БД, представлены результаты сравнительного анализа применяющихся для их решения алгоритмов поиска

Методы решения нелинейных уравнений

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

Управление качеством строительных технологий на основе обобщенного критерия качества

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

Исследование методов сентимент-анализа русскоязычных текстов

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

Методы и алгоритмы эффективного решения задачи маршрутизации транспорта на сетях больших размерностей

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

Алгоритмические аспекты доминирования в графах

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

Цифровая обработка дважды стохастических моделей случайных полей

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

Алгоритмы распознавания символов

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

Похожие статьи

Эволюция способов и алгоритмов сортировки данных в массивах

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

Алгоритмы оптимальной структуры компьютерной сети

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

Анализ поисковых алгоритмов при решении задач идентификации объектов в слабоструктурированных базах данных

В статье рассмотрены проблемы идентификации объектов в слабоструктуриро-ванной БД, представлены результаты сравнительного анализа применяющихся для их решения алгоритмов поиска

Методы решения нелинейных уравнений

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

Управление качеством строительных технологий на основе обобщенного критерия качества

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

Исследование методов сентимент-анализа русскоязычных текстов

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

Методы и алгоритмы эффективного решения задачи маршрутизации транспорта на сетях больших размерностей

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

Алгоритмические аспекты доминирования в графах

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

Цифровая обработка дважды стохастических моделей случайных полей

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

Алгоритмы распознавания символов

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

Задать вопрос