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

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

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

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

Сортировки сравнения, изучаемые в литературе, являются «основанными на сравнении». ^[1] Элементы a и b могут быть поменяны местами или иным образом переупорядочены алгоритмом только тогда, когда порядок между этими элементами установлен на основе результатов предыдущих сравнений. Это тот случай, когда порядок между a и b может быть получен посредством транзитивного замыкания этих результатов предыдущих сравнений.

Для сортировок на основе сравнения решение о выполнении базовых операций, отличных от сравнений, принимается на основе результатов сравнений. Поэтому во временном анализе количество выполненных сравнений используется для определения верхних оценок количества выполненных базовых операций, таких как обмены или назначения. ^[1]

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

Примеры

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

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

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

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

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

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

function tupleCompare((lefta, leftb, leftc), (righta, rightb, rightc)) если lefta ≠ righta вернуть compare(lefta, righta) иначе если leftb ≠ rightb вернуть compare(leftb, rightb) иначе  вернуть compare(leftc, rightc)

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

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

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

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

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

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

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

\left\lceil \log _{2}(n!)\right\rceil

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

Число сравнений, требуемых алгоритмом сортировки сравнением, увеличивается пропорционально , где — число элементов для сортировки. Эта граница асимптотически узка . $n\log(n)$ $n$

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

2^{f(n)}\geq n!

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

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

Рассматривая первые множители , получаем $n/2$ $n!=n(n-1)\cdots 1$

\log _{2}(n!)\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).

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

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

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

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

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

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

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

невозможно определить, в каком порядке находятся входные данные, используя в среднем менее $log 2 (n!) сравнений.$

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

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

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

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

{\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!}}=\lceil \log _{2}n!\rceil +1-{\frac {2^{\lceil \log _{2}n!\rceil }}{n!}}

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

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

n log n максимальное количество сравнений для размера массива в формате 2^k

Можно легко вычислить для реального алгоритма сортировка-список-слияние (массив сортируется на n-блоки размером 1, объединяется с 1–1 в 2, объединяется 2–2 в 4...).

(1) = = = = = = = =(2) = = = = // max 1 сравнивает (size1+size2-1), 4 раза повторяет для объединения 8 массивов размером 1 и 1 === === === ===(3) = = // максимум 7 сравнений, 2x повторений для объединения 4 массивов размером 2 и 2 === ===  ===== ===== ======= =======(4) // максимум 15 сравнений, 1 раз повторяется для объединения 2 массивов размером 4 и 4Формула извлечения:n = 256 = 2^8 (размер массива в формате 2^k, для упрощения)Вкл = (n-1) + 2(n/2-1) + 4(n/4-1) + 8(n/8-1) + 16(n/16-1) + 32(n/32- 1) + 64(н/64-1) + 128(н/128-1)Вкл = (n-1) + (n-2) + (n-4) + (n-8) + (n-16) + (n-32) + (n-64) + (n-128)On = n+n+n+n+n+n+n+n - (1+2+4+8+16+32+64+128) | 1+2+4... = формула геометрической прогрессии Sn = a1 * (q^i - 1) / (n - 1), n - количество элементов, a1 - первый элементВкл = 8*n - 1 * (2^8 - 1) / (2 - 1)Вкл = 8*n - (2^8 - 1) | 2^8 = пВкл = 8*n - (n - 1)Вкл = (8-1)*n + 1 | 8 = ln(n)/ln(2) = ln(256)/ln(2)Вкл = (ln(n)/ln(2) - 1) * n + 1Пример:n = 2^4 = 16, On ~= 3*nn = 2^8 = 256, На ~= 7*nn = 2^10 = 1,024, На ~= 9*nn = 2^20 = 1.048.576, Вкл ~= 19*n

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

Если список уже близок к сортировке, согласно некоторой мере сортированности, количество сравнений, необходимых для его сортировки, может быть меньше. Адаптивная сортировка использует эту «предварительно отсортированность» и работает быстрее на почти отсортированных входных данных, часто при этом сохраняя ограничение по времени в худшем случае. Примером является адаптивная сортировка кучей , алгоритм сортировки, основанный на декартовых деревьях . Она занимает время , где — среднее значение по всем значениям в последовательности количества переходов последовательности снизу вверх или наоборот. ^[12] $O(n\log n)$ $O(n\log k)$ $к$ $x$ $x$ $x$

Примечания

^[13]

Примечания

^ ab Wilkes, MV (1974-11-01). «Искусство программирования компьютеров, том 3, Сортировка и поиск». The Computer Journal . 17 (4): 324–324. doi :10.1093/comjnl/17.4.324. ISSN 0010-4620.
^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. стр. 191–193. ISBN 0-262-03384-4.
^ Марк Уэллс, Применение языка для вычислений в комбинаторике, Обработка информации 65 (Труды Конгресса IFIP 1965 г.), 497–498, 1966.
^ Марк Уэллс, Элементы комбинаторных вычислений, Pergamon Press, Оксфорд, 1971.
^ Такуми Касаи, Сусаку Савато, Шигеки Ивата, Для сортировки 13 элементов требуется тридцать четыре сравнения, LNCS 792, 260-269, 1994.
^ Марцин Печарски, Сортировка 13 элементов требует 34 сравнений, LNCS 2461, 785–794, 2002.
^ abc Марчин Печарски, Новые результаты в сортировке с минимальным сравнением, Algorithmica 40 (2), 133–145, 2004.
^ Марцин Печарски, Компьютерное исследование частично упорядоченных множеств, докторская диссертация, Варшавский университет, 2006.
^ Peczarski, Marcin (2007). «Алгоритм Форда-Джонсона все еще непревзойден для менее чем 47 элементов». Inf. Process. Lett . 101 (3): 126–128. doi :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.
^ abc Stober, F., & Weiß, A. (2023). Нижние границы для сортировки 16, 17 и 18 элементов. В 2023 Труды симпозиума по разработке алгоритмов и экспериментам (ALENEX) (стр. 201-213). Общество промышленной и прикладной математики
^ Левкопулос, Христос; Петерссон, Ола (1989), «Пирамидная сортировка — адаптированная для предварительно отсортированных файлов», WADS '89: Труды семинара по алгоритмам и структурам данных , Lecture Notes in Computer Science, т. 382, Лондон, Великобритания: Springer-Verlag, стр. 499–509, doi :10.1007/3-540-51542-9_41.
^ Кнут, Дональд Э. (1998). Искусство программирования, том 3: (2-е изд.) сортировка и поиск. США: Addison Wesley Longman Publishing Co., Inc. ISBN 978-0-201-89685-5.

Ссылки

Дональд Кнут . Искусство программирования , том 3: Сортировка и поиск , второе издание. Addison-Wesley, 1997. ISBN 0-201-89685-0 . Раздел 5.3.1: Сортировка с минимальным сравнением, стр. 180–197.