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

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

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

3.2 Сортировка Шелла

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

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

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

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

Например, если в массиве 14 объектов (), согласно вышеприведенной формуле, мы выбираем следующие проходы ():

• Проход каждые 6 единиц ();
• Проход каждые 3 единицы ();
• Проход каждые 2 единицы ();
• Проход каждую единицу (), обычная сортировка вставками;

Покажем выполнение такой сортировки на примере массива из четырнадцати элементов (33,95,16,82,24,65,35,19,74,55,39,44,94,67).

Вначале мы сортируем подмассивы с шагом шесть. Таких подмассивов будет также шесть – (33,35,94), (95,19,67), (16,74), (82,55), (24,39), (65,44). Для сортировки данных подмассивов понадобится четыре перестановки (две для второго подмассива, одна для четвертого и одна для шестого). В итоге мы получим подмассивы (33,35,94), (19,67,95), (16,74), (55,82), (24,39), (44,65). Вновь объединим их, и получим массив: (33,19,16,55,24,44,35,67,74,82,39,65,94,95).

Теперь сортируем массивы с шагом три. Таких подмассивов будет также три – (33,55,35,82,94), (19,24,67,39,95), (16,44,74,65). Для сортировки данных подмассивов понадобится три перестановки (одна для первого подмассива, одна для второго и одна для третьего). В итоге мы получим подмассивы (33,35,55,82,94), (19,24,39,67,95), (16,44,65,74). Вновь объединим их, и получим массив: (33,19,16,35,24,44,55,39,65,82,67,74,94,95).

Теперь сортируем массивы с шагом два. Таких подмассивов будет также два – (33,16,24,55,65,67,94), (19,35,44,39,82,74,95). Для сортировки данных подмассивов понадобится четыре перестановки (две для первого подмассива, и две для второго). В итоге мы получим подмассивы (16,24,33,55,65,67,94), (19,35,39,44,74,82,95). Вновь объединим их, и получим массив: (16,19,24,35,33,39,55,44,65,74,82,95).

Наконец отсортируем наш массив с шагом 1, обычной сортировкой вставками. Получим массив (16,19,24,33,35,39,44,55,65,74,82,95) за две перестановки.

Итого, нам понабилось сделать перестановок. Если бы мы сортировали обычными вставками, то на весь процесс ушло бы около 40 перестановок. Наш метод позволил выполнить сортировку практически в три раза быстрее.

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

3.3 Быстрая сортировка

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

Процесс быстрой сортировки состоит из трех шагов.

1. В исходном массиве необходимо выбрать некий элемент, который называется опорным. Такой элемент можно выбрать любым (первым, последним, средним, или вообще случайным). От выбора элемента, вообще говоря, зависит эффективность алгоритма, однако если данные распределены равномерно, то его выбор не является важным;
2. Необходимо перераспределить элементы массива так, чтобы элементы меньшие опорного оказались левее него (имели меньшие индексы), а элементы, большие опорного – правее него (имели большие индексы). Если в массиве есть повторяющиеся элементы, то элементы равные опорному должны оказаться рядом с ним (расположены последовательно);
3. После этого каждый из подмассивов (с числами, меньшими и большими опорного) сортируются тем же методом (рекурсивно).

Сложность в данном алгоритме представляет собой реализация
пункта 2 – а именно, как сделать так, чтобы элементы, меньшие опорного остались слева, а большие оказались справа. Для выполнения данного шага используется так называемое «Разбиение Хоара». Оно состоит в использовании двух указателей – один указывает на первый элемент массива, а другой – на последний. Они постепенно приближаются друг к другу (левый указатель сдвигается вправо, а правый – влево), пока либо не сойдутся до опорного элемента (тогда шаг считается выполненным), либо левый указатель не станет указывать на больший элемент, а правый на меньший. В таком случае эти два элемента необходимо поменять местами, и продолжить выполнение разбиения.

Из-за высокой скорости работы данного алгоритма, а также отсутствия необходимости в дополнительной памяти, он был признан одним из лучших, и очень широко применяется. Однако у данного алгоритма есть один недостаток – позиция опорного элемента влияет на время сортировки. Если опорный элемент каждый раз выбирается удачно, то время выполнение алгоритма асимптотически стремится к , что является очень хорошим результатом. Однако если опорный элемент выбирается не лучшим образом, то время стремится к очень плохому значению . Как правило, если массив не имеет каких-либо особенностей (данные распределены равномерно), а опорный элемент выбирать случайно, то данный алгоритм работает очень быстро. Однако не следует забывать и о том, что эта быстрота не гарантирована.

3.4 Пирамидальная сортировка

Пирамидальная сортировка, называемая еще «сортировка кучей» представляет собой сортировку массива, путем представления его в виде особой структуры данных под названием «бинарное сортирующее дерево». Это дерево (вид графа), обладающее следующими свойствами:

1. Всего в дереве столько узлов, сколько сортируемых элементов;
2. В каждом узле дерева находится какое-либо значение исходного массива;
3. В корне дерева находится самое маленькое или самое большое значение исходного массива (в зависимости от направления сортировки);
4. Из каждого узла, кроме самых последних (листьев) отходят две ветви;
5. Значение в каждом узле дерева должно быть не меньше (либо не больше, в зависимости от направления сортировки) значений потомков, которые из данной ветви выходят.

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

После того, как мы переставили элементы исходного массива таким образом, чтобы они образовали бинарное сортирующее дерево, в его корне мы получаем самое маленькое, или наоборот, самое большое значение исходного массива. Мы можем просто взять его, и обменять с последним элементом. Тогда (при условии, что исходно в массиве было элементов), мы получим один (последний) отсортированный элемент, и элементов, которые «почти» образуют бинарное сортирующее дерево. Оно подходит всем условиям для того, чтобы являться таким деревом кроме одного – в его корне стоит элемент, который ранее находился последним, а не то, которое требуется согласно пункту 3. Поэтому бинарному дереву будет требоваться «перебалансировка» - его упорядочивание, достигаемое путем перемещения корневого элемента в нужное место. Эта перебалансировка можно быть выполнена за шагов, то есть, является довольно быстрой. После выполнения перебалансировки можно повторить данный алгоритм, получив еще один элемент отсортированного массива. Повторив данный алгоритм раз, мы получим полностью отсортированный массив.

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

Из-за достоинств данного алгоритма (быстрота и отсутствие необходимости в дополнительной памяти), он довольно широко применяется. Например, можно отметить применение его в ядре операционной системы Linux [9]

4. Алгоритмы устойчивой сортировки

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

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

Однако иногда данные гарантии необходимы, и приходится использовать именно устойчивую сортировку. Например, у нас есть массив, в который мы записываем ФИО участника, а также количество задач, которые он решил на некоторой олимпиаде. Как только какой-либо участник решал очередную задачу, его данные заносились в этот массив (либо, если он уже там присутствовал, то данные о нем удалялись, и заносились снова с увеличенным количеством решенных им задач). Теперь, если мы отсортируем данный массив по количеству решенных задач (например, желая определить первые три места для награждения), может получиться так, что несколько первых мест (скажем, пять) решат одинаковое количество задач (допустим, все, которые были на олимпиаде). В таком случае, как правило, первое место отдают тому участнику, который решил задачи быстрее всех (то есть, участнику, которого внесли в массив быстрее других, который имеет в нем меньший номер). Если бы сортировка была неустойчивой, то в данном случае первые пять мест могли бы перепутаться как угодно. Хотя, конечно, все эти пять мест решили одинаковое количество задач, тем не менее, согласно регламенту соревнования, их нужно различать.