Оптимальный алгоритм сортировки по количеству свопов

Учитывая последовательность из чисел, можно ли ее отсортировать с помощью сравнений и перестановок / ходов? Любой указатель на публикации по этому вопросу или контраргументы, показывающие нижнюю границу , поможет. $n$ $O(n \ln n)$ $O(n)$ $\Omega(n \ln n)$

cc.complexity-theory ds.algorithms Джесси Цикси Чжан
источник

Любой алгоритм сортировки на основе сравнения должен выполнять

сравнений и

перестановки в худшем случае (см. CLRS).

Ω (n \log n)

$\Omega(n \log n)$

Ω (n)

$\Omega(n)$

Каве

Тривиально, вы можете достичь

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

O (n)

$O(n)$

Юкка Суомела

@jukka хорошо, это обманывает, потому что вы переместили элементы, когда вы сортировали стол ...

Джесси Цикси Чжан

Ответы:

Существует стабильный алгоритм сортировки на месте с сравнениями и ходами. $O(n \log n)$ $O(n)$

$O(n \log n)$ $O(n)$

Snowie
источник