Welcome back.
In this video let's look at the space complexity of the quicksort and let's see how to optimize it.
All right.
Now the quicksort is an algorithm that works in place right.
And with in place we mean that we are not creating any new array or we are not using any new space in
that respect.
Right.
But we cannot say that the space complexity of the quicksort is O of one or constant space.
Why is that so?
Because the quicksort is a recursive algorithm and we will use space on the call stack.
Right.
So let's take a look at the space utilization on the call stack.
Now what is the maximum size of the call stack that we would be using.
This would happen when the depth of the tree is the maximum.
Right.
When the depth of the recursive calls is the maximum.
And this will happen in the worst case, which we discussed right when we are having n calls, we we
saw the case where we had a sorted array, right?
We saw the case where one, two, three, four, five was passed and then we fixed the pivot over here.
Then we called it over here right.
Similarly again this was fixed.
We called it for this part of the array.
And we kept on doing that.
Right.
So we saw the worst case.
In this case the depth will be n.
And therefore the space complexity of the quicksort in the worst case would be o of n.
Because there would be n calls in the call stack.
All right.
Now this case happens when the array was already sorted or we always picked.
We can say in in another words.
In other words we always picked the minimum or the maximum element as the pivot.
All right.
Now what is the best case scenario of the, um call stack?
The height, the best case scenario of the height of the stack.
When would the height of the stack be minimum?
Let's take a look at that now.
Now this would happen when the the tree the tree is evenly created.
Right.
So we have a depth of log n.
So we saw that.
And that happened in the case when we picked the pivot always as the middle value.
So we have seen both the cases already right.
So in the in the case where we always pick the middle value of the array as the pivot, we had log n
levels, right.
And in this case the space utilization on the call stack will be of order O of log n.
Right.
So we have seen the best case and the worst case.
Now the what was the worst case.
Again let's quickly write it.
If we have the array 12345 we call it for 1 to 5.
So this will call it.
This will fix the position of one and it will call it for 2 to 5 right.
Similarly that will call it for 3 to 5 etc..
Right.
So we fix one.
We call it for 2 to 5.
That's this one over here we fix two.
We call the quicksort for 3 to 5 etc..
And then once we reach an array of size only one we start returning.
So over here we can see that the the depth is n right.
If there are n elements the depth is n.
That's why we say that the maximum size of the stack is O of n, and the minimum size is O of log n.
We have seen the best case where we had the tree right.
We had n elements that was divided into n by two and n by two, and this was divided into n by four
and n by four.
And this kept on going right.
This kept on happening till we reach one.
The size of the array is one.
So this over here will have log n levels.
And that's why we say that the best case space complexity of the quicksort is O of log n.
So we can say that the space complexity of the quicksort ranges from O of log n to O of n.
Now we can make some tweaks to the algorithm.
And this was first proposed.
This was actually, uh, discovered or invented by a computer scientist called Cedric.
Okay, so what he said is that there is a way to limit the auxiliary space, which we are using on the
call stack to always to O of log n.
So let's see that.
Now let me make some space over here.
Now in the way that we have discussed so far, the space complexity of the quicksort will be O of log
n to O of n.
Best case is O of log n, and the worst case is O of n.
Now there is a way to limit the auxiliary space or the space on the call stack to O of log n always.
So let's discuss how to do that, and let's make that tweak in the way we will do the quicksort.
So we will implement all of this when we code the quicksort.
Now to achieve always the auxiliary space of O of log n.
To achieve this space complexity, what we need to do is we need to make the recursive call of the quicksort
only on the lower sized subarray.
Now how did we do it so far?
We.
Let's take a look at the earlier discussed implementation.
We find the pivot right.
And then we recursively call the quicksort on the left side and the right side.
This is how we discussed it previously.
Right now when we go to the coding section we will do it in both ways.
Now when we input an array of size 41234 and it will be sorted if we implemented in the previous method.
Right, which we did over here.
In this way you can see that in the call stack there will be four.
The maximum call stack will be four.
There would be four calls on the function quicksort.
We will see that when we do the coding together, and when we change the implementation to what Sedgewick
proposed and discovered, which is recursively calling the quicksort only on the lower side subarray.
When we do that for the same array, we will see that.
Also when we code it, we will see that it will be reduced to log four and log four.
Again remember it's always to the base two that's equal to two right.
Because two to the power two this.
If we raise this two to this power we will get four.
That's why log four to the base two is equal to two.
And we have discussed logarithm in a separate video.
So I am not discussing that again over here.
Now when we make this tweak over here and implement the quicksort, we will see that the maximum call
stack will be of two calls.
Right.
So we will see that.
So in this way always the space complexity or the auxiliary space can be limited to O of log n.
That's what we will discuss over here.
All right.
So let's see this in great detail.
That is recursively calling the quicksort only on the lower sized subarray.
Let's try to understand this.
Let's look at its let's look at this scenarios best and worst case right.
In terms of space complexity it does not affect the time complexity.
The time complexity remains the same.
This only affects the space complexity.
Now the worst case where we got the space complexity of O of N was when we always picked either the
lower or the larger the largest element.
Right.
So that let's let's for example, take a sorted array.
And if you always pick the first element, we will be always picking the lower element.
And in that case we have seen we will get a space complexity of O of n.
Now this is the worst case as per the previous implementation.
Now let's try to think of the same scenario with the new implementation over here, which is which was
brought for forward by Sedgewick.
Right.
So let me quickly write a pseudocode over here so that we can think through this in a better manner.
And we will take a look at the call stack at each level.
Because there that's where the space utilization happens right.
That's where the auxiliary space is used.
So this is the quicksort function which I have over here.
Now what this does is at every point it will check, it will be passing an array.
And it will pass in a start and end to the function.
Right.
So initially it will be this will be the start and this will be the end.
And it will pass this array to the quicksort function.
Now we will check whether start is less than end right.
So this is true.
Start is less than end.
And then we will find the pivot.
So I'm not writing the full pseudocode over here.
The get pivot part remains the same which is what we've discussed when we discussed the logic of the
quicksort.
Right.
We will make comparisons and we will find the correct place where the pivot has to be placed.
Once the array is sorted and we will get the pivot index.
So this is the pivot index right.
So let me just call it as pie.
So we are getting the pivot index at this point.
And then as per the pseudocode over here if the left subarray is smaller we will do quicksort on the
left subarray.
And once we come out of it we will change the start position to pivot plus one or this pivot index.
I'm just calling it pivot over here plus one.
And again we will come out of it.
And this will keep repeating.
All right.
So this is the.
A function.
So over here notice that we have in this code.
In this pseudo code we have iteration as well as recursion.
Right.
So this part this whole part comes within the while loop.
This part.
So there is an iteration happening over here.
And then inside we have recursion.
So over here we have recursion.
We have recursion over here.
So what we are doing is again as we have mentioned over here, we are making recursive calls only on
the lower sized subarray.
Now let's try to understand this.
We will walk through this example so that we can understand it.
Let me quickly revise what we have discussed so far.
We are trying to see the implication of recursively calling only on the lower sized subarray, especially
in the case where we have this case where we had a space complexity of O of N, right.
So this is the pseudocode.
We have iteration in the while loop.
So this all these things comes inside the while loop.
So there is iteration happening over here.
And then we will recursively call the quicksort function which is this whole function over here only
on the lower size subarray.
So that's what we are discussing.
Now let's say we call quicksort with this array over here 12345.
We pick one as the pivot.
All right.
So we are trying to just take this as the first element as the pivot so that we encounter the worst
case scenario because we want to see how this uh, change in the algorithm affects this worst case scenario.
So that's what we are trying to find out.
So in this case we pass the quicksort we we call the quicksort function.
And the array is 12345 which is this array over here.
Right.
So we we take this element as the pivot.
We find the pivot as one right.
And we fix its index right.
We fix its index.
And then as per the previous implementation we find the left and right right.
So the left in this case would be empty right.
Because there's nothing to less than one.
So the left is empty.
And the right will have this part over here.
So so far there is no change.
And it should be clear.
Right.
So the left is empty and the right has 2 to 5.
Now what happens is over here we will check whether the left subarray is smaller or the right subarray
is smaller.
In this case the left subarray has no elements at all right.
So this one is smaller compared to the right subarray.
So we come over here right.
So we come over here and we call quicksort on the left subarray.
In this case that's just empty right.
It's empty.
So what will happen is we will return right.
So again let me also keep track of the call stack.
So let me make some space over here.
We are going to keep track of the call stack over here because we are calling the quicksort again recursively.
Whatever is over here right will be stored in the call stack.
So let me just denote it as queue 125.
So this one over here is put into the call stack.
Right.
And then we call the quicksort again with this queue I mean quicksort.
And we are over here we call the quicksort again.
Now what happens again.
We have to pass the array.
And we have to pass the start and end end right.
We are not creating any new array.
So the same array will be passed but the indices will change.
So at this point the start what is the start.
We will pass the start which is already there and the end we have we are passing the left right.
Remember when when.
Look at the normal case so that you can understand this.
Let me just, uh, make some space over here.
In the normal case, let's say this is the pivot.
So when we are calling quicksort on this part, the star doesn't change.
But the end earlier the end was over.
Here when we call the quicksort on this part we will make the end as pivot minus one.
Right.
So that we want only this part, the quicksort, to run only on this part.
Right.
So in this case also we are calling it on the left.
But the only thing is that the left is empty.
So again we are calling it with the array.
The start does not change but the end is changed to pivot minus one.
And in this case pivot is zero right.
So start is zero and zero minus one is minus one.
So that's I'm just simplifying it to empty.
So we are calling the quicksort on an empty array.
There's nothing over here.
Right.
And then when we come to the function again this is the quicksort function.
We will check whether start is less than end.
Over here it's zero and minus one.
Zero is not less than minus one.
So we will come out of it right.
So what will happen is we will return.
So we will return to where the quicksort was called recursively.
And when we return the call stack will be removed.
Right.
So this will be removed out of the call stack.
All right, now what happens?
We are over here.
Right?
We came out.
So there's no more recursive call on the call stack.
We come to the next line of the code, we come over here and start is changed to pivot plus one.
So we found the place of this as zero right.
So this is the zero index.
This is one this 2345 etc. 1234.
Right.
So the one was fixed at index zero.
So start is changed again I'm just writing it as two so that it's easy again.
Let's just think of it in terms of the elements right.
So start is changed to this element right.
So start is changed to this element.
And then we call the function recursively on this part.
So again what happens.
We come out.
We check whether start is less than n.
Yes it's true.
Again we come and we find the pivot right.
So pivot is two.
It is fixed.
And this happens again.
So let's see what happens again.
So we call the uh the get pivot part the partition function on this part.
So two is the pivot right.
So let's uh clear this up.
So we are calling the quicksort on this part the indices.
Again the whole array is passed.
But the indices are this and this right.
So we are just looking at this part of the array.
And we fix this.
We fix this over here.
And what happens.
Let me write that over here.
We call it we fix the pivot which is two.
We fix its position and its left is now empty.
Right.
We are just looking at this part of the array.
There is nothing to its left right, left is empty and right has three, four, five.
So right has three, four, five.
Now we will look at which is lesser is the lesser left subarray smaller or the right subarray smaller.
Again we see that the left subarray is smaller.
So we call quicksort on the left subarray.
Again it's called on the empty.
When we make this call this this one over here.
This one over here is put into the call stack.
So let's write that over here Q 2 to 5 is put into the call stack.
Right.
And because this is empty again when we check while start less than end it will break and we will return
right.
This will return to the function where it was called.
So when it returns this is removed from the call stack.
Right.
So again it's removed.
So what can you notice over here.
Earlier when we had this we had the call stack.
The call stack looked like this right.
1 to 5 and again 2 to 5.
Again 3 to 5 4 to 5.
And 5 to 5.
So order of n right in the call stack.
But over here you can see it always keeps returning because we are just calling it on the, uh, empty.
Right.
In this case.
In the worst case.
Right.
So it returns.
So you can notice that in the worst case earlier when we got the space complexity of O of n, in this
case, the call stack always has only one element or the call stack is just one element deep.
Right.
So in the case of the worst case, by making this tweak, that is by recursively calling the quicksort
algorithm only on the lower sized subarray, we are getting the call stack to be only one element deep,
right?
But again, you cannot say that the space complexity by making this tweak is O of one.
That would be wrong, right?
This is not O of one.
Why is that?
So let's look at a generic case for this.
Let me clear this.
All right.
Now over here we had our algorithm.
Now let's look at the generic case.
Let's say this is the array which is given to us.
Now what we are doing is we will find the pivot.
So we will find the pivot.
We will fix it at its correct position.
Now we will look at the two subarrays.
Now let's say in this case the left subarray is smaller.
Visually it's also smaller in size right rather than the right subarray.
So we will call quicksort on the smaller subarray.
That's what we do over here.
Now, what about the right side?
Right.
How is it handled now?
Once we are out of this.
Right.
Once we have called this, and once we are out of it, we will change.
Start to pivot plus one.
So start would come over here right.
And end is still over here.
And we will again.
We will while start is less than n.
So this is true.
So again we will call pivot.
So what we are trying to do is for the larger side larger subarray we will find the new pivot over here.
And again we will call quicksort on the smaller side recursively.
So this is what's happening with this algorithm right.
Earlier we were just finding the pivot calling the quicksort recursively on the smaller side again calling
the quicksort recursively on the larger side.
But instead of that what we're doing is on the larger subarray.
What we're doing is we are again finding the new pivot, we are fixing it, and we are calling quicksort
recursively only on the smaller side.
So this is what is happening over here.
Now let's go ahead and look at the worst case scenario of this modified algorithm.
With this tweak in the algorithm, which we discussed, where we only recursively call on the lower
sized sub frame.
The worst case will happen if you always pick the pivot such that it divides the given array into two
equal halves, or if you pick the pivot as the middle value or the median, right?
What would happen in that case?
Let's say the given array is of length n.
We divide it into n by two, n by two, and this over here on the left side, let's say it keeps going
on till we get to a size of one of the array.
Right.
So in this case what is this case where we divide into equal halves.
Right now in this case the stack depth will be log n right.
And therefore in this case the space complexity of this algorithm will be O of log n.
All right, now over here.
What's happening?
Let's quickly draw the stack.
In this case, over here we have n that calls it for n by two.
Then we have n by four and it keeps going till one.
Now this depth as we have seen many times is log n right.
So that's why by making this change we are able to ensure that the auxiliary space used or the call
stack space used is always of order log n.
Without this tweak it was ranging from log n to N, but by making this tweak that is, by recursively
calling the quicksort only on the lower size subarray, we have seen that in the worst case, we have
only a depth of one right in the call stack.
So when we look at the right side, we are no longer we don't have anything in the call stack any longer.
So that's the advantage right.
So again over here also we call the pivot.
And then on the left side we call the quicksort recursively.
That's how this works.
But then there is nothing on the on on the call stack.
Right.
We remove it.
And we have seen in the algorithm we do a fresh start where we look we have the start over here and
over here we find the new pivot.
And we recursively call only on the lower sized subarray.
So by doing this we got that the space complexity is log n o of log n.
The worst case space complexity is O of log n.
So far we have discussed these things.
We have understood the quicksort, we have understood the time complexity, and we have understood that
to avoid the worst case, we can either pick a pivot randomly or the middle value.
And we have understood the space complexity.
Right.
And we have seen we've made a tweak where we can recursively call the quicksort only on the lower size
subarray.
And by doing this we got that the space complexity will always be the worst case.
Worst case space complexity will be O of log n.
So we have seen that the time complexity of the quicksort is O of n log n, right.
That's the best case.
And the average case.
Now to avoid O of n square in the case of sorted data, it's recommended to pick the middle element
or a random element as the pivot.
And we have seen that the space complexity of the quicksort is O of log n.
And for this, to ensure that this is the worst case we have, we have to make the tweak where we do
the recursive call on the quick side quick of the quicksort only on the lower sized subarray, right.
If you don't this if you don't do this in the case where we always pick the pivot as the minimum or
the maximum, we would get O of n space.
And we are avoiding this by making this tweak.
Now let's go ahead and code our solution.
We will also look at the two cases where we do the recursive call only on the lower size, and where
we do it on both the side cases, both the sides left and right, and we will see the difference in
the call stack.