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

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

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

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

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

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

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

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

Примеры

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

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

• Быстрая сортировка
• пирамидальная сортировка
• Шеллсорт
• Идет судьба
• Интросорт
• Сортировка вставкой
• Сортировка выбором
• Пузырьковая сортировка
• Нечетно-четный сорт
• Сорт коктейльного шейкера
• Циклическая сортировка
• Сортировка слиянием-вставкой
• Гладкая сортировка
• Тимсорт
• Блочная сортировка

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

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

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

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

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

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

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

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

н	$\left\lceil \log _{2}(n!)\right\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
13	33	34
14	37	38
15	41	42
16	45	46
17	49	50
18	53	54
19	57	58
20	62	62
21	66	66
22	70	71
н	$\left\lceil \log _{2}(n!)\right\rceil$	$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

Вверху: сравнение нижней границы $\left\lceil \log _{2}(n!)\right\rceil$ к фактическому минимальному количеству сравнений (из OEIS : A036604 ), необходимого для сортировки списка из n элементов (в худшем случае). Внизу: Используя приближение Стирлинга , эта нижняя граница хорошо аппроксимируется формулой $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).$

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

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

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

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

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

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

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

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

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

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

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

${\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 compares (size1+size2-1), 4x repeats to concat 8 arrays with size 1 and 1
   === === === ===

(3)   =       =       // max 7 compares, 2x repeats to concat 4 arrays with size 2 and 2
     ===     ===  
    =====   ===== 
   ======= =======

(4)                   // max 15 compares, 1x repeats to concat 2 arrays with size 4 and 4

Formula extraction:
n = 256 = 2^8 (array size in format 2^k, for simplify)
On = (n-1) + 2(n/2-1) + 4(n/4-1) + 8(n/8-1) + 16(n/16-1) + 32(n/32-1) + 64(n/64-1) + 128(n/128-1)
On = (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... = formula for geometric sequence Sn = a1 * (q^i - 1) / (n - 1), n is number of items, a1 is first item
On = 8*n - 1 * (2^8 - 1) / (2 - 1)
On = 8*n - (2^8 - 1)   | 2^8 = n
On = 8*n - (n - 1)
On = (8-1)*n + 1   | 8 = ln(n)/ln(2) = ln(256)/ln(2)
On = (ln(n)/ln(2) - 1) * n + 1

Example:
n = 2^4 = 16, On ~= 3*n
n = 2^8 = 256, On ~= 7*n
n = 2^10 = 1.024, On ~= 9*n
n = 2^20 = 1.048.576, On ~= 19*n

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

Основная статья: Адаптивная сортировка

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

Ссылки

• Дональд Кнут . Искусство компьютерного программирования , Том 3: Сортировка и поиск , Второе издание. Аддисон-Уэсли, 1997. ISBN   0-201-89685-0 . Раздел 5.3.1: Сортировка по минимальному сравнению, стр. 180–197.