1
00:00:01,470 --> 00:00:03,080
Hey, guys, what's up?

2
00:00:03,719 --> 00:00:10,080
So in the last video, we talked about Selection's art and this video, we will learn what is the Mozart

3
00:00:10,080 --> 00:00:10,770
algorithm?

4
00:00:11,190 --> 00:00:13,110
OK, so let's take an example.

5
00:00:13,410 --> 00:00:15,000
So suppose my is.

6
00:00:20,670 --> 00:00:26,130
So my ED elements are, let's say, five, four, three.

7
00:00:27,120 --> 00:00:34,560
One and two, so this is my area, so where the resources compare adjacent.

8
00:00:35,720 --> 00:00:43,190
So compare to descent, so for will be compared with five now in the final four, should come before

9
00:00:43,190 --> 00:00:43,640
five.

10
00:00:43,670 --> 00:00:45,740
OK, and started at four.

11
00:00:45,750 --> 00:00:46,930
Should come before five.

12
00:00:47,390 --> 00:00:48,710
Let's call it J.

13
00:00:50,200 --> 00:00:52,210
And this will be Jellison.

14
00:00:53,760 --> 00:00:59,590
OK, so this for sure to come before 5:00, so what I will do, I will swipe.

15
00:01:00,060 --> 00:01:01,660
So this will become four.

16
00:01:01,680 --> 00:01:03,330
And this will become five.

17
00:01:05,250 --> 00:01:09,150
My because in the final four should come before five.

18
00:01:10,260 --> 00:01:11,400
Now, compare this to.

19
00:01:13,330 --> 00:01:16,520
Three should come before five, so strap again.

20
00:01:16,540 --> 00:01:18,530
So three and five.

21
00:01:19,240 --> 00:01:22,410
Now again, compare what should come before five.

22
00:01:23,260 --> 00:01:24,070
So when.

23
00:01:25,150 --> 00:01:29,350
Five now compare again to should come before five.

24
00:01:29,860 --> 00:01:33,630
So, again, no swapping, so two and five.

25
00:01:34,150 --> 00:01:36,880
So this is my new ADI.

26
00:01:40,990 --> 00:01:41,860
So for.

27
00:01:43,380 --> 00:01:43,860
Three.

28
00:01:45,760 --> 00:01:46,270
When?

29
00:01:47,870 --> 00:01:48,230
To.

30
00:01:49,330 --> 00:01:56,470
And five, so this is my new area now, I will do the same look, compare for entry.

31
00:01:58,080 --> 00:02:02,850
Today should come before 4:00, so step three and four.

32
00:02:03,600 --> 00:02:04,410
Now compare.

33
00:02:05,500 --> 00:02:14,130
One should come before four, so one and four now compared four and two to should come before four,

34
00:02:14,740 --> 00:02:17,980
so swept through two and four.

35
00:02:18,790 --> 00:02:21,580
Now compare four and five.

36
00:02:21,610 --> 00:02:23,800
So four should come before five do nothing.

37
00:02:24,680 --> 00:02:26,720
OK, so do nothing.

38
00:02:26,790 --> 00:02:27,070
OK.

39
00:02:28,240 --> 00:02:29,530
Now, our new is.

40
00:02:31,070 --> 00:02:32,540
So when you raise.

41
00:02:42,070 --> 00:02:42,550
Three.

42
00:02:43,640 --> 00:02:44,180
When?

43
00:02:45,250 --> 00:02:47,350
Two for.

44
00:02:48,370 --> 00:02:49,090
And five.

45
00:02:50,630 --> 00:02:51,980
OK, so compar.

46
00:02:53,370 --> 00:02:56,010
One should come before three, so swapper.

47
00:02:57,850 --> 00:02:58,660
Now compare.

48
00:02:59,900 --> 00:03:02,360
Those should come before 3:00, so Swapper.

49
00:03:04,450 --> 00:03:05,290
Now compare.

50
00:03:06,250 --> 00:03:07,150
So this is correct.

51
00:03:07,200 --> 00:03:13,920
OK, three should appear before four, so do nothing now compare four shall come before five.

52
00:03:14,650 --> 00:03:15,520
So do nothing.

