Файл: Алгоритмы сортировки данных (Алгоритмы устойчивой сортировки).pdf

В 1959 году американский ученый Дональд Шелл опубликовал алгоритм сортировки, который впоследствии получил его имя – «Сортировка Шелла». Этот алгоритм может рассматриваться и как обобщение пузырьковой сортировки, так и сортировки вставками.

Идея метода заключается в сравнение разделенных на группы элементов последовательности, находящихся друг от друга на некотором расстоянии. Изначально это расстояние равно d или N/2, где N — общее число элементов. На первом шаге каждая группа включает в себя два элемента расположенных друг от друга на расстоянии N/2; они сравниваются между собой, и, в случае необходимости, меняются местами. На последующих шагах также происходят проверка и обмен, но расстояние d сокращается на d/2, и количество групп, соответственно, уменьшается. Постепенно расстояние между элементами уменьшается, и на d=1 проход по массиву происходит в последний раз.

Сортировка Шелла - алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Пример исполнения данного вида сортировки:

(см. приложение Рисунок 18 Реализация в C)

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

Пирамидальная сортировка (она же сортировка кучей) – классический алгоритм который, пожалуй, должен знать любой программист. Старая добрая «пирамидка» примечательна тем, что в независимости от набора данных у неё одна и та же сложность по времени (причём, очень пристойная) – O(n log n). Лучших и вырожденных случаев для неё нет.

С момента изобретения метода (а в этом году алгоритм празднует свой полувековой юбилей) было немало желающих кардинально оптимизировать процесс накладывания сортирующих куч. Тернарная пирамидальная сортировка, плавная сортировка, сортировка декартовым деревом – вот неполный список инноваций. Перечисленные алгоритмы хотя при тестировании и опережают оригинал по абсолютной скорости кто на 12, а кто и на 25%, в оценке временной сложности всё равно крутятся вокруг O(n log n). При этом данные методы весьма изощрённо реализованы.

Своё видение пирамидальной сортировки предложил и скромный труженик Университета Манитобы Джейсон Моррисон. При этом способ в некоторых случаях по скорости приближается к O(n).

HeapSort

Как работает пирамидальная сортировка?

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

Что есть сортирующее дерево? Это дерево, у которого любой родитель больше (или меньше, смотря в какую сторону оно сортирующее) чем его потомки.

Как из обычного дерева сделать сортирующее дерево? Очень просто – нужно двигаться от потомков вверх к родителям и если потомок больше родителя, то менять местами. Если такой обмен произошёл, опустившегося на один уровень родителя нужно сравнить с потомками ниже – может и там тоже будет повод для обмена.

Преобразовывая неотсортированную часть массива в сортирующее дерево, в итоге в корень «всплывёт» наибольший элемент. Обмениваем максимум с последним ключом неотсортированного подмассива. Структура перестанет быть сортирующим деревом, но в качестве моральной компенсации его неотсортированная часть станет меньше на один узел. К этой неотсортированной части заново применим всю процедуру, то есть преобразуем её в сортирующее дерево с последующей перестановкой найденного максимума в конец. И так действуем до тех пор, пока неотсортированная часть не скукожится до одного-единственного элемента.

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

JSort

Канадский учёный пришёл к выводу, что заново перестраивать кучу для каждого элемента – дорогое удовольствие. Так уж ли необходимо массив из n элементов радикально перелопачивать n раз?

Если для массива построить всего пару куч (нисходящую и восходящую), то это значительно его упорядочит в обоих направлениях.

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

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

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

(см. приложение Рисунок 19 Пример, часть 1)

(см. приложение Рисунок 20 Пример, часть 2)

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

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

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

Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующие друг за другом: «меньшие опорного», «равные» и «большие».

Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.

(см. приложение Рисунок 21 Реализация в C)

2.5 Интроспективная сортировка

Introsort

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

Массивы-убийцы

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

Легендарный учёный Никлаус Вирт предложил для преодоления проблемы выбор опоры осуществлять по принципу «медиана из трёх», т.е. в качестве базового ключа подмассива брать средний по величине элемент из 3-х претендентов: первого элемента подмассиса, последнего элемента подмассива и элемента посередине.

Хотя в абсолютном большинстве случаев это позволяло избежать неприятностей, оно не гарантировало 100%-го решения проблемы. Оставалась возможность специально подобрать такой массив, на котором быстрая сортировка, даже реализованная с помощью принципа «медиана из 3-х», всё равно быстро деградировала.

Если использовать вместо правила «медиана из 3-х» какое-нибудь другое, то это принципиально ничего не меняет — вырожденный случай подбирается в соответствии с конкретной реализацией.

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

Решение проблемы

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

Мюссер подобрал «киллер» из 100 тысяч элементов и протестировал его. Introsort обработал массив в 200 раз быстрее чем QuickSort.

2.6 Придурковатая сортировка

Неэффективная сортировка, представляющая чисто академический интерес.

Метод назван в честь американской комик-группы «Three stooges» («Три придурка»), развлекавшая публику в 30-х-60-х годах прошлого века. Коллектив трио периодически менялся, всего в труппе было 6 актёров за 40 лет существования. В алгоритм заложен элемент абсурда — обычно массив давно отсортирован, но сортировка продолжает безумно метаться по третям списка.

Придурковатая сортировка

Алгоритм

Сравниваем элементы на концах отрезка (первоначально это весь массив). Если на левом конце больше чем на правом, то меняем местами.

Рекурсивно применяем сортировку для первых 2/3 элементов списка.

Рекурсивно применяем сортировку для последних 2/3 элементов списка.

Снова рекурсивно применяем сортировку для первых 2/3 элементов списка.

Глава 3. Прочие алгоритмы сортировки

3.1 Топологическая сортировка

Топологическая сортировка (Topological sort) — один из основных алгоритмов на графах, который применяется для решения множества более сложных задач.

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

Существует несколько способов топологической сортировки — из наиболее известных:

Алгоритм Демукрона

Метод сортировки для представления графа в виде нескольких уровней

Метод топологической сортировки с помощью обхода в глубину

Суть алгоритма

Поиск в глубину или обход в глубину (англ. Depth-first search, сокращенно DFS) — один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них.

Запускаем обход в глубину, и когда вершина обработана, заносим ее в стек. По окончании обхода в глубину вершины достаются из стека. Новые номера присваиваются в порядке вытаскивания из стека.

Цвет: во время обхода в глубину используется 3 цвета. Изначально все вершины белые. Когда вершина обнаружена, красим ее в серый цвет. Когда просмотрен список всех смежных с ней вершин, красим ее в черный цвет.

Думаю будет проще рассмотреть данный алгоритм на примере:

Применение

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

3.2 Внешняя сортировка

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