Меню

Сортировка с использованием сравнений



Сортировка сравнения — Comparison sort

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

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

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

Содержание

Примеры

Некоторые из наиболее известных видов сравнения включают:

Пределы производительности и преимущества различных методов сортировки

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

В некоторых списках сортировка сравнения может выполняться быстрее; многие адаптивные сортировки, такие как сортировка вставкой, выполняются за O ( n ) раз в уже отсортированном или почти отсортированном списке. Ω ( п войти п ) нижняя граница относится только к случаю , в котором список вход может быть в любом возможном порядке.

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

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

Сбалансированная троичная нотация позволяет проводить сравнения за один шаг, результат которого будет одним из «меньше», «больше» или «равно».

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

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

Альтернативы

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

Проблема сортировки пар чисел по их сумме также не подчиняется границам Ω ( n ² log n ) (квадрат, полученный в результате объединения в пары); самый известный алгоритм по-прежнему занимает O ( n ² log n ) времени, но только O ( n ²) сравнений.

Количество сравнений, необходимое для сортировки списка

Количество сравнений, которые требует алгоритм сортировки сравнения, увеличивается пропорционально , где — количество элементов для сортировки. Эта оценка асимптотически точна . п журнал ⁡ ( п ) <\ Displaystyle п \ журнал (п)> п <\ displaystyle n>

Учитывая список различных чисел (мы можем предположить это, потому что это анализ наихудшего случая), существует n факториальных перестановок, ровно одна из которых является списком в отсортированном порядке. Алгоритм сортировки должен получить достаточно информации из сравнений, чтобы определить правильную перестановку. Если алгоритм всегда завершается после не более чем f ( n ) шагов, он не может различить более 2 случаев f ( n ), потому что ключи различны и каждое сравнение имеет только два возможных результата. Следовательно,

2 ж ( п ) ≥ п ! <\ Displaystyle 2 ^ <е (п)>\ geq п!> , или эквивалентно ж ( п ) ≥ журнал 2 ⁡ ( п ! ) . <\ displaystyle f (n) \ geq \ log _ <2>(n!).>

Рассматривая первые множители , получаем п / 2 <\ displaystyle n / 2> п ! знак равно п ( п — 1 ) ⋯ 1 <\ Displaystyle п! = п (п-1) \ cdots 1>

журнал 2 ⁡ ( п ! ) ≥ журнал 2 ⁡ ( ( п 2 ) п 2 ) знак равно п 2 журнал ⁡ п журнал ⁡ 2 — п 2 знак равно Θ ( п журнал ⁡ п ) . <\ displaystyle \ log _ <2>(п!) \ geq \ log _ <2>\ left (\ left ( <\ frac <2>> \ right) ^ <\ frac <2>> \ right) = <\ frac <2>> <\ frac <\ log n><\ log 2>> — <\ frac <2>> = \ Theta (n \ log n). > журнал 2 ⁡ ( п ! ) знак равно Ω ( п журнал ⁡ п ) . <\ displaystyle \ log _ <2>(n!) = \ Omega (n \ log n).>

Читайте также:  Алоэ сравнение с папоротником

Это обеспечивает нижнюю границу претензии. Лучшую оценку можно дать с помощью приближения Стирлинга .

Идентичная верхняя граница следует из существования алгоритмов, которые достигают этой границы в худшем случае, таких как heapsort и mergesort .

Приведенный выше аргумент обеспечивает абсолютную , а не только асимптотическую нижнюю границу количества сравнений, а именно сравнений. Эта нижняя граница довольно хороша (к ней можно приблизиться в пределах линейного допуска с помощью простой сортировки слиянием), но известно, что она неточна. Например, но минимальное количество сравнений с элементами сортировки 13 оказалось равным 34. ⌈ журнал 2 ⁡ ( п ! ) ⌉ <\ Displaystyle \ влево \ lceil \ log _ <2>(п!) \ вправо \ rceil> ⌈ журнал 2 ⁡ ( 13 ! ) ⌉ знак равно 33 <\ Displaystyle \ влево \ lceil \ log _ <2>(13!) \ вправо \ rceil = 33>

