Is Quicksort in-place or not? [duplicate]

问题:

This question already has answers here:

Is imperative Quicksort in situ (in-place) or not? (2 answers)

Closed 6 years ago.

So the space efficiency of Quicksort is O(log(n)). This is the space required to maintain the call stack.

Now, according to the Wikipedia page on Quicksort, this qualifies as an in-place algorithm, as the algorithm is just swapping elements within the input data structure.

According to this page however, the space Efficiency of O(log n) disqualifies Quicksort from being in place, as it's space efficiency is greater than O(1). According to this definition any algorithm with space efficiency greater than O(1) is not in-place. So I assume this means that all recursive algorithms are by definition not in place?

So obviously there are two different definitions of in-place here. Wikipedia is not always an entirely reliable source, so I consulted with one of my professors.

My professor agreed with the second definition. He said Quicksort is not in-place. Even though the data remains in the input array, the extra space needed for the stack disqualifies it. My professor wrote a popular book on Algorithms so I respect his opinion greatly, but this answer just does not seem correct to me.

I see the property of in-place as being quite literal. The data stays in place. It does not move from it's original data structure. To me, this definition is more useful, because it means you can perform your algorithm with pointers instead of requiring you to copy data. This seems like a valuable property of an algorithm and worthy of the name "in-place".

回答1:

Intro to Algorithms from MIT Press qualifies QuickSort as in-place - it sorts the elements within the array with at most a constant amount of them outside the array at any given time.

At the end of the day, people will always have differing opinions (is Top-Down Memoization considered Dynamic Programming? Not to some "classical" folks), side with who you trust the most. I trust the editors and the authors at MIT Press (along with my professor, who qualifies it as in-place).

Typically, the problem with QuickSort is not that it doesn't sort in-place, but that it is not stable - satellite data is not kept in order.

Edit

Kuroi's point highlights part of this argument I think is very important.

Many argue that it requires O(log(n)) extra memory for recursive calls and the data is leaked in the form of the indices on the stack, however this is negligible for very large sizes of N (log(1,000,000,000) =~ 30) and it ignores the fact that typically moving data on the heap takes much, much longer, when size(data) >> size(index).

The indices of the data are not the elements themselves - so the elements of the data are not stored outside the array, other than a constant amount of them (in each call).

回答2:

Strictly speaking Quicksort has a space efficiency of O(n) since the degenerate case would require an index on the stack for each element of the array. Though on average it will be O(log(n)). Given that I don't think there is any way you could call it an "in place" algorithm, unless you go with a degenerate definition of "in place" meaning that the original data is not stored outside of the original array bounds (excluding copy/swap operations).

This definition of "in place" would be degenerate because you could take any "out of place" algorithm and make it satisfy this "in place" requirement by having it do all of its extra data storage use pointers to the original array. Then when the answer is found you could reorder the original array "in place" using the pointer data.

回答3:

qsort does indeed swap data in place, but the stack space used for recursion is in log₂(N).

These two properties are not contradictory. Usually "in place" refers to heap memory, i.e. what you must explicitely allocate for the algorithm to work.

However, a logarithmic space complexity is basically neglectible, except in pathological cases (say you want to do a quicksort on a 8 bits microcontroller with 512 bytes of stack :)).

回答4:

It all depends on the definition of "in-place" algorithm.

If you define "in-place" as requiring a constant amount of memory, then quicksort is not "in-place" as it requires log(N) memory for the recursion.

If you define "in-place" as more human-friendly "does not move the data outside the input structure", then quicksort is again not "in-place". The data leaks to the memory in form of indices with which the quicksort method is invoked, which are necessary for algorithm to work. The contents of this additional memory directly depend on the input, how it is not leaking?

If you define "in-place" as not-copying, then what about a stupid algorithm to find a sum of an array: create another array of length (n - 1) with elements like b[i] = a[i + 1] + a[0] / n. This is kinda copying, though the contents are different, but the contents of this additional memory are a function of the input data, just like the indices held on stack in quicksort algorithm.

I think that the wikipedia definition of "in-place" is the most useful, and according to it the quicksort is not "in-place" as it uses non-constant amount of memory.