53
00:03:16,840 --> 00:03:18,400
Now, our final array's.

54
00:03:20,090 --> 00:03:22,700
So this is our new Eddie.

55
00:03:26,600 --> 00:03:27,080
One.

56
00:03:28,090 --> 00:03:29,860
Two, three.

57
00:03:30,900 --> 00:03:33,240
Four and five.

58
00:03:34,700 --> 00:03:37,130
So this is auditoria, and this is my final answer.

59
00:03:38,150 --> 00:03:41,270
So what if you will follow the same approach, SVREP?

60
00:03:42,820 --> 00:03:47,860
So they compare, compare what will happen, they are a degradation, do nothing.

61
00:03:49,190 --> 00:03:56,440
Compare, they are the correct position, do nothing, compare, do nothing, compare, do nothing.

62
00:03:56,930 --> 00:03:58,590
So this is my ordinary.

63
00:03:59,420 --> 00:04:06,730
So my question to you is, how many times do we have to show how many times we have to do all this?

64
00:04:07,490 --> 00:04:10,600
So in this case, I was having five elements.

65
00:04:11,420 --> 00:04:15,330
So if I am having five elements, how many times I have did so?

66
00:04:15,380 --> 00:04:16,010
First time.

67
00:04:16,430 --> 00:04:17,269
Second time.

68
00:04:20,970 --> 00:04:26,490
And third time, so I did three times, so after doing three times, I got my answer.

69
00:04:27,070 --> 00:04:34,500
OK, so if the number of elements was five after doing three times, I got my final answer.

70
00:04:36,150 --> 00:04:36,570
Now.

71
00:04:38,860 --> 00:04:41,170
Now, let us consider the worst case.

72
00:04:42,180 --> 00:04:48,690
So what will happen in the worst case, so what will happen in the worst case, my area will be reversed,

73
00:04:48,690 --> 00:04:55,400
sorted, so reverse order means my area will be sorted in reverse order.

74
00:04:55,410 --> 00:05:02,210
So for three, two and one, so my atoms sorted in reverse order.

75
00:05:02,370 --> 00:05:04,140
So this will be the worst case.

76
00:05:04,170 --> 00:05:06,570
OK, so this is worst case.

77
00:05:07,750 --> 00:05:14,260
Now ahead, we will try to understand that for any limits, how many times we have to do something so

78
00:05:14,260 --> 00:05:23,680
compare and step three and four compare and strap so to full compare.

79
00:05:23,680 --> 00:05:29,920
And so when and for the first time, for the first time, I knew it is.

80
00:05:32,580 --> 00:05:34,500
Three to.

81
00:05:35,610 --> 00:05:49,910
When and so this is my new editor, come back and sweep, compare and sweep, come back and do nothing.

82
00:05:50,430 --> 00:05:51,330
So second time.

83
00:05:53,120 --> 00:05:54,290
Now adays.

84
00:05:55,800 --> 00:05:56,280
So.

85
00:05:58,120 --> 00:05:59,590
My ETA is to.

86
00:06:00,690 --> 00:06:03,270
Then one, then three.

87
00:06:04,280 --> 00:06:05,180
And then for.

88
00:06:07,260 --> 00:06:16,050
So compare and swap, so when we come here to come here, come here, do nothing, compare, do nothing.

89
00:06:16,470 --> 00:06:17,280
So third time.

90
00:06:17,820 --> 00:06:19,170
So after doing three times.

91
00:06:22,430 --> 00:06:29,640
So after doing three times, I got my final answer, my record sorted, one, two, three and four.

92
00:06:30,380 --> 00:06:32,530
OK, so my add is sorted.

93
00:06:33,080 --> 00:06:35,450
So this was the worst case.

94
00:06:36,290 --> 00:06:43,340
And I have to do three times the number of elements are four, so I have to do three times.

95
00:06:45,410 --> 00:06:52,010
OK, so this wrapping things I have to do three times so we can also say like this that.

96
00:06:55,050 --> 00:06:56,490
For sorting in numbers.

97
00:06:58,020 --> 00:07:06,840
For sorting in numbers, what to do is short and minus one numbers short and minus one numbers, you

