Обязательно ли Quicksort in situ (на месте) или нет?

Ответ 1

является Quicksort фактически не алгоритмом in situ?

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

Я говорю "стандартную реализацию" этого, потому что люди модифицировали алгоритм, чтобы сделать его O(1) -пространственным алгоритмом. Вот один пример: Quicksort без стека.

Конечно, в соответствии с классическим пространственно-временным компромиссом такие версии quicksort менее эффективны, чем стандартная реализация.

Ответ 2

Википедия предлагает следующее определение:

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

В соответствии с этим определением типичная быстродействующая система на основе стекол явно не является алгоритмом in situ.

Фактически, статья Википедии явно обсуждает это:

Алгоритм иногда неофициально называется in-place, если он перезаписывает свой вход своим выходом. На самом деле этого недостаточно (, как демонстрирует quicksort), и это не обязательно; выходное пространство может быть постоянным или даже не подсчитываться, например, если выход является потоком.

и

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

Однако, как отметил @Jason в своем превосходном ответе, существуют варианты вариантов быстрой сортировки, которые требуют только O (1) дополнительного пространства. Любые такие алориты будут рассматриваться in situ.