Hi everyone.
In this video let's go ahead and code the quicksort which we have discussed.
And we will first code the version where we will recursively call the quicksort on the lower sized subarray.
All right so we discussed this.
So this will help to ensure that the space complexity is O of log n.
So we will implement this first.
And then let's also implement the case where we call the quicksort recursively on both the sides.
And we will compare the call stack in both the cases.
All right.
Now to do this to implement the quicksort we will need a function to partition a given array right.
So this will find the pivot.
It will it will decide a pivot and it will find the correct position of that pivot.
So this function will take in an array and it will take in a start.
And it will take in an end.
Right.
So this is one function that we will need to write.
And then we will need to write the quicksort function.
This also will take in an array.
And it will have a start and an end.
Right.
And inside this we will decide how to recursively call quicksort.
All right so let's get started.
And initially uh also let me write this part.
Once we are done with this we will define an array.
Let's say it's uh 54032 or let's say one.
And then we will call quicksort on this array.
Right.
And after this we will console log the array and this should give us the sorted array.
So that's the intent.
Now to start with let's go ahead and write the partition function.
Now it takes in an array.
Let's say that if the start is not specified we take it as zero.
And if the end is not specified we take this as array dot length minus one.
All right.
And the same is true for this function.
Also because over here we are just calling the quicksort right.
So if the start is not passed let's take it as zero.
And if the end is not passed let's take it as array dot length minus one.
All right.
And again one more point over here.
We will when we write the partition function we will write the version where we pick the middle value
as the pivot.
All right.
So this will ensure that in case the array which is passed to B which is to be sorted is already sorted,
then we don't want to have the time complexity of O of n square.
Right.
And we discussed that to avoid that, it's recommended that we pick the middle value as the pivot.
So in this implementation we will do it like that.
So for this we just need to make a minor tweak to what we discussed in the logic section.
Right.
So let's implement that and discuss that over here as well.
All right.
So first we will write the partition function.
Now once we are inside the partition function first let's find the middle value.
Because as we discussed we are going to take the middle value as the pivot.
So the middle index can be found by math dot floor.
And we will take the middle of start and end.
So start plus end.
Divided by two.
And I will need one more bracket over here.
All right.
So we get the middle value of the start and the respective end when we call the partition function.
Now what we do is to take the middle.
Like when we discussed it in the video, we always took the pivot value as the first element.
Right.
So to make it the same case, let's swap the middle value and the first value.
So I need a swap function where I will be passing the array.
And I will pass the start value and the middle index right the start index and the middle index.
So let's write the swap function.
That's going to be a simple function right function swap.
And this will take in an array and it will take two indices.
And let's have a temporary variable.
Let temp is equal to array at I and we can say array.
At I is equal to r I a j.
And then we say area J.
Is equal to temp.
So we have swapped these two values.
So it's a simple swap function.
So we call this over here.
And we change the position of the middle value and the start.
So what's happening over here.
Let's also parallelly analyze it.
Let's say over here we have this array which is passed.
And we want to uh we want to sort it.
So in this case the partition let's say it's a sorted array okay.
So we are actually doing this to avoid the case where the passed array is sorted.
So let's say this is the array.
It's sorted.
So what do we do.
We find the middle value and that's three.
And we swap the middle value and the start value.
So after doing the swap the array will look like this.
We have three over here.
Then one then two.
Sorry we have three over here where we had one.
Then we have two and where we had three we'll have one because we just swapped these two right.
So we have one over here.
Then we have four and then we have five.
Now it looks like this.
And then we will proceed with the same way that we discussed in the logic.
That is we will take this value as the pivot and we will change the values of change the position of
these values over here by comparing and swapping.
And then finally we will put the pivot in the correct position.
So this is the only change that we are doing.
We are identifying the middle.
And then we are swapping the middle and the start position.
And then it goes on as we discussed in the video before.
So let's go ahead.
Now let's have a variable pivot.
So let pivot is equal to array at start right.
Because now we have moved it to the start.
So the pivot value over here is three right.
Start is zero.
So the pivot value is three right zero which is three.
All right.
Now let's have two pointers.
Let's call it I and J.
So let I be the first value after start right.
We just need to compare these values.
So this is start.
So this is where I should be right.
Which is the next value after I.
So I should be equal to start plus one.
All right.
And Jay will be the end.
Right.
So let Jay is equal to end.
Now we just need to keep moving them and swapping them as appropriate.
So let's have a while loop.
While I less than equal to J.
We will keep checking and swapping if required.
All right.
And while the value at array I while array I.
Is less than the pivot.
If that is true, then it's its position is fine, right?
So if the value at I is less than the pivot, we can even write less than equal to pivot.
As long as this is true let's keep moving I I plus plus.
And for Jay when it comes to Jay while the value at Ray Jay.
Is greater than the pivot.
It's fine.
So we can just keep moving, which is J minus.
Minus.
Now by the end of this code, we will have identified the I and J where the values are not in order
and we need to swap them.
Right.
So we before we swap them we need to check whether I is less than J.
We have seen this in the video right at the end when we need to stop, right?
I j will be less than I.
So if that is the case we don't swap.
So if I is less than J then we will just swap, right?
We will swap and we are calling our swap function.
We will pass the array and we will pass I and J.
All right.
Now at the end, as we saw in the video, all we need to do is we need to swap after we are out of this
while loop.
Right after we are out of this while loop J will be less than I, right J will be less than I because
it will go on as long as j I is less than equal to j.
So if j is less than I or I is greater than j, we will come out of it, and at that point we just need
to swap the position of J and the start.
Because at start at start we have our, uh, pivot, right?
Our pivot is at start because we swap the middle and the start.
So at the start we have our pivot.
So we need to swap the pivot and J.
And we get the pivot in the correct index where it should be.
And the index where the pivot has been placed is j.
So we return j at the end.
And that's the end of our swap function sorry our partition function.
So we have written the partition function.
Now let's proceed to write the quicksort.
Now as we said over here we are going to first write the version where we will recursively call the
quicksort on the lower sized array.
All right.
So let's get started.
Now in this implementation you will see that as we discussed there is an iterative part and there is
a recursive part.
So for the iterative part we have a while loop while start less than end.
And we will do something right.
We will do something.
So let me just quickly explain what's happening over here.
Now for this, let's have let me comment this part.
And over here I have an array.
And these are all elements.
And let's say P is the pivot.
And then let's say we have few more elements over here.
So we will identify that this is the lower sized array sub array.
And we will recursively call quicksort over here which will happen inside.
All right.
Now once we are done with this we will change the start to this part over here.
So start will be here and end will be here.
And our call stack is now clear.
Right.
There's nothing waiting over there.
And then we again call quicksort.
Right.
By finding the pivot of this part, by finding the pivot of this sub array, we um we find the pivot.
And then on the left side of that we will call we will call quicksort.
So we will that's what we are trying to do.
So once we are out of this we want it to go to the right side right.
So this will be taken care by the while loop which is taken care iteratively.
Now as we write it.
And again after we are done with writing the code, we will also walk through the code and it will become
more clear.
But over here this is the part played by the while loop.
Alright, so let's go ahead and write the remaining part of the code and we will again see and try to
understand it in a better manner.
So once we are one, start is less than n.
So initially let's say the whole array is passed to start is less than end.
All right.
So we call the partition function which we wrote.
So let's say we have a variable pivot.
Let's call it id.
Pivot index for index, and this will store the value that is returned by the partition function, which
is the position of the pivot.
Right.
So partition array and start and end.
All right.
So after we have called this, as we discussed over here and in the previous video, we will recursively
call the quicksort on the lower sized subarray.
So we need to find out whether the left or the right subarray is the lower sized subarray.
So for this let's uh find the size of the two subarrays.
And then we will decide where we should recursively call the quicksort.
Now over here notice that this this length over here is nothing but start minus pivot index.
Right.
So it will give us this length over here.
And this length over here is end minus pivot index.
So we just need to check which among these two is smaller.
So let's write a if function for that.
So if pivot id.
Minus start, which is the left subarray.
If the size of that is less than n minus pivoted x, which is the size of the right subarray right.
So if the left one is the lower sized subarray, then we will call quicksort over here.
So quicksort.
And we will pass the array.
Now for the left side.
Right.
The start will be the same, but the end will be pivoted minus one.
So we will have start comma pivoted minus one.
All right.
Now this will this is a recursive call on the lower uh size sub array.
Right.
So again let me just write comments over here so that it becomes clear.
It becomes clear.
So recursively call quicksort.
On lower sized.
SubArray.
All right.
Now, after we are out of this, right after it's done and we come out of this, we need to change our
start to this, this one over here so that when we come over here, we see start is less than end.
And again we partition this part and it goes on.
Right.
So over here, after we are out of this we have to say start is equal to pivot ID plus one.
All right.
Now, if this is not the lower sized subarray, if that, that means if this is the lower sized subarray.
So then we have to write the else part over here.
And then we call quicksort on that part.
So quicksort again we pass the array.
Now notice if we are passing this part right the start is pivoted plus one.
And the end is still the same.
So over here we write pivot id.
Plus one as the start and we pass end as end itself.
Now let's say this was the smaller subarray.
So let's say this had only two elements.
Now after we are out of this we need to sort this part also.
Right.
And that would be taken care by the while loop.
So for this we need to set the end to pivot ID minus one.
So we do that over here.
End is equal to pivot ID minus one.
And we come over here.
Then this partition will be called on this subarray over here.
Because start is still less than end.
Right.
So that's the end.
So that comes that that brings us to the end of this function.
And we are done.
Now let's test our code and see whether it's working.
So we have a test case over here.
Now let's run it and see what we get.
All right.
So okay this there is the spelling is wrong.
So this has to be capital S.
So let me change that over here.
And let's run it again.
And you can see we get 01345 which is sorted.
So yes our code is working right.
So again notice we have taken the pivot as the middle value.
And we have implemented the case where we recursively call quicksort on the lower sized subarray.
All right.
Now let me just come comment this over here.
And let's go ahead and implement the quicksort where we call it on both the sides.
So let's write that over here.
And let me call that function as quicksort again.
So function quicksort.
And oh, here also we pass in the array.
And we have start.
Let's initialize it to zero.
If the value is not given and n is equal to array dot length minus one.
All right.
Now over here.
When we wrote the case in the previous solution, we had an iterative part as well as a recursive part,
but we don't have that over here in this implementation.
All right.
So let me just check.
We have enough length.
Yes.
It's coming inside the video.
All right.
Now over here.
What we do is we will check if start is less than end.
All right.
So if start if the start is less than end.
So we keep doing this right.
And we will call the quicksort.
First we will call the partition function.
So let's do that.
Let pivot id.
Is equal to partition.
And we pass the array.
And we pass the start and end.
All right.
So this will give us the pivot and it will give us the pivot index.
And then we call quicksort again iteratively on both the sides.
So array and again over here the left side will have the same start.
So start and the end of the left side will be pivot minus one right pivot index minus one.
So pivot id minus one.
Similarly for the right side we will have the start as pivot id plus one.
So let me write that over here quicksort array.
And the start is pivoted plus one.
And the end is still the same.
Right.
So comma and now we have iteratively called quicksort on both the subarrays right.
And then finally we just need to return the array right.
Because this will be a recursive call.
So we need to return the array right.
So over here what will happen is we will get the pivot in this case.
And we will call quicksort on the left part right.
So that again will find the pivot index.
And it will keep calling.
And once this part is sorted we come back over here and it calls quicksort again iteratively on the
right side.
All right.
And then again we over here we get back the array.
And when we call it right because we have we are returning an array.
Similarly over here also we keep returning the array.
Again we are doing this in place.
So we are not creating any new array.
So over here also you can notice that I have array as 54031.
And then we call quicksort on the array.
And then we are just console logging the array.
That means this array over here which was looking like this is now changed once we have sorted it.
All right.
So this is the implementation where we are recursively calling quicksort on both the left and the right
sides.
Now let's run this and see whether this is working.
So let me clear my console and I'm running it.
And you can see yes it's working 01345.
We are getting this also sorted.
Now in the next video let's try to compare the call stack in both these implementations.