Является ли императивная быстрая сортировка на месте (на месте) или нет?

Question

Быстрая сортировка часто описывается как in situ (на месте) алгоритм, несмотря на тот факт, что он требует O (log n) стекового пространства. Так что in situ означает «требует меньше, чем O (n) дополнительного пространства», или пространство стека обычно не считается сложностью пространства (но почему это так?), Или Quicksort на самом деле не in situ алгоритм?

Answer 1

Quicksort на самом деле не алгоритм на месте?

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

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

Конечно, в соответствии с классическим пространственно-временным компромиссом , такие версии быстрой сортировки менее производительны, чем стандартная реализация.

Answer 2

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

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

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

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

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

и

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

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