98
00:07:06,840 --> 00:07:11,640
want to sort end numbers, I'm saying you habibti sort and minus one numbers.

99
00:07:11,970 --> 00:07:14,100
So if and minus the numbers are sorted.

100
00:07:14,130 --> 00:07:21,090
That means if they are at their calculation, then the last number will also be at its current position.

101
00:07:21,120 --> 00:07:26,640
OK, so that is the reason for any calls for I have to do the stabbing two times.

102
00:07:27,250 --> 00:07:27,580
Why?

103
00:07:27,840 --> 00:07:29,730
Because for sorting in numbers.

104
00:07:29,730 --> 00:07:36,330
If we start and minus one numbers then the last number will automatically get it correct position.

105
00:07:39,010 --> 00:07:40,240
So it is very simple.

106
00:07:41,020 --> 00:07:45,940
First of all, how many times do we have to do this wrapping things and minus one times so count to

107
00:07:45,940 --> 00:07:50,150
close one count less than what it was two and minus one times.

108
00:07:50,170 --> 00:07:53,570
We have to do this Sappington and the count plus plus.

109
00:07:54,950 --> 00:07:58,390
OK, now I will start from zero.

110
00:07:58,480 --> 00:07:59,760
I have to start from zero.

111
00:07:59,770 --> 00:08:01,270
The zapping you can see here.

112
00:08:03,130 --> 00:08:06,760
The thing was that starting from zero, and this is and minus one.

113
00:08:08,080 --> 00:08:14,590
OK, so the will start from so this is G and this will be the final value of G.

114
00:08:16,090 --> 00:08:22,930
So Jay will go from this to this David Hotel and minister to minus two, because I'm comparing Jay and

115
00:08:22,930 --> 00:08:31,030
Jay plus one, if you will take Jay here, then Jay plus one will become and and if you will.

116
00:08:31,030 --> 00:08:31,420
Right.

117
00:08:31,420 --> 00:08:35,400
LFN, that will give you segmentation fault.

118
00:08:38,640 --> 00:08:48,330
So they will start from zero, G will go to second last position and C++, so what I was doing if.

119
00:08:49,940 --> 00:08:59,930
If Jay is greater than F.J. plus one I am comparing to our descent values, then what I will do, I

120
00:08:59,930 --> 00:09:00,470
will slap.

121
00:09:01,880 --> 00:09:04,520
Slap, A.J., and the object lesson.

122
00:09:07,600 --> 00:09:09,130
So this is all that we have to do.

123
00:09:09,850 --> 00:09:10,240
OK?

124
00:09:11,400 --> 00:09:12,790
So Vion minus two.

125
00:09:13,260 --> 00:09:19,200
So if the value of Jay and minus two and minus two, so this value will become and minus one.

126
00:09:19,410 --> 00:09:19,860
Correct.

127
00:09:20,250 --> 00:09:22,740
Now put Jaquiss and minus one.

128
00:09:23,580 --> 00:09:28,110
So if you put Ajin minus one this value will become and because.

129
00:09:28,110 --> 00:09:28,950
And minus one.

130
00:09:29,460 --> 00:09:30,000
Plus one.

131
00:09:30,000 --> 00:09:33,660
So this value will become and and you are doing aof and.

132
00:09:35,740 --> 00:09:36,680
Segmentation fault.

133
00:09:36,700 --> 00:09:39,790
So that is the reason I will go to hell and Minnesota.

134
00:09:41,960 --> 00:09:42,400
OK.

135
00:09:44,290 --> 00:09:45,710
So this is all that we have to do.

136
00:09:46,150 --> 00:09:46,750
So if.

137
00:09:47,770 --> 00:09:50,800
So this is my job and this is Jay plus one.

138
00:09:51,280 --> 00:09:52,540
So I believe it should happen.

139
00:09:52,540 --> 00:09:59,120
The value at the J should be less than value plus one to get element sorted in ascending order.

140
00:09:59,500 --> 00:10:06,670
So if Jay is bigger, if it's bigger than swamp, then we have to swap.

141
00:10:08,100 --> 00:10:09,960
OK, so let us write the code.

142
00:10:11,280 --> 00:10:14,910
So one more thing before writing, or have you noticed one thing here?

