Как все уже знают, в основу сортировки могут быть положены обмены, вставки, выбор, слияние и распределение.
Но если в алгоритме комбинируются разные методы, то тогда он относится к классу гибридных сортировок.
Давайте быстро вспомним, какие классы бывают у алгоритмов сортировок и в чём особенности каждого из них.
Статья написана при поддержке компании EDISON.
Мы занимаемся доработкой и сопровождением сайтов на 1С-Битрикс, а также разработкой мобильных приложений Android и iOS.
Мы очень любим теорию алгоритмов! ;-)
Сортировки обменами
Элементы массива попарно сравниваются друг с другом и производятся обмены для неупорядоченных пар.
Самым эффективным представителем этого класса является легендарная быстрая сортировка.
Сортировки вставками
Элементы из неотсортированной части массива вставляются на свои места в отсортированной области.
Из этого класса чаще всего используется сортировка простыми вставками. Хотя этот алгоритм имеет среднюю сложность O(n2), эта сортировка очень быстро работает с почти упорядоченными массивами — на них сложность достигает O(n). Кроме того, эта сортировка является одним из лучших вариантов для обработки малых массивов.
Сортировка с помощью двоичного дерева поиска тоже относится к данному классу.
Сортировки выбором
В неупорядоченной области выбирается минимальный/максимальный элемент, который переносится в конец/начало неотсортированной части массива.
Сортировки простым выбором работают весьма медленно (в среднем O(n2)), но в этом классе есть непростая сортировка кучей (она же пирамидальная сортировка), которая имеет сложность по времени O(n log n) — и, что очень ценно, у этой сортировки нет вырожденных случаев, каковы бы ни были входящие данные. Лучших случаев для входящих данных, у этой сортировки, кстати, тоже нет.
Сортировки слиянием
В массиве берутся отсортированные области и осуществляется их слияние, то есть отсортированные подмассивы поменьше объединяются в общий отсортированный подмассив побольше.
Если два подмассива отсортированы, то их объединение — легко реализуемая и быстрая по времени операция. Обратной стороной медали является то, что на слияние почти всегда требуются расходы на дополнительную память O(n) — хотя известно крайне небольшое количество особо изощрённых вариантов сортировок со слиянием, где расходы по памяти O(1).
Сортировки распределением
Элементы массива распределяются и перераспределяются по классам до тех пор, пока массив не примет отсортированное состояние.
Элементы разбрасываются по группам или в зависимости от их значения (так называемые сортировки подсчётом) или в зависимости от значения отдельных разрядов (это уже поразрядные сортировки).
Вёдерная сортировка также относится к данному классу.
Особенностью сортировок распределением является то, что они или вообще не используют попарные сравнения элементов между собой, или таковые сравнения присутствуют в незначительной мере. Поэтому сортировки распределением часто опережают по скорости, например, быструю сортировку. С другой стороны, сортировки распределением часто требуют много дополнительной памяти, так как группы постоянно перераспределяемых элементов надо где-то хранить.
Очень часты ведутся споры о том, какая сортировка является самой лучшей, но в том-то и дело, что идеального алгоритма на все случаи жизни нет и быть не может. Например, быстрая сортировка действительно очень быстрая (но не самая быстрая) в большинстве ситуаций, но и для неё попадаются вырожденные случаи, в которых происходит крах. Сортировка простыми вставками медленная, но для почти упорядоченных массивов запросто обойдёт другие алгоритмы. Сортировка кучей работает вполне быстро при любых входящих данных, но не настолько быстро как другие сортировки при определённых условиях и нет возможности пирамиду ускорить. Сортировка слиянием медленнее, чем быстрая сортировка, однако если в массиве есть отсортированные подмассивы, то быстрее произвести их слияние, чем досортировывать быстрой сортировкой. Если в массиве много повторяющихся элементов или сортируем строки, то, скорее всего, сортировка распределением — наилучший вариант. Каждый метод особенно хорош в своей самой благоприятной ситуации.
И тем не менее, программисты продолжают изобретать самые быстрые в мире сортировки, синтезируя наиболее эффективные методы из разных классов. Давайте поглядим, насколько успешно у них это выходит.
Поскольку в статье упоминается много нетривиальных алгоритмов, я лишь кратко освещаю основные принципы их работы, не перегружая статью анимациями и подробными объяснениями. В дальнейшем будут отдельные статьи, где будут и «мультики» для каждого алгоритма и обстоятельно разобранные тонкие нюансы.
Вставка + слияние
Чисто эмпирический вывод гласит о том, что в гибридах чаще всего используется слияние и/или вставки. В большинстве сортировок встречается или тот или другой метод, а то и оба вместе. И этому есть логическое объяснение.
Изобретатели сортировок зачастую стремятся к созданию параллельных алгоритмов, одновременно упорядочивающих разные участки массива. Лучший способ как поступить с несколькими отсортированными подмассивами — это произвести их слияние — так будет быстрее всего.
В современных алгоритмах часто используется рекурсия. При рекурсивном спуске массив делится обычно на две части, на самом нижнем уровне происходит упорядочивание массива. При возвращении на более высокие уровни рекурсии при этом ставится вопрос объединения отсортированных на нижних уровнях подмассивах.
Что касается вставок, то в гибридных алгоритмах на определённых этапах часто получаются примерно упорядоченные подмассивы, которые лучше всего приводить к окончательному упорядочиванию именно с помощью вставок.
В этой группе собраны гибридные сортировки, в которых есть и слияние и вставки, причём эти методы применяются очень даже по-разному.
Сортировка слиянием-вставкой :: Merge-insertion sort
Алгоритм Форда-Джонсона :: Ford-Johnson algorithm
Слияние + вставки
Очень древний способ, аж 1959 года. Подробно описан в бессмертном труде Дональда Кнута «Искусство программирования», Том 3 «Сортировка и поиск», глава 5 «Сортировка», раздел 5.3 «Оптимальная сортировка», подраздел «Сортировка с минимальным числом сравнений», часть «Сортировка посредством вставок и слияния».
Сортировка сейчас не имеет практического значения, однако интересна тем, кто любит теорию алгоритмов. Рассмотрена задача нахождения способа, как с наименьшим количеством сравнений отсортировать n элементов. Предлагается нетривиальная эвристическая модификация сортировки вставкой (такой вставки Вы больше нигде не встретите) с использованием чисел Якобсталя, для того чтобы количество сравнений свести к минимуму. На сегодняшний день к тому же известно, что это не самый оптимальный вариант и можно ещё более ловко извернуться и обойтись ещё меньшим количеством сравнений. В общем, эталонная академическая сортировка — практической пользы нет, но для ценителей жанра разбирать подобные хитромудрости с алгебраическим уклоном одно удовольствие.
Сортировка Тима :: Timsort
Вставки + слияние
Автор Тим Петерс лет 15 назад и сейчас
Эту сортировку на Хабре вспоминают очень часто.
Тезисно: в массиве ищутся почти упорядоченные небольшие подмассивы, для которых применяется сортировка вставками. Затем эти подмассивы объединяются с помощью слияния.
Слияние в TimSort — наиболее интересная часть: классическое восходящее слияние дополнительно оптимизировано для разных ситуаций. Например, известно, что слияние более эффективно проходит, если соединяемые подмассивы примерно одинаковы по размеру. В TimSort если размеры сильно отличаются, то после дополнительных действий происходит уравнивание (можно сказать, что из большего подмассива часть элементов «перетечёт» в меньший, после чего слияние продолжится в стандартном режиме). Также предусмотрены разные коварные ситуации — например, если в одном подмассиве все элементы будут меньше чем в другом. В этом случае сравнение элементов из обоих подмассивов будет проходить вхолостую. Модифицированная процедура слияния вовремя «заметит» такое нежелательное развитие событий и если с помощью бинарного поиска «убедится» в пессимистичном варианте, то произойдёт переключение на более оптимальный вариант обработки.
В среднем эта сортировка работает чуть медленнее чем QuickSort, однако если входящий массив содержит достаточное количество упорядоченных подпоследовательностей элементов, то скорость существенно повышается и тут TimSort идёт впереди планеты всей.
Сортировка блочным слиянием :: Block merge sort
Вики-сортировка :: Wiki-sort
Сортировка святого Грааля :: Grailsort
Вставки + слияние + вёдра
Анимация сортировки блочным слиянием из Википедии.
Это весьма свежий (2008 год) и в то же время очень перспективный алгоритм. Дело в том, что относительно весомой проблемой слияния является затраты на дополнительную память. Обычно, там где слияние — там и сложность по памяти O(n).
Но WikiSort устроен так, что слияние происходит без использования дополнительной памяти — среди сортировок слиянием в этом плане это очень редкий экземпляр. Кроме того алгоритм является стабильным. Ну и, если обычная сортировка слиянием имеет лучшую алгоритмическую скорость O(n log n), то у вики-сортировки этот показатель равен O(n). До недавнего времени считалось, что сортировка слиянием с таким набором характеристик невозможна в принципе, но китайские программисты всех удивили.
Алгоритм сильно сложен, чтобы его пояснить в паре предложений. Но когда-нибудь о нём напишу отдельную хабрастатью.
Изначально алгоритм безлико назывался Block Merge Sort однако с лёгкой руки Тима Петерса, который подробно изучал сортировку (на предмет того, стоит ли некоторые её идеи перенести в TimSort) к ней прилепилось название WikiSort.
Безвременно ушедший от нас хабраюзер Mrrl самостоятельно несколько лет работал над сортировкой слиянием которая была бы одновременно быстрой при любых входящих данных, экономичной по памяти и устойчивой. Его творческие поиски увенчались успехом и разработанный алгоритм он несколько позже назвал сортировкой святого Грааля (так как она удовлетворяет всем высоким требованиям «идеальной сортировки»). Большинство идей этого алгоритма похожи на то, что реализовано в WikiSort, хотя эти сортировки не идентичны и разработаны независимо друг от друга.
Сортировка с помощью хеш-таблицы :: Hash table sort
Распределение + вставки + слияние
Массив рекурсивно делится пополам, пока количество элементов в получаемых подмассивах не достигнет некоторого порогового значения. На самом нижнем уровне рекурсии происходит приблизительное распределение (с использованием хеш-таблицы) и сортировка подмассива вставками. Затем происходит рекурсивный возврат на более высокие уровни, отсортированные половинки объединяются посредством слияния.
Чуть более подробно об этом алгоритме я рассказывал месяц назад.
Быстрая сортировка как основная
После слияния и вставки третье место в гибридном хит-параде прочно удерживает всеми любимая быстрая сортировка.
Это очень эффективный алгоритм, однако и для него есть вырожденные случаи. Некоторые изобретатели пытаются сделать QuickSort полностью неуязвимой к любым плохим входящим данным и предлагают её дополнить сильными идеями из других сортировок.
Интроспективная сортировка :: Introsort, Introspective sort, std::sort
Быстрая + куча + вставки
Сортировка кучей работает несколько медленнее, чем быстрая сортировка, но при этом у неё в отличие от QuickSort нет вырожденных случаев — средняя, лучшая и худшая алгоритмическая сложность по времени O(n log n).
Поэтому Дэвид Мюссер предложил обезопасится при быстрой сортировке — если наблюдается слишком большой уровень вложенности, то это расценивается как атака на систему, которой подсунули «плохой» массив. Происходит переключение на сортировку кучей, которая не мегабыстро, но и не медленно справится
В C++ есть алгоритм std::sort, который является реализацией интроспективной сортировки. Небольшое дополнение — если на очередном уровне рекурсии
Многомерная сортировка :: Multikey sort
Порязрядная быстрая сортировка :: Radix quick sort
Быстрая + разряды
Быстрая сортировка, только сравниваются друг с другом не значения элементов массива, а их отдельные разряды (сначала таким образом упорядочиваем старшие разряды, от них двигаемся к младшим).
Или так — это поразрядная сортировка по старшим разрядам, упорядочивание внутри очередного разряда осуществляется по алгоритму быстрой сортировки.
Сортировка разбросами :: Spreadsort
Быстрая + слияние + вёдра + разряды
Гештальт из быстрой сортировки, сортировки слиянием, вёдерной сортировки и поразрядной сортировки.
В двух словах не объяснить. Этот алгоритм подробно разберём в одной из следующих статей.
Прочие гибриды
Сортировка подсчётом/деревом :: Tree-counting sort
Подсчёт + дерево
Алгоритм, предложенный хабрапользователем AlexanderUsatov. Сортировка подсчётом, количества подсчитываемых ключей хранятся в сбалансированном дереве.
J-сортировка :: J-sort
Куча + вставки
Про эту сортировку я уже писал 5 лет назад. Всё достаточно просто — сначала в массиве нужно однократно построить невозрастающую кучу, а затем сделать с точностью до наоборот — однократно построить неубывающую. В результате первой операции минимум окажется на первом месте массива, а небольшие элементы в целом значительно переместятся в начало. Во втором случае максимум окажется на последнем месте, а крупные элементы мигрируют в направлении конца массива. В общем получаем почти отсортированный массив, с которым мы что делаем? Правильно — досортировываем вставками.
Ссылки
Merge-insertion, Block-merge, Tim, Introspective, Spread, Multikey
Grail
Грааль, Хеш-таблица, Подсчёт/дерево, JСтатьи серии:
- Excel-приложение AlgoLab.xlsm
- Сортировки обменами
- Сортировки вставками
- Сортировки выбором
- Сортировки слиянием
- Сортировки распределением
- Гибридные сортировки
- Сортировка слиянием-вставкой
- Сортировка Тима
- Вики-сортировка
- Сортировка разбросами
OasisInDesert
Отличная статья. Спасибо.