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

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

если 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)) if lefta ≠ righta return Compare(lefta, righta) else, если leftb ≠ rightb return Compare(leftb, rightb) else  return 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}}

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

Учитывая список различных чисел (мы можем предположить это, потому что это анализ наихудшего случая), существуют факториальные перестановки, ровно одна из которых является списком в отсортированном порядке. Алгоритм сортировки должен получить достаточно информации от сравнений, чтобы определить правильную перестановку. Если алгоритм всегда завершается после большинства шагов, он не может различать больше случаев, поскольку ключи различны и каждое сравнение имеет только два возможных результата. Поэтому, $п$ ${\ displaystyle 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) = = = = // максимум 1 сравнивает (размер1+размер2-1), 4 раза повторяется для объединения 8 массивов с размером 1 и 1 === === === ===(3) = = // максимум 7 сравнений, 2x повторений для объединения 4 массивов размером 2 и 2 === ===  ===== ===== ======= =======(4) // максимум 15 сравнений, 1x повторяется для объединения 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)Вкл = 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, Вкл ~= 3*nn = 2^8 = 256, Вкл ~= 7*nn = 2^10 = 1,024, Вкл ~= 9*nn = 2^20 = 1.048.576, Вкл ~= 19*n

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

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

Примечания

^[13]

Примечания

^ Аб Уилкс, М.В. (1 ноября 1974 г.). «Искусство компьютерного программирования, Том 3, Сортировка и поиск». Компьютерный журнал . 17 (4): 324–324. дои : 10.1093/comjnl/17.4.324. ISSN 0010-4620.
^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. стр. 191–193. ISBN 0-262-03384-4.
^ Марк Уэллс, Применение языка вычислений в комбинаторике, Information Processing 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.
^ Печарски, Марцин (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.
^ abc Стобер, Ф., и Вайс, А. (2023). Нижние границы для сортировки 16, 17 и 18 элементов. В 2023 г. материалы симпозиума по алгоритмической разработке и экспериментам (ALENEX) (стр. 201–213). Общество промышленной и прикладной математики
^ Левкопулос, Христос; Петерссон, Ола (1989), «Пирамичная сортировка — адаптированная для предварительно отсортированных файлов», WADS '89: Материалы семинара по алгоритмам и структурам данных , Конспекты лекций по информатике, том. 382, Лондон, Великобритания: Springer-Verlag, стр. 499–509, номер документа : 10.1007/3-540-51542-9_41..
^ Кнут, Дональд Э. (1998). Искусство компьютерного программирования, том 3: (2-е изд.) Сортировка и поиск. США: ISBN Addison Wesley Longman Publishing Co., Inc. 978-0-201-89685-5.

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

Примеры

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

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

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

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

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

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

Примечания

Примечания

Рекомендации