Лучший алгоритм сортировки для случая, когда многие объекты имеют отношения «не заботятся» друг о друге

Question

У меня необычный случай сортировки, в котором мое прибегание к поиску оказалось мало. Вот параметры:

1) Контейнер произвольного доступа. (Вектор C ++)
2) Обычно небольшой векторный размер (менее 32 объектов)
3) Многие объекты имеют отношения «не заботятся» относительно друг друга, но они не равны. (т.е. им не важно, какой из них появится первым в конечном отсортированном векторе, но они могут сравниваться по-разному с другими объектами.) Если выразить это третьим способом (если это все еще неясно), функция сравнения для 2 объектов может вернуть 3 результата: «заказ правильный», «заказ нужно перевернуть» или «все равно».
4) Равенство возможно, но будет очень редко. (Но это, вероятно, будет рассматриваться как любой другой "не заботиться".
5) Оператор сравнения намного дороже, чем движение объекта.
6) Нет разницы в скорости сравнения для определения того, что объекты заботятся или не заботятся друг о друге. (т.е. я не знаю способа сделать более быстрое сравнение, которое просто говорит, заботятся ли два объекта друг о друге.)
7) Случайный стартовый порядок.

Answer 1

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

«Не важно» хитроумно, так как большинство алгоритмов сортировки зависят от строгого упорядочения значения сортировки - если A «меньше или равно» B, а B «меньше или равно» C, то он предполагает, что A меньше или равно C - в вашем случае, если A «не заботится» о B, но заботится о C, но B меньше, чем C, то что вы возвращаете для сравнения AB, чтобы гарантировать А будет сравниваться с С?

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

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

[Если операция сравнения особенно дорогая, вам лучше начать с середины и сканировать в одном направлении, пока не достигнете одной границы, а затем выбрать, будет ли найдена другая граница, движущаяся от этой границы, или средняя точка. ... это, вероятно, уменьшит количество сравнений, но, прочитав то, что вы говорите о своих требованиях, вы не сможете, скажем, использовать бинарный поиск, чтобы найти правильное место для вставки каждой записи]

Да, это в основном O (n ^ 2), но для небольшого массива это не должно иметь значения, и вы можете доказать, что ответы верны. Затем вы можете увидеть, будут ли другие сортировки работать лучше, но если вы не сможете вернуть правильный порядок для любой пары, то вы получите странные результаты ...

Answer 2

Вы не можете выполнить сортировку с "пофиг", скорее всего, это испортит порядок элементов. Пример:

list = {A, B, C};
where:
A dont care B
B > C
A < C

Таким образом, даже если между A и B не имеет значения, B должно быть больше, чем A, или одно из них будет ложным: B> C или A

Answer 3

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

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

Если у вас много «безразличных» значений (т. Е. Если в вашем графике частичного упорядочения имеется только субквадратичное число ребер), это будет намного быстрее, чем при обычной сортировке - однако, если вы этого не сделаете, алгоритм будет квадратичным!

Answer 4

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