Нет ли алгоритма сортировки со всеми конкретными желаемыми свойствами?

22

На сайте Алгоритмы сортировки делается следующее заявление:

Идеальный алгоритм сортировки будет иметь следующие свойства:

  • Стабильный: равные ключи не переупорядочены.
  • Работает на месте, требуя дополнительного пространства.O(1)
  • Сравнение ключей в худшем случае .O(n⋅lg⁡(n))
  • В худшем случае свопы.O(n)
  • Адаптивный: Ускоряется до когда данные почти отсортированы или когда уникальных ключей мало.O(n)

Не существует алгоритма, который обладает всеми этими свойствами, и поэтому выбор алгоритма сортировки зависит от приложения.

У меня вопрос, правда ли, что

нет алгоритма [сортировки], который имеет все эти свойства

и если да, то почему? Что в этих свойствах делает невозможным их одновременное выполнение?

algorithms sorting Джеймс Фолкон
источник
4
Они, вероятно, просто означают, что ни один из известных алгоритмов сортировки не обладает всеми этими свойствами.
Юваль Фильмус
3
Существует ли хотя бы одно собрание на основе сравнения 3 и 4?
седобородый
4
@JohnFeminella Требуется хотя бы сравнение , но как это говорит нам о количестве перестановок? Ω(n⋅log⁡(n))
Том ван дер Занден
2
@JohnFeminella Nitpick: «лучше, чем » - пустое утверждение. Вы должны использовать или если хотите поговорить о нижних границах. Ω ΘO(_)ΩΘ
Рафаэль
1
Любой алгоритм сортировки можно сделать стабильным, добавив в качестве вторичного ключа исходную позицию элемента. Тем не менее, это делает его не на месте, так как потребовалось бы O (n) дополнительной памяти.
Джованни Ботта

Ответы:

6

WikiSort и GrailSort - два сравнительно недавних алгоритма, которые позволяют проводить стабильные сравнения ключей худшем случае . К сожалению, я не понимаю их достаточно хорошо, чтобы знать, приближаются ли они к O ( n ) перестановкам или являются адаптивными, поэтому я не знаю, нарушают ли они четвертое и пятое условия, которые у вас есть.О(N Lграмм(N))О(N)

Посмотрев на статью «Стабильное слияние на основе коэффициентов», выполненную Пок-Соном Кимом и Арне Куцнером, на которую ссылается страница WikiSort GitHub, Ким и Куцнер утверждают, что у них есть операция «слияния», которая есть (WikiSort - это вариант Mergesort), но я не уверен, переводит ли это на WikiSort сO(n)перестановками. Считается, что GrailSort работает быстрее (на странице WikiSort GitHub), поэтому я могу предположить, что, скорее всего, оба они имеютO(n) вхудшем случаеи являются адаптивными.О(м(Nм+1))О(N)О(N)

Если кому-то удастся понять WikiSort и / или GrailSort, я был бы признателен, чтобы они также ответили на мой открытый вопрос об этом.

user834
источник
3

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

ОΩΘ

Siggy
источник
1
Добро пожаловать! Это хорошо, но я не вижу, как стабильность связана с эффективностью: просто предпочтение состоит в том, что разделы списка с одинаковыми ключами не должны «случайным образом» переставляться алгоритмом.
Дэвид Ричерби
Да, но это доказуемо возможно или невозможно?
Джеймс Фолкон
1

(Хотя это старый вопрос, я наткнулся на него, как и другие.)

Действительно, существует алгоритм, который удовлетворяет (1) - (4) и второй половине (5), поэтому он очень близок к вышеуказанному требованию. Он описан в [1] и объединяет несколько приемов, изобретенных за последние десятилетия.

[1]: Франческини, Г. Теория компьютерных систем (2007) 40: 327. https://doi.org/10.1007/s00224-006-1311-1

Себастьян
источник