143
00:10:16,640 --> 00:10:23,750
So if you look carefully, the biggest value in forced arbitration reaches its correct position, so

144
00:10:23,750 --> 00:10:31,520
five is the biggest value in the area and then one five reach its correct position in second iteration,

145
00:10:31,550 --> 00:10:35,720
the second largest value reached its correct position.

146
00:10:36,410 --> 00:10:42,320
Similarly, in the third iteration, the third largest value got its correct position.

147
00:10:42,620 --> 00:10:44,140
And similarly, there are two.

148
00:10:44,150 --> 00:10:47,180
And then when you can see here also.

149
00:10:48,640 --> 00:10:56,170
So in the first iteration, the largest value got its correct position in the second iteration, the

150
00:10:56,170 --> 00:11:02,740
second largest value got the second largest value, got its correct position in the third iteration,

151
00:11:03,040 --> 00:11:05,650
the third largest value got its correct position.

152
00:11:05,770 --> 00:11:07,360
OK, so you can see.

153
00:11:09,310 --> 00:11:15,490
In the first iteration, so first iteration, largest value will come, largest value will reach, and

154
00:11:16,420 --> 00:11:21,880
in the second attrition, the second largest value will reach at its correct position.

155
00:11:22,870 --> 00:11:27,580
Third iteration, the third largest value will reach at its highest position.

156
00:11:27,910 --> 00:11:31,360
OK, so my error is getting started in this way.

157
00:11:33,780 --> 00:11:35,670
So this is my unsorted.

158
00:11:37,760 --> 00:11:45,120
And this part is sorted, so the sorted is in this way in case of selection's.

159
00:11:46,490 --> 00:11:47,510
So if you remember.

160
00:11:48,870 --> 00:11:57,030
And selection sort, what we did was, if you are standing here, find the smallest value in the right

161
00:11:57,030 --> 00:11:59,280
hand side and put that value here.

162
00:11:59,730 --> 00:12:07,200
So in first iteration, the smallest value will reach added position in the second iteration, the second

163
00:12:07,200 --> 00:12:11,820
the smallest value will reach at its correct position in attrition.

164
00:12:12,060 --> 00:12:16,050
The third smallest value will reach at its correct position.

165
00:12:16,560 --> 00:12:22,340
So any selection, sort of what is happening might add is getting sorted in this way.

166
00:12:23,100 --> 00:12:27,420
So it is getting started in this way and this part is unsorted.

167
00:12:29,160 --> 00:12:34,920
And in case of bubble my is getting sorted in this way and this part is unsorted.

168
00:12:37,660 --> 00:12:46,280
So this is sort of my area is my area is getting sorted in this way, first and largest value, the

169
00:12:46,340 --> 00:12:52,060
second largest, then third largest and her first port smallest value, then the second smallest value,

170
00:12:52,060 --> 00:12:54,910
then third smallest value, then for smallest value and so on.

171
00:12:57,290 --> 00:13:00,910
I guess that's why the call for Assad to the court is very simple.

172
00:13:02,140 --> 00:13:07,320
How many times do we have to perform this webbing and minus one times, OK?

173
00:13:07,350 --> 00:13:07,560
Why?

174
00:13:07,710 --> 00:13:09,910
Because we have already seen the worst case.

175
00:13:10,420 --> 00:13:14,080
In worst case, if the value of friend goes forward with three times.

176
00:13:14,440 --> 00:13:16,240
So we have to do and minus one times.

177
00:13:17,360 --> 00:13:23,810
And they will start from zero, I will start campaigning from zero, I will come back and plus one since

178
00:13:23,810 --> 00:13:27,520
I am using their platform, so the maximum they will be on minister.

179
00:13:27,860 --> 00:13:33,330
OK, that maximum level, they will be in minus two because I am comparing David J plus one.

180
00:13:35,180 --> 00:13:36,460
OK, so for J.

181
00:13:36,500 --> 00:13:37,650
Question minus two.

182
00:13:37,700 --> 00:13:38,060
This way.

183
00:13:38,060 --> 00:13:39,050
Lewis and minus one.

184
00:13:40,080 --> 00:13:43,590
So if it's good, then lesson, then I will do something.

