- 2 days ago
Transcript
00:00Next, we will talk about sorting time complexity. We have a example of bubble sort.
00:05We will discuss it in a lot of detail. After that, you can analyze the selection, insertion and counting sort.
00:14If we talk about bubble sort, we will take two cases in bubble sort. First is my worst case and
00:18second is my best case.
00:19What is the worst case for any sorting technique? If I have to sort in ascending order, what will be
00:25the worst?
00:26The worst case is that my elements are arranged in descending order.
00:30If I have an array in which I have 5, 4, 3, 2 and 1, I have to sort it.
00:39Which form should I take it? I have to convert it in 1, 2, 3, 4 and 5.
00:44Here I have to make maximum effort.
00:47Because it is completely gone. One of the elements is not in the right position.
00:51It is completely gone, so there will be swaps here.
00:53If we remember here, the code of bubble sort was something like this.
00:57I had to run my loop outside. I was able to run from i is equal to 0.
01:01I can also call this turn.
01:03I is less than n-1.
01:04J is less than n-1-i.
01:07And every time it is j++.
01:09And here we were swapping.
01:11So you can see, in the swapping, it is 1 operation, 2 operations, 3 operations.
01:18So this is my constant work.
01:21Now I have to remove time complexity.
01:23So first, let's talk about worst case.
01:25Here I will write my case 1 time complexity.
01:28Here I will write my case 2 time complexity.
01:30In the worst case, if I have a sorted array in descending order.
01:36So what will I do in reverse sorted array?
01:39What will I do in reverse sorted array?
01:40What will I do every time?
01:41I will go to n-1 to the outside loop.
01:44And for every turn, how will I perform my loop inside?
01:48The outside loop will work to n times.
01:51So first, it will be 0, then 1, then 2.
01:54The value of the turn is 0, then 1, then 2, then 3.
01:57Where will I go to n-1?
01:59Where will I run the outer loop?
02:01The outer loop will run the end times.
02:03Now I will show the inner loop.
02:05For every turn,
02:09I should be 0, I should be 1, I should be 2.
02:13How will I run the inner loop?
02:15We will see inner loop.
02:17The value of the inner loop is always 0.
02:20N-1-I.
02:23What happens every time?
02:24Every time I have constant work,
02:28So what can I say?
02:29My loop every time
02:31I is equal to 0
02:32Where is j equal to 0
02:36N-1
02:37I is equal to 1
02:38Where is my inner loop
02:42N-2
02:43I is equal to 2
02:44J is going to 0
02:46N-3
02:47I is equal to 3
02:48I will go to 0
02:52I will go to 0
02:55I will go to 0
02:55I will go to 0
02:55I will go to 0
02:58In the worst case
03:00How many times I run
03:01J is going to 0
03:03N-1
03:04N-1
03:07N-1
03:08N-2
03:09N-3
03:12N-1
03:14N-1
03:22N-1
03:24N-1
03:28N-1
03:30N-1
03:30N-2
03:31N-3
03:32N-1
03:34N-1
03:36N-1
03:38N-2
03:42N-1
03:44N-1
03:47N-1
03:481 or 0 is coming in the last
03:49so this will be k of n square
03:53so here will be my big of n square
03:55my bubble sort of time complexity
03:58to remove this, a little easier approach
04:02what do I see?
04:04how many times I run the outer loop?
04:05n times
04:06then I see how many times I run the inner loop
04:08I know the inner loop in my worst case
04:11will run n times
04:12so the outer loop will run n times
04:14and for the inner loop
04:16will run n times
04:181x if either outer loop run
04:19will run n times
04:212x will run, inner loop 2n
04:242x will run n times
04:25our inner loop will run
04:26n times will run so how many times?
04:31with n times
04:44How much will it be?
04:46n square by k
04:47So time complexity is n square by k
04:50So because we ignore constants here
04:53This will be bigger of n square
04:54So both approaches are correct
04:56This approach will be built with experience
04:59When you solve 10 questions in loops
05:02This approach will automatically start in the brain
05:05After that, we don't have to analyze the loops
05:08After that, we will know what is the time complexity
05:11There will be a little time, it will be more practice
05:14But if you do practice, then you will become a master of time complexity
05:18And in interviews, it will give you the strength and confidence
05:23It will not give you much more
05:25As long as we practice the time complexity and space complexity
05:28So confidently, we will solve the next questions and understand
05:33Now this is about the worst case
05:36If I talk about the best case, then what will happen in the best case?
05:40In this case, my time complexity will also be big of n square
05:42Why will it be?
05:44It will be that if I already take sorted array
05:471, 2, 3, 4 and 5
05:49So for sorted array, I didn't have any conditions
05:53Let's suppose I am at i is equal to 0
05:55For i is equal to 0
05:57I will go to j is equal to 0
06:01So I will compare it with this value
06:03Then I will compare it with this value
06:04Here is my comparison
06:07Here I will compare it with these values
06:09And when I compare it with values
06:11When I have compared it, I realized that
06:13Array of j is not greater than Array of j plus 1
06:16So my comparison will be false
06:18So this is not my case
06:21It will be a part of the other operations
06:21But these operations are already
06:23The other operations are also in turn
06:26And it will be a part of the other operations
06:27And the other operations will be big of j
06:28There will be a part of j
06:29So there will be any functions that are at that
06:32So if my array is sorted
06:35Completely sorted which is my best case
06:37Then the code of bubble sort
06:39This will give me the time complexity of big of n2. Why? Because if my array is already sorted, then
06:47my operations are performed.
06:50If my array is already sorted, then it will increase the value. Now it will compare them, no work.
06:56Then it will increase and compare them, then it will not be swapped. Then it will compare them, then it
07:01will not be swapped.
07:02But when comparing them, the value of j is increasing to last and i also increasing to last.
07:08I should have a mechanism that I should know that if these values are not increasing, then I will stop
07:14this loop that my array is already sorted.
07:16So in this case, I have to write an optimized bubble sort.
07:22When we discussed the bubble sort, I told you that for tracking this swapping, I can create a boolean variable,
07:29swap.
07:31What do I do here? I will write the value as false here.
07:35And as it has been swapped, I will make it true.
07:37And I will check here that my swap value is true.
07:41If swap value is true, then I have swapped.
07:44I mean, there will be some things in my array.
07:47My array is already sorted.
07:49So in this case, I will increase.
07:51Or else I will break.
07:52I will check.
07:53I have already explained in the bubble sort of value lecture.
07:57And I have given it as a homework problem.
07:59That you have to implement the optimized bubble sort.
08:02So in that optimized bubble sort, there is a time complexity in the best case.
08:05But if we have written a normal bubble sort, I can summarize that the worst case time complexity, that is
08:14big of n-square.
08:16And the best case time complexity, that is also big of n-square.
08:21There is no difference between both.
08:22But when the advantage comes when we use the optimized bubble sort?
08:26Now I have optimized bubble sort.
08:28If you have not done homework problems at that time, it looks like this.
08:32I have given it as a modified bubble sort.
08:34What did I do here?
08:35I have made a boolean variable swap.
08:37I have made it with false.
08:39What did I do here?
08:40I will check my condition.
08:43I will check my condition.
08:43I will check it.
08:44I will check it.
08:45In this loop.
08:46If there is also one swapping.
08:48It means that my area needs to be sorted.
08:51It needs to be sorted.
08:51It is not sorted already.
08:53And if this is never true.
08:55I have cut the entire line of comparison.
08:58You have compared all the elements on the entire area.
09:01But no one was like that.
09:03Everyone was in the right place.
09:05So the swapping will be false.
09:07And I will break from here.
09:08So my value will not increase.
09:10So this is my modified bubble sort.
09:13The worst case of time complexity.
09:15It comes to big of n square.
09:17But my best case of time complexity.
09:20It comes to big of n.
09:22How will it come to big of n?
09:24I will see.
09:25I will make a small area.
09:27Three sizes.
09:29What will I do here?
09:30The value of i will be 0.
09:32I will write this turn.
09:33And j is j.
09:35When i is 0, what will I do?
09:37My swaped variable.
09:40I have initialized it with false.
09:43Inside the line.
09:44Now I will start the j.
09:46The value of j is 1.
09:47As first of all, the value of 0 is equal to 0.
09:48So 0 is equal to 0.
09:50Where is my index?
09:51My index is here.
09:52Will compare 0 and j plus 1.
09:56That means i will compare it with one with 2.
09:58When this one and 2 will compare.
10:00It will compare one with 2.
10:00To be compared with one with 2.
10:07obviously not so this value will be false, so I will not run all the lines here
10:12so I will return j++, j value will increase 1, j value will be 1
10:19now what will be comparison? now the comparison will be here, so 2 is greater than 3
10:23this also is false, so this value will not run again, I will increase j++
10:29j++ and j++ becomes 2, as j++ becomes 2, what was the length of my array?
10:35n is equal to 3, and when will my j run?
10:39I had to run from j is equal to 0 to n minus i minus 1
10:45i was equal to 0 to n minus 1, i was equal to 2
10:49and it is equal to 2, so now I will go out of the loop
10:54because for 3 to compare, there is no element, so I have compared all of them
10:59so as I will go out of this loop, I will check whether swapped is equal to false
11:05swap is equal to false, swap is equal to false
11:08swap is equal to false basically means that 1 is also swapping
11:11if there was a bubble sort, then 1 is also swapping
11:14in this case, there was no bubble sort because it is already sorted
11:17so swap is equal to 1, so swap variable is false
11:20swap variable is false, if swap variable is false, then I will do break
11:23break means that I will go out of the loop
11:25I will become 1, I will become 2, I will become 3, I will become 4, I will become 5
11:31I will become 3, I will become 4, I will become 5
11:32in one turn, I have told that I got a completely sorted array
11:37which means that I got a better case
11:39and what happens in that case
11:42and what happens in that case
11:43What happens in that case
11:43My loop is big of end times
11:45that means that just end times
11:47my loop will go out of the loop
11:49if I have got optimized or modified bubble sort
11:51so we always write some of the bubble sort
11:53so we always write some of the bubble sort
11:54we always write some of the bubbles sort
11:55Yes, in the worst case
11:57there will be enough time complexity
11:58But in the best case, or in a little bit, the time will be a little less.
12:04The time complexity will keep up.
12:05If we get the best case, then the time complexity will come back to the end.