Файл: Методы сортировки данных: эволюция и сравнительный анализ. Примеры использования (Свойства и классификация).pdf

Введение

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

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

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

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

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

• Анализ эволюции методов сортировки.
• Проведение классификации и сравнения методов сортировки.
• Подробное изучение и реализация некоторых алгоритмов на языке С++.

Глава 1. Эволюция и сравнение методов сортировки

В середине 1950-х годов с разработкой ЭВМ второго поколения началось активное развитие алгоритмов сортировки. Основными предпосылками для этого стали, во-первых, значительное упрощение и ускорение написания программ для компьютеров в результате разработки первых языков программирования высокого уровня (Фортран, Алгол, Кобол); во-вторых, значительное повышение доступности компьютеров в результате резкого уменьшения их габаритов и стоимости и, как следствие, достаточно широкое их распространение; в-третьих, увеличение производительности компьютеров до 30 тысяч операций в секунду.

В 1959 году Дональд Левис Шелл (Donald Lewis Shell) предложил метод сортировки с убывающим шагом (shellsort), в 1960 году Чарльз Энтони Ричард Хоар (Charles Antony Richard Hoare) — метод быстрой сортировки (quicksort), в 1964 году Дж. У. Дж. Уильямс (J. V. J. Williams) — метод пирамидальной сортировки (heapsort). Многие из разработанных в этот период алгоритмов (например, быстрая сортировка Хоара) широко используются до настоящего времени [3].

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

Большинство методов использовали алгоритмы вставок, обменов или выбора для внутренних сортировок. Но не всегда объемы данных позволяли использовать внутреннюю сортировку, что привело к развитию алгоритмов внешних сортировок, позволяющих сортировать данные лишь частично подгруженные в оперативную память [4].

Очередной всплеск интереса к алгоритмам сортировки произошел в середине 1970-х годов, когда элементной базой компьютеров стали большие интегральные схемы и появилась возможность объединения мощности вычислительных машин путем создания единых вычислительных центров, позволяющих работать с разделением времени. В период с середины 1970-х до 1990-х годов были достигнуты значительные успехи в увеличении скорости сортировки за счет повышения эффективности уже известных к тому времени алгоритмов путем их доработки или комбинирования. К примеру, нидерландский учёный Эдсгер Вибе Дейкстра (Edsger Wybe Dijkstra) в 1981 году предложил алгоритм плавной сортировки (Smoothsort), который является развитием пирамидальной сортировки (Heapsort).

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

В своих работах Дупленко А. Г выделил пять этапов развития процесса сортировки [6].

Первый этап начался в 1870 году и длился до начала 1940-х годов. В это время появляются первые механизмы машинной сортировки данных, однако они основаны на простых перфокарточных машинах.

Второй этап — с начала 1940-х годов до середины 1950-х. Этот этап характеризуется появлением первых ЭВМ и соответственно первых алгоритмов сортировки для этих ЭВМ. Появилась классификация сортировок на внешние и внутренние. Наиболее распространенными в этот период были модификации сортировки слиянием и вставками сложности O (n log n).

Третий этап начался в середине 1950-х годов и продолжался до середины 1970-х. Этот этап характеризуется появлением первых языков программирования высокого уровня. Появляется большое количество алгоритмов сортировки для этих языков программирования, появляется классификация этих алгоритмов на устойчивые и неустойчивые. Наибольшее количество разработанных к тому времени методов относилось к сортировке путем вставок, обменной сортировке и сортировке посредством выбора.

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

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

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

1.1 Свойства и классификация

• Устойчивость (англ. stability) — устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами.
• Естественность поведения — эффективность метода при обработке уже упорядоченных или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
• Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет O(n log n), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.

По сфере применения сортировки делят на следующие группы:

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

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

Рассмотрим основные сортировки:

Сортировка выбором (Selection sort). Может быть реализован и как устойчивый, и как неустойчивый алгоритм. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае О(n²), предполагая, что сравнения делаются за постоянное время.

Наихудший случай:

• Число сравнений в теле цикла равно (N-1)*N/2.
• Число сравнений в заголовках циклов (N-1)*N/2.
• Число сравнений перед операцией обмена N-1.
• Суммарное число сравнений N2−1.
• Число обменов N-1.

Сортировка простыми обменами, сортировка пузырьком (bubble sort). Сложность алгоритма: O(n²).

Наихудший случай:

• Число сравнений в теле цикла равно (N-1)*N/2.
• Число сравнений в заголовках циклов (N-1)*N/2.
• Суммарное число сравнений равно (N-1)*N.
• Число присваиваний в заголовках циклов равно (N-1)*N/2.
• Число обменов равно (N-1)*N/2.

Наилучший случай:

• Число сравнений в теле цикла равно (N-1).
• Число сравнений в заголовках циклов (N-1).
• Суммарное число сравнений равно 2*(N-1).
• Число обменов равно 0.

Быстрая сортировка (англ. quicksort), часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром в МГУ в 1960 году. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов), хотя и имеющий ряд недостатков.

Наихудший случай:

• Число разбиений: N.
• Сложность алгоритма: O(N²).

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

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

В приведенных таблицах используются следующие сортировки:

• Selection sort – сортировка выбором.
• Bubble sort – сортировка пузырьком.
• Insertion sort – сортировка вставками.
• Quick sort – быстрая сортировка.

Полностью неотсортированный массив:

Рисунок 1. Результат эксперимента.

Частично отсортированный массив (половина элементов упорядочена):

Рисунок 2. Результат эксперимента.

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

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