Определение точного числа сравнений, необходимых для сортировки заданного количества записей, представляет собой вычислительно сложную задачу даже для малых n , и простой формулы для решения неизвестно. Для некоторых из немногих конкретных значений, которые были вычислены, см. OEIS : A036604 .

Нижняя оценка среднего числа сравнений

Аналогичная оценка применяется к среднему количеству сравнений. При условии, что

    все ключи различны, т.е. каждое сравнение даст либо a >b, либо a log 2 ( n !) .

В этом легче всего убедиться, используя концепции теории информации . Энтропия Шеннона такой случайной перестановки в журнале 2 ( п !) Бит. Поскольку сравнение может дать только два результата, максимальный объем предоставляемой информации составляет 1 бит. Следовательно, после k сравнений оставшаяся энтропия перестановки с учетом результатов этих сравнений в среднем составляет не менее log 2 ( n !) — k бит. Для выполнения сортировки необходима полная информация, поэтому оставшаяся энтропия должна быть 0. Отсюда следует, что k в среднем должно быть не меньше log 2 ( n !) .

Нижняя граница, полученная с помощью теории информации, сформулирована как «теоретико-информационная нижняя граница». Теоретико-информационная нижняя оценка верна, но не обязательно является самой сильной нижней оценкой. А в некоторых случаях теоретико-информационная нижняя оценка проблемы может даже быть далека от истинной нижней границы. Например, теоретико-информационная нижняя граница отбора — это тогда, когда сравнения необходимы для состязательного аргумента. Взаимодействие между теоретико-информационной нижней границей и истинной нижней границей во многом похоже на действительную функцию, ограничивающую снизу целочисленную функцию. Однако это не совсем верно, если рассматривать средний случай. ⌈ журнал 2 ⁡ ( п ) ⌉ <\ Displaystyle \ влево \ lceil \ log _ <2>(п) \ вправо \ rceil> п — 1 <\ displaystyle n-1>

Чтобы понять, что происходит при анализе среднего случая, ключ в том, что означает «средний»? Усреднение по чему? Имея некоторые знания в области теории информации, теоретико-информационная нижняя граница усредняет набор всех перестановок в целом. Но любые компьютерные алгоритмы (согласно тому, что считается в настоящее время) должны рассматривать каждую перестановку как отдельный экземпляр проблемы. Следовательно, средняя нижняя граница, которую мы ищем, усредняется по всем индивидуальным случаям.

Для поиска нижней границы недостижимости компьютеров мы применяем модель дерева решений . Давайте перефразируем нашу цель. В модели дерева решений нижняя граница, которая должна отображаться, является нижней границей средней длины путей от корня к листу двоичного дерева -лист (в котором каждый лист соответствует перестановке). Было бы убедительно сказать, что сбалансированное полное двоичное дерево достигает минимума средней длины. После некоторых тщательных вычислений для сбалансированного полного двоичного дерева с листьями средняя длина путей от корня к листу определяется выражением п ! <\ displaystyle n!> п ! <\ displaystyle n!>

( 2 п ! — 2 ⌊ журнал 2 ⁡ п ! ⌋ + 1 ) ⋅ ⌈ журнал 2 ⁡ п ! ⌉ + ( 2 ⌊ журнал 2 ⁡ п ! ⌋ + 1 — п ! ) ⋅ ⌊ журнал 2 ⁡ п ! ⌋ п ! <\ displaystyle <\ frac <(2n! -2 ^ <\ lfloor \ log _ <2>n! \ rfloor +1>) \ cdot \ lceil \ log _ <2>n! \ rceil + (2 ^ <\ lfloor \ log _ <2>n! \ rfloor +1> -n!) \ cdot \ lfloor \ log _ <2>n! \ rfloor> >>

Например, для n = 3 теоретико-информационная нижняя граница для среднего случая составляет примерно 2,58, а средняя нижняя граница, полученная с помощью модели дерева решений, составляет 8/3, примерно 2,67.

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

Источник

Гибридные сортировки

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

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


Статья написана при поддержке компании EDISON.

Мы очень любим теорию алгоритмов! 😉

