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

Для современного этапа разработки методов и методов сортировки характерно исследование задач сортировки по частично упорядоченным множествам: задачи распознавания частично упорядоченного множества M; задачи сортировки частично упорядоченного множества M с использованием результатов парных сравнений элементов, а также задачи определения порядка на множестве M без априорной информации. Актуальность этих задач обусловлена ​​появлением и распространением компьютеров на суперкомплексных микропроцессорах с параллельно-векторной структурой, высокоэффективных сетевых компьютерных систем [3].

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

Первый этап начался в 1870 году и продолжался до начала 1940-х годов. Отмечен переход от ручной сортировки к сортировке с использованием статистических табуляторов. В этом случае использовался алгоритм побитовой сортировки [4].

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

Третий этап начался в середине 1950-х годов и продолжался до середины 1970-х годов. Для него было характерно активное развитие алгоритмов сортировки - внешних и внутренних, стабильных и нестабильных - многие из которых широко используются сегодня. Наибольшее количество разработанных к тому времени методов связано с сортировкой по вставкам, обменной сортировкой и сортировкой по выбору [10].

Четвертый этап длился с середины 1970-х до середины 1990-х годов. Появление компьютерных центров, сочетающих мощность отдельных компьютеров и позволяющих работать с разделением времени, потребовало разработки новых алгоритмов сортировки и модификации существующих. Началось изучение проблем сортировки в классе параллельных алгоритмов, достигнут значительный прогресс в увеличении скорости сортировки за счет повышения эффективности алгоритмов, уже известных к тому времени благодаря их уточнению или комбинации. В то же время был проведен поиск оптимальных входных последовательностей для разных методов сортировки, что позволило значительно сократить его время [3].

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

3. Методы внутренней сортировки

При внутренней сортировке все отсортированные данные помещаются в оперативную память компьютера, где вы можете получить доступ к данным в любом порядке (то есть используется модель памяти с произвольным доступом). Внешняя сортировка применяется, когда объем данных, которые нужно упорядочить, слишком велик для того, чтобы все данные были помещены в основную память. Здесь узким местом является механизм перемещения больших блоков данных с внешних устройств хранения данных в основную память компьютера и наоборот. Тот факт, что физически непрерывные данные необходимы для удобного перемещения в виде блочной структуры, заставляет нас использовать различные методы внешней сортировки [1].

Рассмотрим основные базовые алгоритмы внутренней сортировки. Простейший из этих алгоритмов тратит время порядка O (n2). Другими словами, при сортировке массива, состоящего из n компонентов, такие алгоритмы будут выполнять действия c * n2, где c - некоторая константа. Потому что применимо только к небольшим наборам предметов. Один из самых популярных алгоритмов сортировки, так называемая быстрая сортировка, выполняется в среднем за время O (n log n). Быстрая сортировка хорошо работает в большинстве приложений, хотя в худшем случае она также имеет время выполнения O (n2). Существуют другие методы сортировки, такие как сортировка по пирамиде или сортировка по слиянию, которые в худшем случае дают время порядка O (n log n), но в среднем (в статистическом смысле) работают не лучше, чем быстрая сортировка. Отметим, что метод сортировки слиянием хорошо подходит для построения внешних алгоритмов сортировки [7].

Предположим, что сортируемые объекты являются записями, содержащими одно или несколько полей. Одно из полей, называемое ключом, имеет такой тип данных, что оно определяет отношение линейного порядка «<». Целые и действительные числа, символьные массивы являются типичными примерами таких типов данных, но, конечно, мы можем использовать ключи других типов данных, при условии, что они могут определять отношение «меньше» или «меньше или равно» [6].

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

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

3.1.Простые методы сортировки

3.1.1.Пузырьковая сортировка (метод обменной сортировки)

Самым простым и известным методом сортировки является так называемый метод пузырьковой сортировки. Основная идея этого метода заключается в том, что сортируемые данные хранятся в массиве, расположенном вертикально. Записи с небольшими значениями ключевого поля светлее и всплывают вверх, как пузырь [3]. Во время первого прохода по массиву, начиная переход снизу, берется первая запись массива, и ее ключ поочередно сравнивается с ключами последующих записей. Если есть запись с «более тяжелым» ключом, то эти записи меняются местами. При встрече записи с «светлым» ключом эта запись становится «эталоном» для сравнения, и все последующие записи сравниваются с этим новым, более светлым «ключом». В результате запись с наименьшим значением ключа будет находиться в самом верху массива. Во время второго прохода вдоль массива идет запись со вторым по величине ключом, которая помещается под записью, найденной во время первого прохода массива, то есть на втором месте с верхней позиции и т. Д. [1].

Демонстрация сортировки по неубыванию методом «пузыря» представлена ​​в приложении [рис.1]

