Hello all and welcome back.
So in this video let us continue our discussion on quicksort.
And now let's write a workable code for the same.
Pretty sure that you have tried the same out once at your end, if not a humble request to do the same.
Even if not fully, you will be able to get 7,080% gist of it and the rest will get clearer in this
video.
Okay, so now let's get started.
Uh, for simplicity, just for this particular case, I am just removing this extra for, uh.
Again, that should not be a problem.
I will be taking that towards the end as well.
What I'm going to do is, uh, basically let me just copy this into a different file so that you can
like code on that.
Once you get this file, what I'm going to do, everyone here is first, let us, let me actually work
on this partition function.
Because actually if I see this is the main function here right.
Partition function is where all the work is happening.
Nowhere like this is the major.
Just like in merge sort, when the merge function was there.
Here the same thing is happening in the partition function.
Okay.
So let me just go a little bit deep into this and explain you the same.
Now the very first thing is I am getting this S and E here, right?
I can like what I have to do.
What I have to do is I have to take a pivot here.
I have to take a pivot here.
And I have to make sure.
I have to make sure that I am bringing it to its right position.
Okay.
Just one more thing.
Which is the most common thing where we make mistake?
Where I used to make lots of mistake.
We can.
We have to always consider this as a part of some array.
Okay.
That's why we are dealing in terms of s and E okay.
So now the next part is to make sure that I'm able to bring this five to its right position.
For that what I can do is I have to start okay.
So just let me move this.
Yeah one second.
Yeah.
So let's say my I initially is s and I am taking one right position okay.
I am taking one right position also equal to s now.
So just to make it a little bit more easy I is here and my right position is also here.
Okay.
One second.
Let me just use one of the more feature nodes layers.
Second layer.
Great.
One second.
Okay.
No.
Second, everyone.
Okay.
Should be fine.
I was just trying to use another feature, but seems like that is a little bit complex.
But anyways, everyone just pay attention.
So we have this right index.
Okay.
Right position.
Sorry here as well.
So my understanding here is that I'm going to start and assume that okay it should come in the starting
I'm going to count how many elements are there which are smaller.
And if it is smaller then I'm going to just like increment this right position.
Okay.
So pay attention everyone.
This is my right position right.
First is I element at I which is three less than my pivot seems.
So.
So what I'm going to do I'm going to move my p here.
Let me make a different color pen.
I'm going to move my Sharpie here.
Okay.
And I will be I will be increasing at each and every point.
Now is my six greater than pivot?
No it's not.
So I'm not going to move my right position.
I'm just going to move my eye.
Similarly is my seven greater than pivot which is five.
No.
So I'm not going to move I sorry not going to move r p I is going to the next is my two less than five.
Yes.
Seems so.
So let me move it again.
So what I'm doing effectively here is I'm making space for all the elements which are smaller than me
using this right position index.
Right right position variable.
Now similarly, is this one less than my five?
Yes it is.
So let me move it here.
Okay.
And finally the four less than my five.
Yes.
Less than pivot index.
So I'm going to move r p again.
Okay.
And if you will see now this is where five should come.
This is where five should come.
Why is that?
Because I have just started from the s basically from the start of my day.
Gone till n minus one.
Basically just before pivot I have gone till n minus one just before pivot.
Okay, so all these I have covered and I have just allotted space for all the elements which are smaller
than me.
Okay.
Such that I know that okay.
Right now four elements are smaller than me.
So I need these four spaces.
Okay.
Just remove these four spaces I need.
And my r p is actually now at the right position.
Will request you to see this once again.
Okay.
If it is not clear.
But that's how we can get the position very nicely.
You can also count the same.
You can count let's say how many elements are smaller and then do S plus C as well okay.
That is also going to work fine.
But if you will see I am just incrementing it by every time.
And just that is how's plus C is going to get calculated as well.
Okay.
So this five is now should come here okay.
So let me do this every one.
So let me now just start coding in this partition function.
The first thing is I have to define my pivot.
Pivot.
I take L1 of E, right?
Once my pivot is defined, I have to define I is equals to S and right a right position.
Right position only so that your code is pretty nice for you all to refer.
Right position.
Now what I'm going to say is while my I okay.
While my I is less than equal to E minus one.
Okay.
So you can write less than E as well.
Uh, pretty sure by hope.
Like by now these things are clear, but I tend to make sure that the boundaries are very well defined.
Okay, if this is the case, if this is the case, then what I have to do is if my L1 of I if my L1
of I is less than pivot, if it is less than pivot, I just have to do right position plus equals one.
So I am just increasing my right position if that is the case.
And in any case I is going to get increased every at every step, right?
Because I am going to each element using I once this is done, once this is done, I actually have the
right position where my five should be.
Okay, so as of now my five is here.
Everyone.
My five is here, but I have to bring it here.
So what I have to do now, all I have to do here is now is bring my five here.
Okay.
So I just have to swap them.
And one here.
So this is what is going to happen for three, six, seven and two right.
So just this if I do I will be bringing my five to the right position.
And you can see that in left four elements, four spaces are there which are the four elements smaller
than five.
In the right two spaces.
Are there two elements bigger than five?
Okay.
So something which I have already explained in the last video.
Just want to make sure that you also grasp for how you have to write the code.
That is how you have to understand it.
One thing more.
Uh, please follow the framework.
Don't try to, uh, get a lot more depth into the tree, like exactly how it's going to happen or anything.
Just solve for the cases the way we have understood it.
Now, once I have actually got this, what I have to do L1 of right position okay and L1 of end okay.
This is something which I have to swap.
So the right position is going to go to end.
So what I'm saying is that this one it should go to five and five should come to my right position.
Right.
So five should come to right position one second.
Yeah I hope this works fine as well.
So all I'm doing is just swapping here.
So just move the end to the right position and right right position element.
The element which is at right position to that to end.
Okay cool everyone.
So yeah now once this is done okay I think I also have my pivot index something which I have to return
which is nothing but right index.
Right right position.
Sorry.
My bad.
Right position.
So this is actually the index right.
So if you will see in the last class where I explained you what we have to return.
So this pivot index, this pivot index okay.
It is something which my partition function returns, and I have actually got my pivot index from via
this particular code.
Now the work is half done.
Work is half done still.
Okay, so what I have to do now, make sure that everything smaller than pivot to left and greater.
To right.
Okay, so the work is half done as of now.
That is not something which I have to run.
Now again let me do something.
So start is going to be at S and my end.
End is going to be at E okay.
Now see what I am going to do.
I am going to say that hey while.
My start is less than pivot uh pivot index.
Okay, so while my start is less than pivot index and my end is greater than pivot index.
So now what?
All I'm doing is just trying to make sure that I squeeze these boundaries.
So this is my start and this is my end, right?
This is my pivot index.
I have to make sure that you know everything towards the left which is this part.
Okay.
That is less.
And everything towards the right which is this part that is more.
Okay.
So with that in mind, what I'm going to do, I'm going to start and compare.
If at start the element is smaller seems right.
Okay, I can move forward.
But once I move forward and go to six then I think there is a problem.
Six is not smaller than five.
So we have to do something.
We must somehow push it backwards.
Similarly, if my end it is not bigger then also we have to do something and yes, we have to then not
just swap both of them.
Okay, so let me just do this in code as well.
So it is a lot clearer.
Everyone pay attention.
If my L one of start okay is less than pivot.
Then I have to just do start plus equals one, right?
Else if L one of end is greater than or equal to pivot, then all I have to do is n minus one.
Now you will actually just understand one thing here that while I was trying to shift it to the right
position, I did not consider equal to here.
Okay.
And that's the same reason I am not now considering equal to here as well.
Whenever you are doing such kind of question, always have a practice of like fixing where you are going
to put this equal to okay.
So because I have not put equal to here, I was considering everything which is equal greater than my
pivot.
Similar thing I have to do here as well.
If that is not the case, if both the cases are like if everything is like let's say both the statement
fails, then what I have to do everyone, then I just have to swap these elements, right.
So L1 of n is equals to L one of n and l one of start.
Once I have done this start plus equals one and n minus equals one.
And yeah I think this is what all we have we should do.
And we should be good to return the pivot index.
Okay.
So just one thing I will explain you this a little bit more better.
So let me just draw here only and let me see what was our array.
3671 second 3672541.
Right.
So pay attention everyone
367254141.
What I am saying is my start is here and end is here.
So I am making sure that I am calling it start and end.
You can use them I or J as well.
That should be fine, but just make sure that you are not missing this sneer.
Okay, so that in worst case we have to use them afterwards.
These function arguments should be as it is.
Okay, now this is my pivot.
This is my main index.
If it is smaller, s can move forward.
Not a problem.
Okay then I am checking again for S.
Then I am checking again for S.
Here it is not smaller so I will go to E.
This is also not the case.
E is bigger now actually I will swap them.
Okay so I will swap them.
So it will become one.
It will become six.
This is what will happen when we swap them.
And I am going to move my S and E as well.
Now in this case as well if you will see my s basically okay.
This particular element is not less than or sorry, it is not less than my pivot.
Similarly E is not less than this.
Okay.
And now what I have to do now what I have to do again I will swap it.
So this will come, four will come here, seven will come here is going to be S and it is going to be
E.
Now one thing here, we do not have to actually check after if this after this our code will run.
The reason for that is If one of the if one of the start or end pointer is able to reach to pivotindex,
then that means that all the elements at that particular side is greater or smaller, right?
Because what I'm saying is that let's say if I start from here and it's able to reach to my pivotindex,
then that means that everything is smaller here.
And if everything is sorry, if everything is larger here, and if everything is larger here, then
for sure I can say that everything is going to be smaller here because I have counted my positions and
then moved my pivot.
I have counted my position and then moved my pivot.
Okay, so that's the reason we are not running these loops again, the way we were doing in merge sort,
because we are sure that, hey, if my end is able to reach, I know that, okay, it has just two positions
or five positions which are right for this particular case.
If I am able to do that, I should be all good and thus I can move for the same.
Okay, so cool everyone.
I hope with this it is clear.
Let us run the same as well to see if it is working or not.
So pretty big code we have written for this.
But yeah, I will just suggest to write these codes in the initial manner with good names and everything
so that you're able to understand the same as well.
Now quicksort.
Yeah.
We are calling and let me just run it.
Nice.
Seems that our code is working because we are able to get the sorted manner.
Let me now add another for as well.
Should not be any problem because you have handled this properly.
Okay.
And if I run it you are able to see 1234456.
Okay.
So yeah, with that I hope you are able to understand the same as well everyone.
Now one thing more I would like to show.
Same thing which I showed you in merge sort.
The way we have actually understood recursion and the way you are writing a partition function, you
can actually test it individually as well.
Okay.
You can test it individually as well.
How you can do that?
Pay attention everyone.
So let's say yeah.
So let us say I have this L1 which is like this only.
Now I have this partition function.
I am calling L1 zero and length of L1 minus one.
Right.
And I am printing L1 here for the time being.
Let me just, uh Comment everything down and see the understanding is if I have written my partition
function correctly.
This for.
Let me make it five as of now, because this is what you have understood on this five should reach that
is right position, and all the things on the left should be smaller.
All the things on the right should be bigger.
That is what our understanding with partition function is right now.
This thing of course will be a lot helpful.
Let us say you are not able to write this particular code.
Just check your partition function separately because everything lies there only now.
Why you should go on recursion and everything.
That is some smart work that you can do in your OS or in your interview or anything.
Which interviewer will also basically appreciate because you are able to break your problem into smaller
problems the way recursion does.
But yeah, okay, now if I run it and you see the output, okay, let me show you that output to you.
See I think it has done its work.
Five is at its position, five is at the position we wanted and everything on the right is greater.
Everything on the left is smaller.
Yes.
They are not sorted as of now, but that was not my work.
Even this part and this part recursion and quicksort will handle.
I do not have to worry on that.
Okay.
So again this is very very important stuff.
Everyone please make sure that you understand and see that okay.
For which question you can test like that.
And you will be saving lots of your time.
Okay.
So now let me just do one more thing.
Let me just try to showcase you this using a visualizer as well.
Again this might not this will be a little different from our case because we take one second here.
Let me run it.
Great.
So one more second.
Let me take erase only.
That should be fine.
It is seven length.
Yeah.
Cool.
So pay attention everyone.
What happens is that it is not going to take the pivot in the end.
As I said in the very starting to you that pivot, you can take any any element like you can take the
starting index, you can take the end index.
You can even take any randomly as well.
So what it's going to do is it starts a pivot randomly, then move it towards the end okay.
Then move to the end.
And then it works basically on the same principle.
So now it's the two pointers are here.
Okay.
Let me just zoom in a little bit.
So now these are the two pointers.
Okay.
What it's going to do.
Let us see the the overall I would say implementation might be a little different.
But let us understand.
Move to the left, one to the right until it reaches a value greater than or equal to the pivot.
Okay.
So we are just trying to move this left.
Let us move it.
Okay.
So it's saying that okay three is the biggest one.
So it's going to count.
Like this is also another way.
It is counting just nothing else.
Okay.
So it's saying that okay this is as far as we can go.
And it is just shifting it.
Okay.
Somehow it is like doing things.
But I hope you are able to understand this implementation is little different from what we have done,
but overall it will try that it is able to find the right position for pivot and that is what it is
doing directly here.
So it is just trying to actually see, okay, where the pivot should be and based on that.
So pivot it, move to the end.
And finally after some time it is going to move your pivot to two points.
See pivot is brought to the right position.
Now the next part.
Okay let's let's stop this.
Contain a single element which means it is sorted.
So this is our base case which is going to handle here.
And now it's going to call the same problem the same thing on the right.
Sub list.
Okay, I hope you are able to understand this everyone.
Because the two.
Was selected as a pivot.
It took to the end.
We can just ignore like how it did the other part.
That should be fine.
It brought to its true right position.
Now it's calling the quicksort on the left part.
Okay.
And I hope you all also remember that how we draw the tree in terms of Fibonacci, where yes, the left
part always is going to get first solved.
Now because it is a single element, S will be equal to e, and because s is equal to e, we are going
to just return.
So that's what it's saying.
Left sub list contain a single element which means it is sorted.
If it is sorted then we are just call on the second part and pay attention.
Now call quicksort on the right sub list.
Once I call it on the right sub list, it's selecting this three.
For this three it's going to move to the end.
So see it's move to the end.
Now it's going to find like do the partition okay.
So partition it might be doing in some different manner.
That should not be a problem.
Our implementation is more than good.
We have understood it intuitively.
I have explained you that exactly using that school example, and I hope you always remember the same,
so don't get confused.
Of course, there can be more than one way of doing any particular problem, right?
So it's going to do the partition.
Okay.
Move the left bound to the right until it reaches a value greater than or equal to the pivot.
Okay.
So it is saying that okay this is as far as it can go.
Similarly left it is trying to do to find the less value.
It did not find any less value.
So I think these things are there.
It's going to just send this pivot to the three.
Now again left quicksort on the right sub list because left nothing is there.
Now when we call on the right sub list again it selected a pivot which is six.
I'm going to shift it, do some process through which it will be able to find the right position.
Okay.
Once it finds it's right position it's going to send six to this particular position okay.
Let us see.
Yeah six is on this position now.
Five and four will come.
Five and four are going to get sorted.
Select the pivot as five shifted it to four.
Doing the partition.
We do not know how it's going to do it, but I think it is fine.
It is on the right position only.
So if it's on the right position okay, it's going to be here only.
Pivot is moved to the final position and now four and seven are left.
So it's going to call for four.
Okay.
Single element is going to get sorted similarly right seven single element.
It's going to get sorted.
And we have our own thing sorted okay.
So yeah with this I took it a little quick because major steps were the partition part.
And I don't want to confuse you.
So that's why I just showed you what exactly is happening.
Right.
The major of I would say in every iteration six seven steps of the partition problem, something which
we have done differently.
Okay.
So I don't want to confuse you.
And that's the reason I showed and basically just skip through it.
But I hope you get the idea after visualization that how things are moving forward here as well.
It was doing the same thing, finding a pivot, moving it towards the end, then finding the right position
to the pivot.
The partition was a little different, but overall it was able to see that yes, I am able to finally
move everything towards the left on the which is lower and on the right which is greater.
Okay, so that was the whole aim and the whole stuff which this particular problem did.
Everyone now same we have done here.
I have also told you how you can check this particular code in middle.
Okay.
So this is a very helpful trick I would say.
Let's just comment it and let me just comment this.
Remove comment here and we can run this one second.
Yeah.
So we are able to get this.
And yeah that is more than enough I think for quicksort it is going to work fine.
So please make sure that you try to write it yourself as well.
Again it's a little little bit difficult to grasp, but I hope with the intuition and with the understanding
which I have given you, you are able to understand it.
And now you will be good to write the same if it takes time.
Please make sure that you are giving the time.
Please make sure that you are drawing all these steps, even if you have to do all these 67 steps in
the starting.
Like let's say you are working it for the first time, please make sure that you spend that time okay.
Don't worry on that.
It's going to take time in the starting.
But as you code along a lot of recursion problems, it's going to become easy.
Okay, cool then everyone, thanks a lot.
So let's meet in the next video where we are going to start with recursion and strings.
Thank you.