Давайте быстро вспомним, какие классы бывают у алгоритмов сортировок и в чём особенности каждого из них.

Сортировки обменами


Элементы массива попарно сравниваются друг с другом и производятся обмены для неупорядоченных пар.

Самым эффективным представителем этого класса является легендарная быстрая сортировка.

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


Элементы из неотсортированной части массива вставляются на свои места в отсортированной области.

Из этого класса чаще всего используется сортировка простыми вставками. Хотя этот алгоритм имеет среднюю сложность O(n 2 ), эта сортировка очень быстро работает с почти упорядоченными массивами — на них сложность достигает O(n). Кроме того, эта сортировка является одним из лучших вариантов для обработки малых массивов.

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

Сортировки выбором


В неупорядоченной области выбирается минимальный/максимальный элемент, который переносится в конец/начало неотсортированной части массива.

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

Читайте также:  Какое имя прилагательное имеет степени сравнения вчерашний хитрый лисий зеленеющий

Сортировки слиянием

В массиве берутся отсортированные области и осуществляется их слияние, то есть отсортированные подмассивы поменьше объединяются в общий отсортированный подмассив побольше.

Если два подмассива отсортированы, то их объединение — легко реализуемая и быстрая по времени операция. Обратной стороной медали является то, что на слияние почти всегда требуются расходы на дополнительную память O(n) — хотя известно крайне небольшое количество особо изощрённых вариантов сортировок со слиянием, где расходы по памяти O(1).

Сортировки распределением

Элементы массива распределяются и перераспределяются по классам до тех пор, пока массив не примет отсортированное состояние.

Элементы разбрасываются по группам или в зависимости от их значения (так называемые сортировки подсчётом) или в зависимости от значения отдельных разрядов (это уже поразрядные сортировки).

Вёдерная сортировка также относится к данному классу.

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

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

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

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

Вставка + слияние

Чисто эмпирический вывод гласит о том, что в гибридах чаще всего используется слияние и/или вставки. В большинстве сортировок встречается или тот или другой метод, а то и оба вместе. И этому есть логическое объяснение.

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

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

Что касается вставок, то в гибридных алгоритмах на определённых этапах часто получаются примерно упорядоченные подмассивы, которые лучше всего приводить к окончательному упорядочиванию именно с помощью вставок.

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

Сортировка слиянием-вставкой :: Merge-insertion sort
Алгоритм Форда-Джонсона :: Ford-Johnson algorithm

Слияние + вставки


Очень древний способ, аж 1959 года. Подробно описан в бессмертном труде Дональда Кнута «Искусство программирования», Том 3 «Сортировка и поиск», глава 5 «Сортировка», раздел 5.3 «Оптимальная сортировка», подраздел «Сортировка с минимальным числом сравнений», часть «Сортировка посредством вставок и слияния».

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

Сортировка Тима :: Timsort

Вставки + слияние


Автор Тим Петерс лет 15 назад и сейчас

Эту сортировку на Хабре вспоминают очень часто.
Тезисно: в массиве ищутся почти упорядоченные небольшие подмассивы, для которых применяется сортировка вставками. Затем эти подмассивы объединяются с помощью слияния.

Слияние в TimSort — наиболее интересная часть: классическое восходящее слияние дополнительно оптимизировано для разных ситуаций. Например, известно, что слияние более эффективно проходит, если соединяемые подмассивы примерно одинаковы по размеру. В TimSort если размеры сильно отличаются, то после дополнительных действий происходит уравнивание (можно сказать, что из большего подмассива часть элементов «перетечёт» в меньший, после чего слияние продолжится в стандартном режиме). Также предусмотрены разные коварные ситуации — например, если в одном подмассиве все элементы будут меньше чем в другом. В этом случае сравнение элементов из обоих подмассивов будет проходить вхолостую. Модифицированная процедура слияния вовремя «заметит» такое нежелательное развитие событий и если с помощью бинарного поиска «убедится» в пессимистичном варианте, то произойдёт переключение на более оптимальный вариант обработки.

Читайте также:  Сравнение радар детекторов neoline x cop

В среднем эта сортировка работает чуть медленнее чем 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

Источник