Hello all and welcome back.
So in this video let's continue our discussion on sorting and recursion.
Now in the last couple of videos we learned about Merge Sort.
We understood the intuition and saw some examples and then solve the same using visualization as well
as writing a proper working code.
Now in this video, similarly, I'm going to introduce you to quicksort.
I'm going to first tell you the intuition.
Then I'm going to show you an example and give you the code skeleton, where I would like you to try
out the solution or try out the code once.
And then in the next video I'm going to discuss the solution.
Okay, so let's get started.
Now the basic idea behind quicksort is actually a little bit different from merge sort.
So that is the first thing which we have to understand in merge sort.
Whereas first we were calling the merge sort to go and sort our array, sort the part of an array.
And then we used to do our work which was the merge function, the merging of the two sorted half.
In quicksort we say that, okay, we are going to do our work first and then let recursion take care
of the rest.
Okay.
So let us of course understand the same using example in quicksort okay.
Unlike merge unlike merge sort we first do our work and then let recursion handle the rest.
Now, I would like you all to focus a lot here, because Mergesort and other sorting algorithms actually
were still a little intuitive, like we were having some real life use case, like for example, in
insertion sort we have the card use case.
Similarly, merge sort was also intuitive in a way that we can divide it in half.
Quicksort.
I personally found that it is something which by default we might never come up right.
So if I just I will be giving you the example of that students in an assembly as well.
Again.
But that solution is actually a little bit tricky to understand or think of in the starting.
But once you understand it properly and I'm going to make sure that I do that for you, then it will
be a lot clearer.
Okay, so now of course, let's go to the example only.
Our main aim is to make sure that we are able to sort the given array okay array or list.
Now let's say this is the array which is in front of us is given to us.
And of course we need to make sure that we are able to sort the same.
Now quicksort.
Quicksort works on the principle wherein we pick up an element so you can pick up any element.
I by default tend to pick up the last element.
Okay.
So you pick up an element, we call it pivot.
And on top of this pivot like we have to do something.
Whereas what we will say is that we are going to take this pivot to its right position.
Okay.
We are going to take its pivot to its right position.
Now if you think about it, what exactly will happen when this pivot?
The number six is at the right position.
All the elements.
So there are I think two things which are going to happen.
Okay.
It's first it's going to get moved to its right position.
Okay.
All the elements which are less are going to be it's on its left side.
All the elements which are left are less than six are going to be on its left side, and greater than
six are going to be on the right side.
Right.
Because if you think about it, then is when six will say that, okay, I seems to be in the right position
now.
You can of course think of that with the student example as well.
Like you are all good if let's say you are able to see the assembly, right?
So that is what we took in this example from the starting only.
So once you have reached the right position and everyone in front of you is smaller than you, and everyone
in back of you is actually greater than you.
Then is one.
You can say that.
Okay, I seem to be on the right position right now.
Yes, the order might be different as of now, but we will see that.
So what I am saying now, let us visualize the same when I pick up this six when I pick up this six,
I have to somehow I have to somehow get this six to its right position.
Okay?
I have to somehow get this six to its right position, and then I have to make sure further.
Then I have to make sure that further I am going to divide this array in such a way that everything
less than this six is on this side, and everything greater is then on this side.
Okay, so I will repeat this once again.
This process is known as partitioning okay.
So we are partitioning our array similarly.
Right.
So I am picking up an element which is known as pivot.
Now you can pick up any element.
That is not a problem I tend to pick up the last one and that is a very good practice.
We are going to see that in the next module as well.
Why that is.
So now you are going to first bring this pivot to its right position.
Okay.
And then we are going to do something.
Then we are going to do something such that everything which is less than this pivot is on the left
side and greater than this pivot is on the right side.
Okay.
Greater than or equal to.
So we will handle this equal to sign based on how we are moving things.
So that will also be clear.
Okay.
Once I have done this once I have done this and say I also know that okay, where I have moved my pivot,
then all I have to do, all I have to do is call my recursion on this and this half.
Okay.
Now the understanding is again, I have kind of divided my problem, right?
I have divided my problem into smaller same problems.
So once I know that okay, this is the part and this is ah, this is the part which I have to sort.
And I am sure that okay, along this partition, along this partition, everything on the left is smaller
and everything on the right is smaller.
If now I get everything sorted here and everything sorted here, then I can surely say in the end that
my array will get sorted.
Okay.
So let me explain it using an intuitive example as when a working example.
So pay attention everyone.
This again is the same one the students in an assembly.
Let's say students are standing in this way in an assembly.
Okay, so these are the heights.
Now, I am sure that you must have listened this particular example a lot of time for me.
So students are standing.
I pick up this fourth one.
I pick up this fourth one I as a teacher, my I am a sorter, okay?
I have to make sure that I am able to sort them properly.
First I ask this for that.
Okay?
Hey, where should you actually be?
Where should you actually be?
So fourth, say that.
Hey, I see that three students, three students are smaller than me.
Three students are smaller than me.
Okay, so we are going to what we are going to do.
I can tell you here as well we are going to start counting.
Okay.
We are going to start counting.
Let us say from I is equals to zero all the way till n minus one.
So if this is my n right or length of let us say from this element.
So whatever this pivot is okay.
Or let me take it's and e in terms of s and d.
So I am going to start my I from S and go all the way to E minus one.
Right.
I'm going to go all the way to E minus one.
Now I will be counting that.
How many elements are smaller than me?
Okay.
Once I have counted that, I will actually get.
Where should I be in this particular list?
Okay, in this particular list or array, the one which I am actually considering, where should I be?
So force is that.
Hey, I seem to I feel that I should be here because I know that three elements are smaller than me,
so I should keep the spaces for them, right?
So this is the half work done.
So initial part picking up the pivot.
Second is moving pivot to right position.
And now I will come the third part okay.
Where I have to make sure that these red ones are the bigger and these green ones are the smaller than
my four.
Okay.
I have to make sure that somehow I am able to send this six backwards, okay?
Because this is bigger and similarly bring this to forward.
Okay.
So let us see how we are going to do that as well.
Now again, I am going to make sure that we are doing everything with respect to the pointers here.
Again, this approach has been discussed a lot of times now in the starting as well.
So please make sure that you see the previous video if any doubt is there.
Now let's say I take this as I okay which is equal to s.
And so let me just draw it in terms of area as well.
Let's say this will be some of my area okay.
Now what I have to do, what I have to do is I have a start and I have a end.
Okay.
So I am just assuming that I'm picking up the problem from between.
Again, if it is the starting, then S is going to be zero and E is going to be your length of your
list minus one.
Now once I bring my four at this position, all I have to do is I can start one I from here and one
J from here.
Okay.
Now pay attention.
This process is very important.
First I am going to check if I is greater than sorry.
If I is less than four, I is less than my pivot.
Yes.
So I can move my I to this position right.
Next I can check if my I eye is smaller than four, again, it is not okay.
If it is not, then we are not going to move I.
We have to do something here.
We will see what we have to do.
But we will do something here.
Once I have done this for I now next I'm going to move for J.
Is J greater than four?
No, it doesn't seem so right now.
What I'm going to do is I'm going to swap both of them.
So I'm going to make sure that I swap both of them such that finally I will get my two here and my six
here.
J will be at this position and I will be at this position.
Right.
So this is one, this is five and this is seven.
Now I will check if my I, if my I is less than four less than pivot element.
Yes.
So we are going to move and I'm going to stop on I now because of course I as a element okay.
It has to just move towards the pivot element only pivot index.
Now I'm going to talk about this J.
J is this for five greater than pivot.
Yes it is.
So let me remove it here.
Now similarly, is this seven greater than four?
Yes it is.
So I am going to move it here.
And once they reach towards the middle okay.
Towards where my four pivot was, I am going to stop my whole flow.
And then in the end, as you can see, I can say that my whole array is actually partitioned.
It is partitioned in such a way around four that everything on the left side of four is smaller.
Everything on the right side of four is greater.
Okay, so I hope with this particular example everything is clear.
Everyone.
Now, let me just, uh, make sure that I can tell you how we can code the same as well.
So let us go to the VS code once.
So I am going to write my function.
Def quicksort okay.
It's going to get an L1.
I'm taking that I'm getting s and e as well.
So I hope that is fine.
Everyone okay.
So if s is greater than or equal to E then of course I can just return.
Right.
Because it's a single element.
Of course you cannot do anything there.
Now comes the major part.
Now is actually something which we have to do.
So let us understand this as well how we are going to do that.
Let us say we get an array.
Okay.
Let's say this is the array which we are getting.
Right.
And I am taking some part of this array.
So something like this I am taking right S and E.
The very first thing which I now have to do is I have to partition along some element.
So I am going to take this last element and I am going to call some partition function.
Right.
So I have to define some function.
Or I have to make sure that I am able to do this.
I am going to do it in a separate function such that this particular pivot goes to its right direction.
That is the first word.
First word, and second is to make sure that everything on the left of this pivot and on the right of
this pivot is smaller and greater, respectively.
Okay.
So this is the whole work of my partition function.
Okay.
And once this does one like once it is able to do this particular thing let us say it will also return
me the final pivot index.
Final pivot index okay.
Now, once I have this pivot index, let's say after doing the work it bought my pivot somewhere here.
So I have S, I have E and this is my pivot index.
Now all I have to do now all I have to do is to just call my quicksort again on this part and on this
part.
Right.
So what all I have to do again everyone.
So let me just first write this partition book.
So next up is my pivot index okay.
Where I'm going to call one function partition function okay.
It's going to take my L one.
It's going to take S and it's going to take e.
Somehow this partition function I will assume that it is going to do what I want okay.
Partition function.
Let me just copy this.
Yeah L1S and e.
And it's going to return me.
It's at the time I am taking it pass, it is going to return me a pivot index.
Once I have the pivot index, okay, then all I have to do is just call my quicksort on s pivot index
minus one and quicksort on l one, pivot index plus one and e.
Right.
So these are the two parts which I am going to get from.
And I can return it.
So yeah that is the whole flow here.
Like just like the merge function was the major driver in merge sort.
Partition function is a major function.
So I have explained you how.
So again this is going to get from here.
So this is P I minus one.
And this is p I plus one okay.
So again I will quickly repeat all the steps so that you are comfortable in writing this code I have.
First make sure to explain you intuitively and using this example that okay what is our main aim or
the basic idea?
Now I know that okay, this is not normally very sort or anything in front of us.
That is not how we do it.
But yes, this is of course one of the awesome way we can sort things as well.
Our whole aim here is that we are able to bring each and every element, one by one, on its right position,
and then sort the left over part on both the sides.
Okay.
So again, I will just repeat the steps so that you can write this code properly yourself.
I will be getting and let me use another pen.
One second.
Yeah.
So everyone I will be getting a list or an array.
I have to pivot, pick up a pivot S and E.
Okay.
I have to call partition function.
This partition function what it is going to do.
It is going to transform my list in such a way.
It is going to transform my list in such a way that.
This particular element, this particular element is get to its right position, which is p I.
And it returned me this p I.
Okay.
So here I am getting this.
So this is going to get L1S and E.
Once I have this I just have to call my quicksort on L1 s and this particular thing, because now this
pivot is at right index p I minus one and quicksort on l1 p I plus one and e okay.
Just one thing you have to handle.
Make sure that the two steps which are involved right.
The first one is finding the right position of the pivot.
And second one is to shift the elements you compare or you handle the equal to sign in both of them
in the same way.
Okay.
So let us say, while you are counting the right position, make sure that you are able to handle that
okay.
If you are considering equal to as greater or smaller and the same thing in this pivot two while moving
the same as well.
Okay.
So yeah, I hope that helps in understanding the same.
Now please make sure that you try to code it once.
Okay.
In the next video I'm going to discuss the solution with you all.
As of now, I think that I have given you a good idea about this particular thing.
So now we have to make sure that we are able to write a proper working code for this.
Let me give you a test case as well, which you can try.
So L1 let us say 36721454.
And all I have to do is just call my quicksort on this.
Okay.
So L1 zero and length of L1 minus one.
Okay.
So this is very important.
We are calling on length of L1 minus one.
And I can just print my L1 now.
Okay great.
As of now of course it is going to give some error.
Like I have not worked it out.
It is returning a null.
So yeah it should be fine.
You can just write the partition function just like you completed the merge function.
And quicksort is going to work fabulously.
Please make sure that you take a proper pen and paper.
Assume first and then when you have written the code, then try to draw the tree and everything.
This is just like following all the steps in the framework which we have discussed, because that is
that is going to help you fabulously in solving these problems.
Okay, so cool everyone, let's meet in the next video where I'm going to give you the solution and
write the same and help you to visualize the same also.
Okay.
Thank you.