Сравнительная сортировка - Comparison sort

Для сортировки набора немаркированных весов по весу с использованием только весов требуется алгоритм сортировки сравнения.

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

если а ≤ б и б ≤ c тогда а ≤ c (транзитивность)
для всех а и б, а ≤ б или же б ≤ а (связь ).

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

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

Примеры

Быстрая сортировка в действии над списком номеров. Горизонтальные линии - это значения разворота.

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

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

Существуют фундаментальные ограничения на эффективность сортировок для сравнения. Сортировка сравнения должна иметь нижнюю границу среднего регистра Ω (п бревно п) операции сравнения,^[1] который известен как линейный время. Это следствие ограниченной информации, доступной только посредством сравнений, или, говоря иначе, нечеткой алгебраической структуры полностью упорядоченных множеств. В этом смысле сортировка слиянием, heapsort и introsort являются асимптотически оптимальный с точки зрения количества сравнений, которые они должны выполнить, хотя этот показатель не учитывает другие операции. Сортировки без сравнения (такие как примеры, обсуждаемые ниже) могут обеспечить О (п) производительность за счет использования операций, отличных от сравнений, что позволяет им обойти эту нижнюю границу (при условии, что элементы имеют постоянный размер).

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

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

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

функция tupleCompare ((lefta, leftb, leftc), (righta, rightb, rightc)) если lefta ≠ righta возвращаться сравнить (слева, справа) иначе если leftb ≠ rightb возвращаться сравнить (слеваb, справаb) еще        возвращаться сравнить (leftc, rightc)

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

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

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

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

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

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

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

п	${ Displaystyle влево lceil журнал _ {2} (п!) вправо rceil}$	Минимум
1	0	0
2	1	1
3	3	3
4	5	5
5	7	7
6	10	10
7	13	13
8	16	16
9	19	19
10	22	22
11	26	26
12	29	30^[2]^[3]
13	33	34^[4]^[5]^[6]
14	37	38^[6]
15	41	42^[7]^[8]^[9]
16	45	45 или 46^[10]
17	49	49 или 50
18	53	53 или 54
19	57	58^[9]
20	62	62
21	66	66
22	70	71^[6]

п	${ Displaystyle влево lceil журнал _ {2} (п!) вправо rceil}$	${ displaystyle n log _ {2} n - { frac {n} { ln 2}}}$
10	22	19
100	525	521
1 000	8 530	8 524
10 000	118 459	118 451
100 000	1 516 705	1 516 695
1 000 000	18 488 885	18 488 874

Вверху: сравнение нижней границы

{ Displaystyle влево lceil журнал _ {2} (п!) вправо rceil}

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

{ displaystyle n log _ {2} n - { frac {n} { ln 2}}}

.

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

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

{ Displaystyle 2 ^ {е (п)} geq п!}

, или эквивалентно

{ displaystyle f (n) geq log _ {2} (n!).}

Посмотрев на первый ${ displaystyle n / 2}$ факторы ${ Displaystyle п! = п (п-1) cdots 1}$ , мы получаем

{ displaystyle log _ {2} (п!) geq log _ {2} left ( left ({ frac {n} {2}} right) ^ { frac {n} {2} } right) = { frac {n} {2}} { frac { log n} { log 2}} - { frac {n} {2}} = Theta (n log n). }

{ displaystyle log _ {2} (n!) = Omega (n log n).}

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

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

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

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

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

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

все ключи различны, т.е. каждое сравнение даст либо а>б или же а<б, и
вход представляет собой случайную перестановку, выбранную равномерно из множества всех возможных перестановок п элементы

невозможно определить, в каком порядке находится вход с меньшим, чем $бревно 2 (п!)$ сравнения в среднем.

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

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

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

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

{ 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.

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

Примечания

^ Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. С. 191–193. ISBN 0-262-03384-4.
^ Марк Уэллс, Приложения языка для вычислений в комбинаторике, Обработка информации 65 (Труды Конгресса ИФИП 1965 г.), 497–498, 1966.
^ Марк Уэллс, Элементы комбинаторных вычислений, Pergamon Press, Oxford, 1971.
^ Такуми Касаи, Сюсаку Савато, Сигеки Ивата, Тридцать четыре сравнения необходимы для сортировки 13 элементов, LNCS 792, 260-269, 1994.
^ Марчин Печарски, Для сортировки 13 элементов требуется 34 сравнения, LNCS 2461, 785–794, 2002.
^ ^а ^б ^c Марцин Печарски, Новые результаты в сортировке с минимальным сравнением, Алгоритмика 40 (2), 133–145, 2004.
^ Марцин Печарски, Компьютерное исследование поз, докторская диссертация, Варшавский университет, 2006.
^ Печарски, Марцин (2007). «Алгоритм Форда-Джонсона по-прежнему непревзойден для менее чем 47 элементов». Инф. Процесс. Латыш. 101 (3): 126–128. Дои:10.1016 / j.ipl.2006.09.001.
^ ^а ^б Ченг, Вэйи; Лю, Сяогуан; Ванга, банда; Лю, Цзин (октябрь 2007 г.). "最少比较排序问题中 S （15）和 S （19）的解决" [Результаты S (15) и S (19) к задаче сортировки по минимальному сравнению]. Журнал Frontiers of Computer Science and Technology (на китайском языке). 1 (3): 305–313.
^ Печарски, Марцин (3 августа 2011 г.). «К оптимальной сортировке 16 элементов». Acta Universitatis Sapientiae. 4 (2): 215–224. arXiv:1108.0866. Bibcode:2011arXiv1108.0866P.

Алгоритмы сортировки
Теория	Теория вычислительной сложности Обозначение Big O Общий заказ Списки Замена Стабильность Сравнительная сортировка Адаптивная сортировка Сортировочная сеть Целочисленная сортировка X + Y сортировка Трансдихотомическая модель Квантовая сортировка
Обменные сорта	Пузырьковая сортировка Сорт коктейльный шейкер Нечетно-четная сортировка Сортировка гребней Сортировка гномов Быстрая сортировка Slowsort Stooge sort Богосорт
Выборочные сорта	Выборочная сортировка Heapsort Smoothsort Сортировка декартовых деревьев Сортировка турнира Цикл сортировки Сортировка слабой кучи
Вставки	Вставка сортировки Shellsort Сортировка Сортировка дерева Сортировка библиотеки Сортировка терпения
Сортировка слияния	Сортировка слиянием Каскадная сортировка слиянием Осциллирующая сортировка слиянием Полифазная сортировка слиянием
Виды распространения	Американский флаг сортировка Сортировка бисера Ковшовая сортировка Burstsort Счетная сортировка Сортировка интерполяции Сорт голубятни Proxmap сортировка Radix sort Flashsort
Параллельные сортировки	Bitonic сортировщик Сортировка по четным и нечетным дозаторам Сеть попарной сортировки Samplesort
Гибридные сорта	Блокировать сортировку слиянием Сорт Киркпатрика-Райша Тимсорт Интросорт Spreadsort Сортировка слиянием-вставкой
Другой	Топологическая сортировка Предпотопологический порядок Сортировка блинов Сортировка спагетти