185
00:13:45,160 --> 00:13:46,240
So right outside the cold.

186
00:13:47,680 --> 00:13:50,020
So let us nameless, faceless babble sort.

187
00:13:55,240 --> 00:13:56,980
So there was Art and Art CBB.

188
00:14:11,730 --> 00:14:13,560
So let us take input from the user.

189
00:14:17,140 --> 00:14:29,040
So far, and I equals zero, I lost and I plus plus seven if I let us make an error.

190
00:14:30,220 --> 00:14:32,440
So the size of the arrays and.

191
00:14:35,030 --> 00:14:43,330
Now I will write a function, bubbles or so bubble, what bubbles heart will take as input, so bubbles,

192
00:14:43,460 --> 00:14:49,570
it will take two things it and the size of the eddy and it will start my eddy.

193
00:14:49,880 --> 00:14:51,050
So my heart is ordered.

194
00:14:51,090 --> 00:14:56,210
Now let us print this after Eddy far and die equals zero.

195
00:14:56,210 --> 00:14:59,440
I less than in a plus place.

196
00:15:01,280 --> 00:15:03,080
See I would if I.

197
00:15:05,340 --> 00:15:12,990
OK, so the Court of Appeals thought so this function will return void, OK, because I'm just sorting

198
00:15:12,990 --> 00:15:17,850
that I'm not returning any value to mean so bubble.

199
00:15:19,080 --> 00:15:27,480
So it is taking to things as input first lady and second, the size of the Harry.

200
00:15:31,990 --> 00:15:43,090
So for how many times and minus one times count equals one count less than an hour equals and minus

201
00:15:43,090 --> 00:15:46,480
one count plus plus.

202
00:15:50,160 --> 00:15:59,040
Now, what we have to do, we have to just compare and numbers, so I'm starting from zero G is less

203
00:15:59,040 --> 00:16:01,750
than articles two and minus two.

204
00:16:01,770 --> 00:16:02,910
So this is important.

205
00:16:02,910 --> 00:16:05,080
And minus two J.

206
00:16:05,340 --> 00:16:06,000
Plus plus.

207
00:16:08,940 --> 00:16:11,980
Now, what he will do, he will compare their DNA to numbers.

208
00:16:12,450 --> 00:16:20,880
So if F.J. is greater than of J plus one, then you have to swab.

209
00:16:21,840 --> 00:16:22,740
So swab.

210
00:16:24,700 --> 00:16:29,780
F, G and F, g plus one.

211
00:16:31,270 --> 00:16:33,100
So this is all that we have to do.

212
00:16:33,650 --> 00:16:38,100
OK, so I told you Ariha Pasta, Bio-Reference.

213
00:16:38,110 --> 00:16:44,110
So if I am changing the values of at O'Haire, this changes will be reflected in function men.

214
00:16:44,690 --> 00:16:51,940
OK, so one more time I told you when you pass ETA to a function, then they are passed by reference.

215
00:16:52,270 --> 00:16:59,410
So if you will do changes in the Eddie, those changes will be reflected in the main function in the

216
00:16:59,490 --> 00:17:00,670
calling function.

217
00:17:04,000 --> 00:17:12,520
Certain number of elements are faith and the values are, let's say, five, four, three, two and

218
00:17:12,520 --> 00:17:12,770
one.

219
00:17:13,810 --> 00:17:16,869
So this is my output, which is sorted.

220
00:17:20,400 --> 00:17:27,910
Let's say MPs are five and the elements are five, four, three, one and two.

221
00:17:29,190 --> 00:17:31,500
So again, this is producing the correct output.

222
00:17:33,390 --> 00:17:45,240
So let's say the number of elements are four and the elements are 30, 20, 10 and 50, so elements

223
00:17:45,240 --> 00:17:46,330
are getting started.

224
00:17:47,160 --> 00:17:49,770
So this is how it works.

225
00:17:51,720 --> 00:17:54,660
OK, so now let's discuss one last thing.

226
00:17:57,470 --> 00:18:01,430
So how many steps it takes to start?

227
00:18:02,600 --> 00:18:11,360
So this outer function is running approximately and minus one times, so outer loop is running and minus

