Hi everyone.
In the previous video we have discussed these two implementations of the quicksort, right?
We have implemented the quicksort in the way where we recursively call the quicksort only on the lower
size subarray.
That's this implementation over here.
And we have also written the quicksort in the manner where we call it recursively on both the left side
and the right side that is on both the subarrays.
So in this video, let's try to understand the implication of these two implementations on the call
stack.
So over here I have an array 3124.
Now I have written it in such a manner that when we pick the middle element the array is always, uh,
divided in a way that we don't have a left.
Right.
So for example I have three one, two four.
So initially the middle element will be one.
It will be placed at its right position and then everything else will be to its right.
So left will be empty right.
So that's the worst case scenario where we discussed this implementation.
Right.
And to avoid the n o of n space in that case that's where we discussed that we could make this implementation
and only recursively call quicksort on the lower size subarray.
So to get the worst case I have engineered this array over here.
Right.
Especially I have written 3213124.
Because in the partition function we always pick the middle value.
Right.
So if if the partition function was written so that we always pick the left most value, then if we
have the input one, two, three, four, then that would be the worst case, right?
We always pick the left one.
So the left side of that sub array is empty.
Then we recursively call it on two three, four and it goes on like that.
So that was the case where we got a depth of n.
So I just want to simulate that over here.
But I don't want to change this code.
I want to keep it over here as it is.
So let's look at this input array 3124.
And let's look at the call stack.
When we run this over here we have the debugger.
So let me just write debugger over here.
Or you can also rather create a breakpoint over here by clicking this.
So now the code will stop over here.
And then we can just press next next and look at the call stack.
Right.
So that's what we are trying to do over here I'm not walking through the code over here.
We'll do that separately.
We are just trying to look at the call stack between these two implementations.
So let's run it.
All right, so we have caught the debugger.
We are over here.
Now let's look at the call stack and keep track of it as we proceed.
And again let me just increase this so that we can see this properly.
All right.
So we have one quicksort in the call stack.
And whenever I come to partition, I'm just going to come out of the function quickly, right?
So that we don't waste too much time.
So we have quicksort only one time.
Now we have it two times.
All right.
And one is popped off and we have again quicksort over here.
We are in the partition function.
I come out of it.
Now we have two on the call stack.
Now we have three quicksort's in the call stack.
Right.
All right.
One is popped off again, one is added.
We are in the partition function, so I come out of it.
Now we have three quicksort's.
Now you can see we have four quicksort's right in the call stack.
Now the size of the input was only four.
Right.
So we have we have discussed that in the case where we call recursively on both the sides, the worst
case complexity is O of n right.
The worst case complexity is O of n.
And we see that over here because we have four quicksort's in the call stack.
So the space complexity in this case is O of n.
Now by doing this implementation where for the same input array, by doing this implementation where
we recursively call only on the lower size subarray, we saw that we can reduce the space complexity
to O of log n right o of.
Login.
Right.
Now in this case n is equal to four.
So log n is equal to what's log n log four.
Right.
So log four is equal to two.
So over here n is equal to four.
So that's what we have seen over here we have quicksort four times in the call stack.
So we have seen this case.
Now let's try to implement let's try to try to run this case this quicksort over here.
This implementation where we recursively call the function the quicksort function only on the lower
sized subarray.
And we should be getting a call stack depth of only two, which is log n.
And that's the improvement that we are looking for by doing this implementation.
All right.
So let's just come out of this.
All right, so we are out of it.
Now what we will do is let's comment this quicksort over here.
And let's.
Remove the comments over here.
Okay.
So we will call this quicksort.
And again we will look at the call stack.
And our expectation is that the depth the maximum depth should only be log n which is equal to two.
So let's run our code and take a look at the call stack in this case.
So we are at the debugger now.
And we call quicksort one time.
We go to the partition function and I come out of it.
So we have only one quicksort in the whole stack at this point.
Now we have two quicksort's in the call stack.
And one is popped out.
Again, we are in the partition function.
We come out of it.
We have only two quick thoughts at this time in the call stack.
Wherein the partition function, I come out of it.
You can see that we've popped out one.
We have only one quicksort in the call stack now, and we have now two quicksort in the call stack.
And that's the end.
See, the array is sorted and you can see that at any point we only had two quick sorts in the call
stack.
Right.
So that's why this implementation is much better.
And we have achieved a space complexity of O of log n instead of O of n.