Требуется ли транзитивность для алгоритма сортировки

14

Можно ли использовать алгоритм сортировки с нетранзитивным сравнением, и если да, почему транзитивность указана в качестве требования для сортировки компараторов?

Фон:

Алгоритм сортировки обычно сортирует элементы списка в соответствии с функцией сравнения C (x, y), с

$\begin{array}{ll} C (x, y) = {\begin{cases} - 1 & if x ≺ y \\ 0 & if x \sim y \\ + 1 & if x ≻ y \end{cases} \end{array}$

Требования к этому компаратору, насколько я понимаю, следующие:
- рефлексивный: $\forall x: C(x,x)=0$
- антисимметричный: $\forall x,y: C(x,y) = - C(y,x)$
- переходный: $\forall x,y,z, a: C(x,y)=a \land C(y,z)=a \Rightarrow C(x,z)=a$
- C (x, y) определяется для всех x и y, а результаты зависят только от x и y
(Эти требования всегда перечислены по-разному в разных реализациях, поэтому я не уверен, что понял их правильно)

Теперь я задаюсь вопросом о «толерантной» функции компаратора, которая принимает числа x, y как похожие, если : $|x - y| \le 1$

\begin{array}{ll} С (Икс, Y) знак равно {\begin{cases} - 1 & если Икс < Y - 1 \\ 0 & если | Икс - Y | \leq 1 \\ + 1 & если Икс > Y + 1 \end{cases} \end{array}

$\begin{array}{ll} C(x,y) = \begin{cases} -1 & {\text{if}}\ x\lt y-1 \\ 0 & {\text{if}}\ |x - y| \le 1 \\ +1 & {\text{if}}\ x\gt y+1 \\ \end{cases} \end{array}$

Примеры: оба [ 1, 2, 3, 4, 5]и [1, 4, 3, 2, 5]правильно отсортированы в порядке возрастания согласно толерантному компаратору ( $C(x,y) \le 0$ если x стоит перед y в списке),
но [1, 4, 2, 3, 5]это не так, поскольку C (4,2) = 1

Этот толерантный компаратор является рефлексивным и антисимметричным, но не транзитивным.

т.е. C (1,2) = 0, c (2,3) = 0, но C (1,3) = -1, нарушая транзитивность

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

Поэтому транзитивность в этом случае не требуется? И есть менее строгий вариант транзитивности , что является требуется для сортировки на работу?

Смежные вопросы:

Почему антисимметрия необходима для сравнения? (об антисимметрии)
Алгоритмы сортировки, которые принимают случайный компаратор (о случайном C (x, y))
OrderBy с нетранзитивным IComparer (об алгоритме сортировки c #, мной)

algorithms sorting quicksort transitivity HugoRune
источник

Я думаю, что быстрая сортировка с «всегда выбирать середину» для оси не удалась бы с помощью этого компаратора на [3, 2, 1].

Г. Бах

2

Я подозреваю, что некоторый нетранзитивный компаратор, используемый в каком-либо алгоритме сортировки, может вызвать бесконечный цикл.

Каролис Юоделе

1

a_{i} \leq a_{i + 1}

$a_i \leq a_{i+1}$

a_{i} \leq a_{j}

$a_i \leq a_j$

i \leq j

$i \leq j$

@ G.Bach Я думаю, что на самом деле быстрая сортировка завершится неудачей, если в вашем массиве будет n раз 3, один раз 2, n раз 1, а середина 2 используется в качестве первого стержня, независимо от того, что произойдет после этого.

gnasher729

11

Вы спросили: Можем ли мы запустить алгоритм сортировки, используя его нетранзитивный компаратор?

Ответ: конечно. Вы можете запустить любой алгоритм с любым входом.

Тем не менее, вы знаете правило: Garbage In, Garbage Out. Если вы запустите алгоритм сортировки с нетранзитивным компаратором, вы можете получить бессмысленный вывод. В частности, нет гарантии, что выходные данные будут «отсортированы» в соответствии с вашим компаратором. Таким образом, запуск алгоритма сортировки с нетранзитивным компаратором вряд ли будет полезен так, как вы, вероятно, надеялись.

$[3, 2, 1]$

DW
источник

1

моя первая мысль была о том , что список [3,2,1] находится в отсортированном порядке в соответствии с моим компаратором, поэтому, конечно, своего рода должен оставить его без изменений; но я мог использовать неправильное определение сортировки. Я просто сравниваю каждый элемент с его прямыми соседями, но это может быть слишком слабым ограничением для рассмотрения отсортированного списка

HugoRune

4

@HugoRune Ну, это интересный момент. Что вы имеете в виду под сортировкой ? Если вы можете показать, что алгоритм сортировки будет прерван при наличии нетранзитивного компаратора, и что всякий раз, когда алгоритм завершает работу, какое-то условие выполняется, и это условие является тем, что вы принимаете за сортировку ... тогда, конечно, этот алгоритм будет сортировать ваш список каждый раз, для этого определения сортировки . Если компаратор не транзитивен, может не иметь смысла принимать определение отсортированного, которое требует попарного сравнения всех элементов в отсортированном списке.

Patrick87

3

@HugoRune, с "сравниваются только соседи", вам, вероятно, понадобится пользовательская сортировка. Стандартные алгоритмы предполагают транзитивность, чтобы избежать избыточных сравнений. Или вы можете встроить свой нетранзитивный заказ в переходный. Или, может быть, вы ищете что-то вроде топологической сортировки ?

vonbrand

Я столкнулся с этим некоторое время назад и обнаружил, что сортировка пузырьков на самом деле работает просто отлично, поскольку она сравнивает только смежные элементы.

Mooing Duck

4

Учитывая набор элементов и бинарное отношение порядка, требуется транзитивность, чтобы полностью упорядочить элементы. Фактически, транзитивность требуется даже для определения частичного порядка элементов. http://en.m.wikipedia.org/wiki/Total_order

Вам нужно гораздо более широкое определение того, что означает «отсортированный», чтобы сортировать элементы без транзитивности. Трудно быть последовательным. Другой ответ гласит: «В частности, нет никакой гарантии, что результат будет« отсортирован »в соответствии с вашим компаратором». Но мы можем сказать что-то гораздо более сильное. Вам гарантируется, что вывод не отсортирован в соответствии с вашим компаратором.

$a<b$ $b<c$ $c<a$

Джо
источник

1

Я интерпретировал вопрос, чтобы задавать вопрос о сортировке с использованием частичных порядков (так, чтобы сравнения, которые говорят, что вещи неравны, были транзитивными, а те, которые относятся к элементам, неразличимы, - нет). Сортировка на основе частичного упорядочения иногда полезна, но в худшем случае требует сравнения N (N-1) / 2. Любой алгоритм сортировки, который в худшем случае делает сравнения меньше, чем N (N-1) / 2, не сможет правильно ранжировать частично упорядоченные элементы по причинам, описанным в моем ответе.

суперкат

2

Звучит так, будто вы хотите расположить предметы так, чтобы все различимые ранжировки были правильными, но близкие предметы можно было бы считать «неразличимыми». Можно разработать алгоритмы сортировки, которые будут работать с такими сравнениями, но если нет ограничений на то, сколько сравнений может сообщить, что все неразличимо, невозможно избежать того, чтобы они требовали N (N-1) / 2 сравнений. Чтобы понять почему, выберите какое-нибудь число N и любой алгоритм сортировки, который делает меньше чем N (N-1) / 2 сравнений. Затем заполните список L [0..N-1], установив для каждого элемента L [I] значение I / N и «отсортируйте» его с помощью компаратора (минимальное значение будет 0, а максимальное (N-1) / N). , поэтому разница будет (N-1) / N, что меньше 1).

Поскольку существует N (N-1) / 2 пары элементов, которые можно сравнивать, и сортировка не выполняла такого большого количества сравнений, должна быть какая-то пара элементов, которые не сравнивались напрямую друг с другом. Замените тот, который в итоге был отсортирован первым на 1, а другой на -1 / N, верните все элементы в исходное положение и повторите операцию сортировки. Каждая операция сравнения будет давать ноль, так же как и в первый раз, поэтому будут выполняться одни и те же сравнения, и элементы окажутся в одной и той же последовательности. Чтобы список был правильно отсортирован, «1» придется сортировать после «-1 / N» (поскольку они отличаются более чем на один), но поскольку алгоритм сортировки никогда не сравнивает эти два элемента непосредственно друг с другом, он не было бы никакого способа узнать это.

Supercat
источник

0

Заполните массив из n элементов значениями n, n-1, n-2, ..., 2, 1. Затем попытайтесь отсортировать, используя алгоритм "прямой вставки". Вы обнаружите, что каждый элемент считается равным элементу непосредственно перед ним, и поэтому не перемещается. Результатом «сортировки» является тот же массив.

gnasher729
источник

Требуется ли транзитивность для алгоритма сортировки

Ответы: