В худшем случае

У меня проблемы с поиском хороших ресурсов, которые дают наихудший случай на месте стабильного $O(n \ln n)$ алгоритма сортировки. Кто-нибудь знает какие-нибудь хорошие ресурсы?

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

Например, сортировка наивного слияния является наихудшим вариантом и стабильна, но использует дополнительное пространство. Стандартная быстрая сортировка может быть сделана стабильной, она на месте, но в худшем случае . Heapsort на месте, в худшем случае но не стабильный. В Википедии есть хорошая диаграмма того, какие алгоритмы сортировки имеют какие недостатки. Обратите внимание, что в списке нет алгоритма сортировки, который имеет все три условия устойчивости, наихудший случай $O(n \ln n)$ $O(n)$ $O(n^2)$ $O(n \ln n)$ $O(n \ln n)$ и быть на месте.

Я нашел статью под названием «Практическая сортировка на месте», выполненную Катаяйненом, Пасаненом и Теухолой, в которой утверждается, что в худшем случае вместо стабильного варианта слияния. Если я правильно понимаю их результаты, они используют (снизу вверх?) Mergesort рекурсивно на первом $O(n \ln n)$ массива и последний $\frac{1}{4}$ из массива и использовать второй $\frac{1}{2}$ как царапать пространство, чтобы сделать слияние. Я все еще читаю это, так что любая дополнительная информация о том, правильно ли я интерпретирую их результаты, ценится. $\frac{1}{4}$

Я также был бы очень заинтересован в наихудшем случае вместо стабильной быстрой сортировки. Из того, что я понимаю, изменение быстрой сортировки в худшем случае требует выбора правильной оси $O(n \ln n)$ $O(n \ln n)$ центра, который разрушил бы стабильность, которой он обычно мог бы пользоваться.

Это чисто теоретический интерес, и у меня нет практического применения. Я просто хотел бы знать алгоритм, который имеет все эти три функции.

algorithms reference-request sorting in-place user834
источник

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

user834

Смотрите этот вопрос на math.stackexchange.com.

Tsuyoshi Ito

Почему другой способ выбора оси в QuickSort разрушает ее стабильность?

svick

@svick, единственный способ, которым я знаю, как сделать QuickSort наихудшим вариантом

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

O (n \ln n)

$O(n \ln n)$

user834

@ TsuyoshiIto, подумайте над тем, чтобы сделать это ответом. Кроме того, если бы вы могли дать краткий набросок алгоритма, я думаю, что это было бы действительно полезно.

user834

Ответы:

Есть несколько алгоритмов, описанных выше, и почти все они были изобретены за последние 30 лет.

Вероятно, самым хорошим является класс алгоритмов, называемых сортировкой блоков , в том числе версия (названная WikiSort) Кимом и Кутцнером в 2008 году. Она не только стабильна и полностью на месте (O (1) накладные расходы памяти в трандихотомной модели), она также является адаптивным и, таким образом, предпринимает меньше шагов для сортировки почти отсортированных списков, сходясь к O (n) сравнениям в случае уже отсортированного списка. Вы можете найти реализацию в C, C ++ и Java здесь: https://github.com/BonzaiThePenguin/WikiSort

Также представляет интерес алгоритм GrailSort (также сортировка по блокам) Хуанга и Лэнгстона (1989-1992), который фактически превосходит WikiSort в нескольких типах тестовых случаев. Реализация на C ++ доступна здесь: https://github.com/Mrrl/GrailSort

quintopia
источник

Вы можете написать стабильную сортировку на месте. Смотрите это для деталей. По словам самого автора:

Красивый на месте - алгоритм слияния. Протестируйте его на инвертированных массивах, чтобы понять, как работают вращения. Самый быстрый из известных на месте стабильных сортов. Нет риска взрыва стека. Стоимость: относительно большое количество ходов. Стек все еще может быть дорогим. Это сортировка слиянием с умным слиянием на месте, которое «вращает» подмассивы. Этот код немного скопирован из библиотеки C ++ stl и переведен на Java.

Я не буду копировать код здесь, но вы можете найти его по ссылке или проверив C ++ STL. Пожалуйста, дайте мне знать, если вы хотите, чтобы я попытался предоставить более подробное описание того, что здесь происходит.

Patrick87
источник

O (\ln n)

$O(\ln n)$

O (1)

$O(1)$

O (\ln n)

$O(\ln n)$

Кнут говорит и об этом в TAoCP.

Рафаэль

O (n \ln^{2} n)

$O(n\ln^2n)$

Пожалуйста, примите это как длинный комментарий к некоторым практическим соображениям. Хотя это не ответ на ваш вопрос, я думаю, что вас может заинтересовать это обсуждение Python:

$\lg(N!)$ $N-1$ ), но все же так же быстро, как предыдущий сильно настроенный гибрид сортировки выборок Python на случайных массивах.

[...]

Объединить смежные участки длин А и В на месте очень сложно . Известны теоретические конструкции, которые могут это сделать, но они слишком сложны и медленны для практического использования . Но если у нас есть временная память, равная min (A, B), это легко.

Источник: bugs.python.org , автор: Тим Питерс

$\mathcal{O}(n \log n)$ сортировкой с наименьшей сложностью.

Также обратите внимание, что Timsort хорошо работает с уже отсортированными массивами.

Таким образом, Python использует Timsort (то есть Mergesort с некоторыми изменениями), и, как я искал реализацию Java несколько лет назад, это была также Mergesort (я думаю, что теперь они также используют Timsort).

Мартин Тома
источник