Введение
Тип алгоритма сортировки, который работает путем сравнения пар элементов.
Сравнительный алгоритм сортировки — это тип алгоритма сортировки, который считывает элементы списка только посредством одной абстрактной операции сравнения (часто оператор "меньше или равно" или трехстороннее сравнение), определяющей, какой из двух элементов должен идти первым в окончательном отсортированном списке. Единственное требование заключается в том, что оператор формирует полный предзаказ данных, при этом: если a ≤ b и b ≤ c, то a ≤ c (транзитивность); для всех a и b, a ≤ b или b ≤ a (связность). Возможно, что a ≤ b и b ≤ a; в этом случае любой из них может оказаться первым в отсортированном списке. В стабильной сортировке входной порядок определяет отсортированный порядок в этом случае. Сортировки, изучаемые в литературе, являются "основанными на сравнении". Элементы a и b могут быть поменены местами или иным образом переупорядочены алгоритмом только тогда, когда порядок между этими элементами был установлен на основе результатов предыдущих сравнений. Это происходит, когда порядок между a и b может быть выведен посредством транзитивного замыкания этих предыдущих результатов сравнения. Для сортировок, основанных на сравнении, решение о выполнении основных операций, отличных от сравнений, основывается на результатах сравнений. Следовательно, при анализе времени количество выполненных сравнений используется для определения верхней границы оценок количества выполненных основных операций, таких как перестановки или присваивания, что известно как линейно-логарифмическое время. Это является следствием ограниченной информации, доступной только через сравнения, или, иными словами, нечеткой алгебраической структуры полностью упорядоченных множеств. В этом смысле сортировка слиянием, сортировка кучей и интросортировка асимптотически оптимальны с точки зрения количества сравнений, которые им необходимо выполнить, хотя эта метрика не учитывает другие операции. Сортировки, не основанные на сравнении (например, примеры, обсуждаемые ниже), могут достичь производительности O(n), используя операции, отличные от сравнений, что позволяет им обойти эту нижнюю границу (при условии, что элементы имеют постоянный размер). Сравнительные сортировки могут выполняться быстрее на некоторых списках; многие адаптивные сортировки, такие как сортировка вставками, выполняются за время O(n) на уже отсортированном или почти отсортированном списке. Нижняя граница Ω(n log n) применима только в том случае, если входной список может быть в любом возможном порядке. Реальные измерения скорости сортировки могут учитывать способность некоторых алгоритмов оптимально использовать относительно быструю кэшированную компьютерную память, или приложение может выиграть от методов сортировки, при которых отсортированные данные начинают быстро появляться перед пользователем (а затем скорость чтения пользователя будет ограничивающим фактором), в отличие от методов сортировки, при которых вывод недоступен, пока весь список не будет отсортирован. Несмотря на эти ограничения, сравнительные сортировки предлагают заметное практическое преимущество, заключающееся в том, что контроль над функцией сравнения позволяет сортировать множество различных типов данных и точно контролировать способ сортировки списка. Например, обращение результата функции сравнения позволяет сортировать список в обратном порядке; и можно отсортировать список кортежей в лексикографическом порядке, просто создав функцию сравнения, которая сравнивает каждую часть последовательно:
function tupleCompare((lefta, leftb, leftc), (righta, rightb, rightc)) {
if (lefta ≠ righta)
return compare(lefta, righta);
else if (leftb ≠ rightb)
return compare(leftb, rightb);
else
return compare(leftc, rightc);
}
if a ≤ b and b ≤ c then a ≤ c (transitivity)
for all a and b, a ≤ b or b ≤ a (connexity). It is possible that both a ≤ b and b ≤ a; in this case either may come first in the sorted list. In a stable sort, the input order determines the sorted order in this case. Comparison sorts studied in the literature are "comparison based". Elements a and b can be swapped or otherwise re arranged by the algorithm only when the order between these elements has been established based on the outcomes of prior comparisons. This is the case when the order between a and b can be derived via the transitive closure of these prior comparison outcomes. For comparison based sorts the decision to execute basic operations other than comparisons is based on the outcome of comparisons. Hence in a time analysis the number of executed comparisons is used to determine upper bound estimates for the number of executed basic operations such as swaps or assignments. which is known as linearithmic time. This is a consequence of the limited information available through comparisons alone — or, to put it differently, of the vague algebraic structure of totally ordered sets. In this sense, mergesort, heapsort, and introsort are asymptotically optimal in terms of the number of comparisons they must perform, although this metric neglects other operations. Non comparison sorts (such as the examples discussed below) can achieve O(n) performance by using operations other than comparisons, allowing them to sidestep this lower bound (assuming elements are constant sized). Comparison sorts may run faster on some lists; many adaptive sorts such as insertion sort run in O(n) time on an already sorted or nearly sorted list. The Ω(n log n) lower bound applies only to the case in which the input list can be in any possible order. Real world measures of sorting speed may need to take into account the ability of some algorithms to optimally use relatively fast cached computer memory, or the application may benefit from sorting methods where sorted data begins to appear to the user quickly (and then user's speed of reading will be the limiting factor) as opposed to sorting methods where no output is available until the whole list is sorted. Despite these limitations, comparison sorts offer the notable practical advantage that control over the comparison function allows sorting of many different datatypes and fine control over how the list is sorted. For example, reversing the result of the comparison function allows the list to be sorted in reverse; and one can sort a list of tuples in lexicographic order by just creating a comparison function that compares each part in sequence:
function tupleCompare((lefta, leftb, leftc), (righta, rightb, rightc))
if lefta ≠ righta
return compare(lefta, righta)
else if leftb ≠ rightb
return compare(leftb, rightb)
else
return compare(leftc, rightc)
Сравнительные сортировки, как правило, легче адаптируются к сложным порядкам, таким как порядок чисел с плавающей запятой. Кроме того, как только функция сравнения написана, любой алгоритм сравнительной сортировки может быть использован без изменений; сортировки, не основанные на сравнении, обычно требуют специализированных версий для каждого типа данных. Эта гибкость, в сочетании с эффективностью вышеупомянутых алгоритмов сравнительной сортировки на современных компьютерах, привела к широкому предпочтению сравнительных сортировок в большинстве практических задач.
Альтернативы
Некоторые задачи сортировки допускают решение, строго более быстрое, чем оценка Ω(n log n) для сортировки сравнением, используя сортировки без сравнения; примером является сортировка целых чисел, где все ключи – целые числа. Когда ключи образуют небольшой (по сравнению с n) диапазон, сортировка подсчётом является алгоритмом, работающим за линейное время. Другие алгоритмы сортировки целых чисел, такие как поразрядная сортировка, не являются асимптотически быстрее сортировки сравнением, но могут быть быстрее на практике. Задача сортировки пар чисел по их сумме также не подчиняется оценке Ω(n² log n) (квадрат возникает из-за образования пар); лучший известный алгоритм всё ещё требует O(n² log n) времени, но только O(n²) сравнений.