Bubblesorting использует метод сортировки обмена. Он основан на выполнении операций сравнения в цикле и, при необходимости, обмена соседними элементами. Его название обусловлено сходством процесса движения пузырьков в резервуаре с водой, когда каждый пузырь находит свой уровень [6].

При анализе любой сортировки определяется количество операций сравнения и обмена, выполненных в лучшем, среднем и худшем случаях. Для пузырьковой сортировки количество сравнений остается неизменным, поскольку два цикла всегда выполняются указанное количество раз, независимо от порядка в исходном массиве. Это означает, что при сортировке методом пузырьков всегда выполняются операции сравнения, где «n» указывает количество элементов, которые должны быть отсортированы массивом. Эта формула получена на основании того, что цикл сортировки внешнего цикла выполняется n-1 раз, а внутренний цикл - n / 2 раза. Их умножение даст указанную формулу. Количество операций обмена будет нулевым в лучшем случае, когда исходный массив уже отсортирован. Количество обменных транзакций для среднего случая будет равно, а для худшего случая оно будет равно временам. Можно отметить, что по мере ухудшения упорядочения исходного массива число неупорядоченных элементов приближается к числу сравнений (каждый неупорядоченный элемент требует трех операций обмена). Сортировка по пузырьковому методу называется квадратичным алгоритмом, поскольку время его выполнения пропорционально квадрату количества отсортированных элементов. Сортировка большого количества элементов с использованием пузырькового метода займет много времени, так как время выполнения сортировки находится в квадратичной зависимости от количества элементов массива [5].

3.1.2.Сортировка вставками

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

Хотя этот метод сортировки намного менее эффективен, чем более сложные алгоритмы (такие как быстрая сортировка), он имеет несколько преимуществ:

• прост в реализации

• эффективен для небольших наборов данных

• эффективен для наборов данных, которые уже частично отсортированы

• это надежный алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы)

• может сортировать список по мере его поступления

На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его в нужную позицию в уже отсортированном списке, пока набор входных данных не будет исчерпан. Выбор следующего элемента, выбранного из исходного массива, является произвольным; можно использовать практически любой алгоритм выбора. Количество перестановок для сортировки вставок в среднем точно такое же, как и для пузырькового алгоритма [2]. Демонстрация сортировки вкладышей представлена ​​в приложении [Рис.2].

Сортировка вкладышей требует фиксированного количества проходов. Общее количество сравнений:

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

Положительной стороной метода является простота реализации, а также его эффективность на частично упорядоченных последовательностях и / или состоящих из небольшого количества элементов. Однако высокая вычислительная сложность не позволяет рекомендовать алгоритм для широкого использования. [4].

3.1.3.Сортировка методом выбора.

Сортировка выбором — это некий гибрид между пузырьковой сортировкой и сортировкой вставками [5].

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

При данной сортировке из массива выбирается элемент с наименьшим значением и обменивается с первым элементом. Затем из оставшихсяn-1 элементов снова выбирается элемент с наименьшим ключом и обменивается со вторым элементом, и т.д. Демонстрация методом выбора представлена в приложении [рис. 3].

Как и в пузырьковой сортировке, внешний цикл выполняетсяn-1 раз, а внутренний – в среднем n/2 раз. Следовательно, сортировка методом простого выбора требует сравнений. Таким образом, это алгоритм порядка O(n²), из-за чего он считается слишком медленным для сортировки большого количества элементов.

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

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

3.2. Улучшенные (усовершенствованные) методы сортировки

В отличие от простых сортировок со сложностью O (n2), алгоритмы с общей сложностью O (n log n) относятся к числу улучшенных сортировок.

Следует отметить, однако, что для небольших наборов данных, которые должны быть отсортированы (n <100), эффективность быстрых сортировок не столь очевидна: усиление становится заметным только для больших n. Поэтому, если необходимо отсортировать небольшой набор данных, выгоднее выполнить одну из простых сортировок [2].

3.2.1. Сортировка Шелла (слияние с обменом)

В 1959 году Дональд Шелл отметил, что в алгоритме вставки наиболее неэффективным шагом является перенос текущего объекта в левую сторону через множество других объектов [6]. Shell предложила эффективный способ решения этой проблемы - последовательное применение так называемых частичных сортировок. Используя указанный механизм, алгоритм генерирует массив для сортировки по h, где h - это значение, на которое каждый элемент может отклоняться от своей целевой позиции в полностью отсортированном массиве данных. Таким образом, последовательно применяя частичную сортировку с уменьшением значения h, можно сортировать большой массив данных быстрее, чем классические алгоритмы сортировки. Однако слабым местом этого метода является сложность выбора последовательности частичных сортировок. От правильности этого выбора зависит конечная эффективность алгоритма. Обычная практика - последовательность, предложенная Дональдом Кнутом, математиком и ученым.: . [2].