228
00:18:11,360 --> 00:18:15,500
one times and inner loop is also running and minus two times.

229
00:18:16,460 --> 00:18:24,260
So a number of steps, a number of steps equals and minus one and two and minus two.

230
00:18:24,860 --> 00:18:26,570
OK, so these are the number of steps.

231
00:18:27,260 --> 00:18:34,440
So if you will multiply them, we will get and squared them, then income and then some constant.

232
00:18:34,850 --> 00:18:38,390
OK, so let's put an inquest into the power six.

233
00:18:38,960 --> 00:18:43,650
So this value will be 10 to the power to this value will return to the power of six.

234
00:18:43,670 --> 00:18:45,200
And this is something constant.

235
00:18:46,040 --> 00:18:51,870
Now tell me in front of this, does it have any significance?

236
00:18:52,430 --> 00:18:52,880
No.

237
00:18:53,650 --> 00:18:58,710
In front of to the power, to oil and to the power six is nothing.

238
00:18:59,100 --> 00:19:04,460
OK, so I can say the number of steps is a close to and square.

239
00:19:05,900 --> 00:19:10,790
OK, so the number of steps is actually called time complexity.

240
00:19:13,210 --> 00:19:19,840
Time, complexity and complexity means how many number of steps your program took to execute.

241
00:19:21,010 --> 00:19:29,690
OK, so this thing is clear, so how we report and complexity, we will write big or record and square.

242
00:19:30,250 --> 00:19:32,950
So this is called time, complexity of bubbles.

243
00:19:33,670 --> 00:19:35,920
So this is the time, complexity of bubbles.

244
00:19:36,940 --> 00:19:39,750
So what was the time complexity of selection start?

245
00:19:40,120 --> 00:19:43,160
So time, complexity of selection, so was also in the square.

246
00:19:44,320 --> 00:19:46,330
OK, so selection's our time.

247
00:19:46,330 --> 00:19:52,210
Complexity was also in the square and the time complexity of bubbles is also and square.

248
00:19:53,930 --> 00:19:56,990
Now, any idea why we calculate time, complexity?

249
00:19:58,320 --> 00:19:58,800
So.

250
00:20:01,630 --> 00:20:03,300
Suppose you want to buy a car.

251
00:20:04,540 --> 00:20:09,430
So what we will check it will check what is the mileage, what is the cost?

252
00:20:11,040 --> 00:20:12,480
How many number of seats?

253
00:20:14,400 --> 00:20:18,090
What is average speed and there are many factors.

254
00:20:18,480 --> 00:20:22,710
OK, so for deciding which car to buy, you will see many factors.

255
00:20:23,500 --> 00:20:26,640
OK, so there are many sorting algorithms.

256
00:20:26,820 --> 00:20:29,340
There are many sorting algorithms.

257
00:20:30,210 --> 00:20:33,720
How we will decide which sorting algorithm is best.

258
00:20:35,100 --> 00:20:42,330
So what we will do, we will find how much time is my program taking to execute the algorithm, which

259
00:20:42,330 --> 00:20:49,300
take the least amount of time, the algorithm which takes the least amount of time, is the best algorithm.

260
00:20:50,190 --> 00:20:57,030
OK, so that is the reason we calculate the complexity of the program to compare to algorithms or to

261
00:20:57,030 --> 00:20:58,360
compare two programs.

262
00:20:59,010 --> 00:21:07,860
So both bubble sort and solutions are both complexity is and where they both take an equal number of

263
00:21:07,860 --> 00:21:09,060
steps to execute.

264
00:21:10,820 --> 00:21:18,430
OK, so actually, time complexity is a very big topic, I have just given you an introduction to time

265
00:21:18,450 --> 00:21:19,070
complexity.

266
00:21:19,430 --> 00:21:21,620
That is why we calculate time complexity.

267
00:21:21,650 --> 00:21:23,990
OK, so this was just an introduction to time.

268
00:21:23,990 --> 00:21:26,600
Complexity and complexity is a big topic.

269
00:21:28,070 --> 00:21:32,770
OK, so this is it for this video, if you have any doubt in the heart, you can ask me.

270
00:21:33,230 --> 00:21:33,800
Thank you.

