Hi, everyone.
So in this video, we are going to discuss about the quicksort algorithm, so this is also a recursive
algorithm, just like the heart and quicksort algorithm is also very fast.
So now let's discuss the algorithm.
What is quicksort algorithm?
So given an array and I want to sort this out.
So let's take a random area.
So this is eight five two two one, seven, three and four.
So is I don't know.
Now, I want to sort this out with the help of quicksort.
So what Quicksort says is pick the last element.
So the name of the last element is basically pivot.
So what you will do, you will rearrange your elements.
So you will rearrange the elements such that so Ford will be present here.
So all the elements greater then for all the elements.
Good four will be present on the right hand side, all the elements, less than four will present on
the left hand side.
So to one entry, they are smaller than four.
So two, one and three will be present on the left hand side and eight, five and seven.
So they are larger.
So the president on the right hand side.
So seven, eight and five.
OK, so these parts are not sorted.
These parts left and right hand side of what?
They are not sorted.
So what do you need to do after picking the pivot?
So after taking the pivot element, you will rearrange the element in such a way that forward will be
present at the correct position.
So this is the calculation of forward in this today because all the elements, less than four, are
present on the left hand side.
OK, so this is the calculation of four.
So what you need to do?
I am repeating myself again.
So this is our area which we want to sort, and the last element is X, so what I will do, I will pick
X and the last element is called pivot in quicksort.
So after picking the X material, you will put X in its current position.
So all the elements good.
The next will be present on the right hand side.
All the elements less than X represent on the left hand side.
So this thing rearranging.
So this rearranging thing is basically called partition.
So this is called partition in quicksort.
So this is called this rearranging of elements is called partition function.
OK, so this is called partition function.
So here the spelling is wrong.
So this is called partition.
So after partitioning so let's say the Nexus B, let's say the index of Alimentarius, B, let's say
its index is basically B, so after partitioning.
So first step is basically partition.
So after partitioning, what you will do, you will apply quicksort on this area, you will apply a
quicksort on this area.
So after a plane quicksort on this area, since it's a recursive algorithm, so this will be so this
is a start.
This is and so this will be the last element will be minus one.
This is the starting this is B plus one and this is end.
OK, so what we will do, you will apply quicksort on this area.
So this area will be sorted.
So it will become one, two, three.
You will apply quicksort on this area.
So this area will be sorted.
So it will become five, seven and eight and four is present at position B..
So now your computer is sorted.
Simple.
So that's how quixotry Waldenbooks.
Similarly for this area, you will apply quicksort.
This is a starting, this is the end.
So you will apply quicksort on this area.
And similarly, you will apply quicksort on this area.
So this is the end and this is B plus one.
So basically it's write the code, let's write the basics.
I will only write the basic code and you will write the complete code.
So what I want to do is that there will be right, because I will change the area itself, the name
of the function is quicksort.
I will take the area, I will take the starting next.
I will take the next and what we need to do.
So what we need to do, what is our approach?
So our approach is very simple, we will pick the last element.
So this is the work of the partition function.
So partitioning function will put let's say the element is X, so actually present here, all the elements
go to the next present on the right side, all the elements less than X will be president on the left
hand side.
So this is the working of partition function and partition function will return the index.
So let's say the Nexus B. So partition function will return the units and we call it partition index.
Let's call it partitioning.
OK, so what to do, you need to apply quicksort on this area, you need to apply quicksort on this
area.
So this is the starting next.
This is the end of next.
This is the starting next.
This is B minus one just starting next for this arizpe plus one.
And the ending is.
And so quicksort algorithm is a recursive algorithm.
So first of all, the best case case is if zero element or one element, so start good, then order
close to zero or one element in that case that is already sorted.
So do nothing.
We will simply better done otherwise, but only to do so.
And B, I will call the function partition.
So I will call the function partition.
I will give Adi, I will give you starting next and I will give the ending.
So this partition function, so I will write the code for this partition function.
I will write the code for partition functions of partition function will return the next be OK, it
will return the next B.
So after getting B, what we will do, we need to apply quicksort on the left.
We need to apply quixotically.
Right.
So let's call the quicksort function.
Quicksort, so left-to-right starting next is a start and a Nexus B minus one and what is the right
area?
So Eddie starting next is B plus one and the next is end and that's all.
So now what we need to do, we need to write the code for the partition function.
So we need to write the code for this partition function, it will take at it will take new starting
and it will take the next.
So what I'm doing is so what I'm doing here, I'm calling the function partition, I'm calling the function
partition, I'm giving at it start.
And so I'm giving this area I'm giving the start.
Next, I will give the index since that is are passed by reference.
So it will rearrange my area, it will rearrange all the elements such that x the last element says
that X is present at its correct position.
All the elements will present at the left hand side will be smaller.
All the elements on the right side will be greater.
So this is the working of the partition function and it will return the index B so it will return the
index of X, it will then be simple.
So after getting B, what I'm doing, I'm calling quicksort on side.
So A start and B minus one start and B minus, I'm calling partition on this area.
So this is B plus one and so B plus one and OK, so that is the working of quicksort function.
So the only thing remaining to do is so now the only thing remaining to do is basically write the code
for partition function so it will write the code properly, then your algorithm will work.
So I will not write the code for the partition function.
You have to write the code it yourself, OK, you have to write the code for partition function yourself.
So let me explain you the logic and then you will write the code.
So basically there are many ways of writing the code.
So basically there are many approaches to write the partition function.
So let me discuss one approach so that the elements five.
Let's make a two one, seven, three and four.
So this is the area this is the starting next and this is the end, and it's simple.
So this is the pivot element I told you so.
The name of this element desperate.
So in this alternate what the correct position for.
In this auditorium, what will be the correct position of for so elemental, so we need to count, we
need to count how many elements are smaller than elements, so count smaller, which will be you will
read the area and we will count which elements are smaller than four.
So two smaller ones smaller, three smaller.
So these elements will come before.
So basically three so countermelodies.
Three, what do we do.
So you will.
You will.
Right.
Three plus the starting index.
So this is the starting index which is currently zero.
So zero blistery.
So the right index for position four is basically three.
Simple so that, you know, the correct position for four correct position for forestry, you know this.
OK, first of all, you will find out three by rating over the area.
So after finding out the three, you saw the value of start to zero for this area right now.
So triple zero is three.
And what you will do, you will strap so four and so zero one, two and three.
So you will step forward with one.
So when will we present that last?
And here the elements are eight, five and two, and it had elements are seven and three.
So first step is very clear.
You will count how many elements are smaller by taking over the area and then you will find out the
correct position.
So the correct position is basically.
So this is called pivot.
OK, this is called pivot index, which you are returning, which you are returning.
OK, so count smaller, plus the starting index.
So you will return this value.
OK, we will return this value.
We will return in the next three.
So after getting the next three, you will strap what is the value presented next to you?
So when is president so swappable enfold?
So when will the president at last and forward is presented?
OK, so now what we will do, we will take two variables.
So I will take one variable here.
I so I is present at start and I will take one variable here.
G G will represent that and simple.
So now compare it with four so each would be present on the right hand side.
So I will stop here.
Now compare one with the four.
So one should be present on the left hand side.
So strap I enjoy, so I will strap Angie.
I will slap it with one so no one is present here, it is present here, so I will move forward.
So now I is present at this.
So now this is a and G will move in this direction.
So this is G now compare five.
So five should be present on the right hand side completely.
So they should be present on the left hand side, all four.
So again we will swap.
So three will come here and five will come here.
Simple, so Jay will move in this direction.
So this is Gino, I will move in this direction.
So this is I know so to do is correct.
OK, to shoot the the left hand side and to the left hand side.
So do not move forward.
So this is your I checked seven so seven.
Is that correct.
So do nothing and move back.
So we will reach here and you can see what is my final area.
You will stop.
So the final rule is basically one, then three, then two, then four, seven, five and eight.
So now you can see.
This is the building next to me, so I will read Dante and all the elements, less than four percent
on the left hand side, all the elements good then for are present on the right hand side.
So that is how you can write the code for partisan function.
So this is approachable and you can write the code for this.
There are many other approaches to write the partisan function, so this is one of them.
OK, so now you can see the side is not sorted.
This out is not sorted.
So for sorting these two areas, I will call quicksort for the city.
I will call quicksort for this area.
So Bodanis will be sorted and our completed will become sorted.
OK, so what is the stopping criteria.
So stopping criteria is basically so I is moving in this direction.
Just moving in this direction so.
I should be basically less than Britannicus, so the next is basically three, so I should be less than
be the next and should bigger than be with the next.
So this will be your condition and develop.
This is a condition develop and then you can compare you will compare the elements I would be to next
with four and you will compare the elements with Ford and then you will swear you will do the slapping
part.
OK, so you can write the code for the partition function.
So this is it from this video.
I will see you in the next one.
Thank you.