Hey, guys, what's up?
So in the last video, we talked about Selection's art and this video, we will learn what is the Mozart
algorithm?
OK, so let's take an example.
So suppose my is.
So my ED elements are, let's say, five, four, three.
One and two, so this is my area, so where the resources compare adjacent.
So compare to descent, so for will be compared with five now in the final four, should come before
five.
OK, and started at four.
Should come before five.
Let's call it J.
And this will be Jellison.
OK, so this for sure to come before 5:00, so what I will do, I will swipe.
So this will become four.
And this will become five.
My because in the final four should come before five.
Now, compare this to.
Three should come before five, so strap again.
So three and five.
Now again, compare what should come before five.
So when.
Five now compare again to should come before five.
So, again, no swapping, so two and five.
So this is my new ADI.
So for.
Three.
When?
To.
And five, so this is my new area now, I will do the same look, compare for entry.
Today should come before 4:00, so step three and four.
Now compare.
One should come before four, so one and four now compared four and two to should come before four,
so swept through two and four.
Now compare four and five.
So four should come before five do nothing.
OK, so do nothing.
OK.
Now, our new is.
So when you raise.
Three.
When?
Two for.
And five.
OK, so compar.
One should come before three, so swapper.
Now compare.
Those should come before 3:00, so Swapper.
Now compare.
So this is correct.
OK, three should appear before four, so do nothing now compare four shall come before five.
So do nothing.
Now, our final array's.
So this is our new Eddie.
One.
Two, three.
Four and five.
So this is auditoria, and this is my final answer.
So what if you will follow the same approach, SVREP?
So they compare, compare what will happen, they are a degradation, do nothing.
Compare, they are the correct position, do nothing, compare, do nothing, compare, do nothing.
So this is my ordinary.
So my question to you is, how many times do we have to show how many times we have to do all this?
So in this case, I was having five elements.
So if I am having five elements, how many times I have did so?
First time.
Second time.
And third time, so I did three times, so after doing three times, I got my answer.
OK, so if the number of elements was five after doing three times, I got my final answer.
Now.
Now, let us consider the worst case.
So what will happen in the worst case, so what will happen in the worst case, my area will be reversed,
sorted, so reverse order means my area will be sorted in reverse order.
So for three, two and one, so my atoms sorted in reverse order.
So this will be the worst case.
OK, so this is worst case.
Now ahead, we will try to understand that for any limits, how many times we have to do something so
compare and step three and four compare and strap so to full compare.
And so when and for the first time, for the first time, I knew it is.
Three to.
When and so this is my new editor, come back and sweep, compare and sweep, come back and do nothing.
So second time.
Now adays.
So.
My ETA is to.
Then one, then three.
And then for.
So compare and swap, so when we come here to come here, come here, do nothing, compare, do nothing.
So third time.
So after doing three times.
So after doing three times, I got my final answer, my record sorted, one, two, three and four.
OK, so my add is sorted.
So this was the worst case.
And I have to do three times the number of elements are four, so I have to do three times.
OK, so this wrapping things I have to do three times so we can also say like this that.
For sorting in numbers.
For sorting in numbers, what to do is short and minus one numbers short and minus one numbers, you
want to sort end numbers, I'm saying you habibti sort and minus one numbers.
So if and minus the numbers are sorted.
That means if they are at their calculation, then the last number will also be at its current position.
OK, so that is the reason for any calls for I have to do the stabbing two times.
Why?
Because for sorting in numbers.
If we start and minus one numbers then the last number will automatically get it correct position.
So it is very simple.
First of all, how many times do we have to do this wrapping things and minus one times so count to
close one count less than what it was two and minus one times.
We have to do this Sappington and the count plus plus.
OK, now I will start from zero.
I have to start from zero.
The zapping you can see here.
The thing was that starting from zero, and this is and minus one.
OK, so the will start from so this is G and this will be the final value of G.
So Jay will go from this to this David Hotel and minister to minus two, because I'm comparing Jay and
Jay plus one, if you will take Jay here, then Jay plus one will become and and if you will.
Right.
LFN, that will give you segmentation fault.
So they will start from zero, G will go to second last position and C++, so what I was doing if.
If Jay is greater than F.J. plus one I am comparing to our descent values, then what I will do, I
will slap.
Slap, A.J., and the object lesson.
So this is all that we have to do.
OK?
So Vion minus two.
So if the value of Jay and minus two and minus two, so this value will become and minus one.
Correct.
Now put Jaquiss and minus one.
So if you put Ajin minus one this value will become and because.
And minus one.
Plus one.
So this value will become and and you are doing aof and.
Segmentation fault.
So that is the reason I will go to hell and Minnesota.
OK.
So this is all that we have to do.
So if.
So this is my job and this is Jay plus one.
So I believe it should happen.
The value at the J should be less than value plus one to get element sorted in ascending order.
So if Jay is bigger, if it's bigger than swamp, then we have to swap.
OK, so let us write the code.
So one more thing before writing, or have you noticed one thing here?
So if you look carefully, the biggest value in forced arbitration reaches its correct position, so
five is the biggest value in the area and then one five reach its correct position in second iteration,
the second largest value reached its correct position.
Similarly, in the third iteration, the third largest value got its correct position.
And similarly, there are two.
And then when you can see here also.
So in the first iteration, the largest value got its correct position in the second iteration, the
second largest value got the second largest value, got its correct position in the third iteration,
the third largest value got its correct position.
OK, so you can see.
In the first iteration, so first iteration, largest value will come, largest value will reach, and
in the second attrition, the second largest value will reach at its correct position.
Third iteration, the third largest value will reach at its highest position.
OK, so my error is getting started in this way.
So this is my unsorted.
And this part is sorted, so the sorted is in this way in case of selection's.
So if you remember.
And selection sort, what we did was, if you are standing here, find the smallest value in the right
hand side and put that value here.
So in first iteration, the smallest value will reach added position in the second iteration, the second
the smallest value will reach at its correct position in attrition.
The third smallest value will reach at its correct position.
So any selection, sort of what is happening might add is getting sorted in this way.
So it is getting started in this way and this part is unsorted.
And in case of bubble my is getting sorted in this way and this part is unsorted.
So this is sort of my area is my area is getting sorted in this way, first and largest value, the
second largest, then third largest and her first port smallest value, then the second smallest value,
then third smallest value, then for smallest value and so on.
I guess that's why the call for Assad to the court is very simple.
How many times do we have to perform this webbing and minus one times, OK?
Why?
Because we have already seen the worst case.
In worst case, if the value of friend goes forward with three times.
So we have to do and minus one times.
And they will start from zero, I will start campaigning from zero, I will come back and plus one since
I am using their platform, so the maximum they will be on minister.
OK, that maximum level, they will be in minus two because I am comparing David J plus one.
OK, so for J.
Question minus two.
This way.
Lewis and minus one.
So if it's good, then lesson, then I will do something.
So right outside the cold.
So let us nameless, faceless babble sort.
So there was Art and Art CBB.
So let us take input from the user.
So far, and I equals zero, I lost and I plus plus seven if I let us make an error.
So the size of the arrays and.
Now I will write a function, bubbles or so bubble, what bubbles heart will take as input, so bubbles,
it will take two things it and the size of the eddy and it will start my eddy.
So my heart is ordered.
Now let us print this after Eddy far and die equals zero.
I less than in a plus place.
See I would if I.
OK, so the Court of Appeals thought so this function will return void, OK, because I'm just sorting
that I'm not returning any value to mean so bubble.
So it is taking to things as input first lady and second, the size of the Harry.
So for how many times and minus one times count equals one count less than an hour equals and minus
one count plus plus.
Now, what we have to do, we have to just compare and numbers, so I'm starting from zero G is less
than articles two and minus two.
So this is important.
And minus two J.
Plus plus.
Now, what he will do, he will compare their DNA to numbers.
So if F.J. is greater than of J plus one, then you have to swab.
So swab.
F, G and F, g plus one.
So this is all that we have to do.
OK, so I told you Ariha Pasta, Bio-Reference.
So if I am changing the values of at O'Haire, this changes will be reflected in function men.
OK, so one more time I told you when you pass ETA to a function, then they are passed by reference.
So if you will do changes in the Eddie, those changes will be reflected in the main function in the
calling function.
Certain number of elements are faith and the values are, let's say, five, four, three, two and
one.
So this is my output, which is sorted.
Let's say MPs are five and the elements are five, four, three, one and two.
So again, this is producing the correct output.
So let's say the number of elements are four and the elements are 30, 20, 10 and 50, so elements
are getting started.
So this is how it works.
OK, so now let's discuss one last thing.
So how many steps it takes to start?
So this outer function is running approximately and minus one times, so outer loop is running and minus
one times and inner loop is also running and minus two times.
So a number of steps, a number of steps equals and minus one and two and minus two.
OK, so these are the number of steps.
So if you will multiply them, we will get and squared them, then income and then some constant.
OK, so let's put an inquest into the power six.
So this value will be 10 to the power to this value will return to the power of six.
And this is something constant.
Now tell me in front of this, does it have any significance?
No.
In front of to the power, to oil and to the power six is nothing.
OK, so I can say the number of steps is a close to and square.
OK, so the number of steps is actually called time complexity.
Time, complexity and complexity means how many number of steps your program took to execute.
OK, so this thing is clear, so how we report and complexity, we will write big or record and square.
So this is called time, complexity of bubbles.
So this is the time, complexity of bubbles.
So what was the time complexity of selection start?
So time, complexity of selection, so was also in the square.
OK, so selection's our time.
Complexity was also in the square and the time complexity of bubbles is also and square.
Now, any idea why we calculate time, complexity?
So.
Suppose you want to buy a car.
So what we will check it will check what is the mileage, what is the cost?
How many number of seats?
What is average speed and there are many factors.
OK, so for deciding which car to buy, you will see many factors.
OK, so there are many sorting algorithms.
There are many sorting algorithms.
How we will decide which sorting algorithm is best.
So what we will do, we will find how much time is my program taking to execute the algorithm, which
take the least amount of time, the algorithm which takes the least amount of time, is the best algorithm.
OK, so that is the reason we calculate the complexity of the program to compare to algorithms or to
compare two programs.
So both bubble sort and solutions are both complexity is and where they both take an equal number of
steps to execute.
OK, so actually, time complexity is a very big topic, I have just given you an introduction to time
complexity.
That is why we calculate time complexity.
OK, so this was just an introduction to time.
Complexity and complexity is a big topic.
OK, so this is it for this video, if you have any doubt in the heart, you can ask me.
Thank you.