On Wikipedia, it said that
The in-place version of quicksort has a space complexity of O(log n), even in the worst case, when it is carefully implemented using the following strategies:
- in-place partitioning is used
- After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most O(log n) space. Then the other partition is sorted using tail recursion or iteration, which doesn't add to the call stack.
Below is naive quick sort:
Quicksort(A, p, r)
{
if (p < r)
{
q: <- Partition(A, p, r)
Quicksort(A, p, q)
Quicksort(A, q+1, r)
}
}
Below is tail recursion quick sort:
Quicksort(A, p, r)
{
while (p < r)
{
q: <- Partition(A, p, r)
Quicksort(A, p, q)
p: <- q+1
}
}
Algorithms above are based on this link
What if we just use in place partitioning? Is it not enough to make quicksort having space complexity of O(log n)?
Below is what I understand of stack call of quicksort. Do I misunderstand it?
Suppose I have sequence of number: 3 5 2 7 4 1 8 6. I use in place method in this case.
input : 5 3 2 7 4 1 8 6
partition: 3 2 4 1 (5) 7 8 6
stack 1 : 2 1 (3) 4
stack 2 : 1 (2)
stack 3 : 1 - stack 3 removed
stack 2 : 1 (2) - stack 2 removed
stack 1 : 1 2 (3) 4
stack 2 : 4 - stack 2 removed
stack 1 : 1 2 (3) 4 - stack 1 removed
input : 1 2 3 4 (5) 7 8 6
stack 1 : (6) 7 8
stack 2 : (7) 8
stack 3 : 8 - stack 3 removed
stack 2 : (7) 8 - stack 2 removed
stack 1 : (6) 7 8 - stack 1 removed
input : 1 2 3 4 5 6 7 8 -> sorted
we need 3 stacks at most, which is log(n) = log(8) = 3
If what I told above is correct, the worst case with that method is n, which is happened when the pivot is the minimum or maximum
input : 5 3 2 7 4 1 8 6
stack 1 :(1) 5 3 2 7 4 8 6
stack 2 : (2) 5 3 7 4 8 6
stack 3 : (3) 5 7 4 8 6
stack 4 : (4) 5 7 8 6
stack 5 : (5) 7 8 6
stack 6 : (6) 7 8
stack 7 : (7) 8
stack 8 : 8
stack 7 : (7) 8
stack 6 : (6) 7 8
stack 5 : (5) 6 7 8
stack 4 : (4) 5 6 7 8
stack 3 : (3) 4 5 6 7 8
stack 2 : (2) 3 4 5 6 7 8
stack 1 :(1) 2 3 4 5 6 7 8
input : 1 2 3 4 5 6 7 8 -> sorted
we need 8 stacks, which is n
that's why in place partitioning is not enough. But if I am correct, what makes it different using tail recursion?
And also, anyone can give pseudo code for iteration instead of tail recursion?
