1
00:00:00,830 --> 00:00:01,330
OK.

2
00:00:01,730 --> 00:00:07,700
So welcome back, everybody in this lecture, we're actually not going to introduce a new sort quite

3
00:00:07,700 --> 00:00:13,630
yet and the subsequent lectures, we will talk about some new and better sorts.

4
00:00:13,670 --> 00:00:15,110
Maybe just one, actually.

5
00:00:15,530 --> 00:00:19,490
But in this lecture, we're going to focus on revising our bubble sort.

6
00:00:19,490 --> 00:00:24,080
If you remember in the last lecture, we kind of talked about how the algorithm that we came up with

7
00:00:24,080 --> 00:00:26,110
was, like extremely rudimentary.

8
00:00:26,120 --> 00:00:34,160
It just had like a double, you know, a nested for loop where it tried to just do a full path of swapping

9
00:00:34,160 --> 00:00:37,610
for as many elements as there were in the array.

10
00:00:38,210 --> 00:00:39,860
And you know, that was all it.

11
00:00:39,860 --> 00:00:44,440
Did it just check to see if something was bigger and it just kept swapping it and it just kept swapping.

12
00:00:44,450 --> 00:00:51,710
And you know, eventually the whole array is going to be sorted because it does as many swaps as there

13
00:00:51,710 --> 00:00:54,130
are items in the array.

14
00:00:54,140 --> 00:01:00,620
It does as many full pass throughs of swaps as there are items, so as many pass through.

15
00:01:00,650 --> 00:01:04,250
So that's the way that nested loop was pretty inefficient.

16
00:01:05,180 --> 00:01:08,630
So we're doing a lot of redundant kind of pointless calculations in this.

17
00:01:08,630 --> 00:01:11,120
So we're going to go through and kind of revise it a little bit.

18
00:01:11,660 --> 00:01:15,900
So currently, this bubble sort of algorithm does a lot of these pointless calculations.

19
00:01:15,940 --> 00:01:19,370
We're going to go ahead and step through and kind of see why and what's happening.

20
00:01:20,300 --> 00:01:24,080
So let's go ahead and just walk through right off the bat.

21
00:01:24,200 --> 00:01:28,340
We're going to start off on the left here and we know that we need to swap one in for it.

22
00:01:29,420 --> 00:01:32,300
So we're going to swap one in for this is our first pass through.

23
00:01:32,810 --> 00:01:38,120
We go over here, we don't need to swap four and seven because those are already in short order.

24
00:01:38,900 --> 00:01:42,170
Then we go over to we're going to move over to the seven and three.

25
00:01:43,250 --> 00:01:45,620
And those two are going to swap.

26
00:01:46,190 --> 00:01:53,870
And so something important to think about is that on each pass through, essentially, we're going to

27
00:01:53,870 --> 00:02:00,530
run into the largest value at some point inside of this array or vector.

28
00:02:01,010 --> 00:02:07,130
And what we're going to do is we're going to bubble that largest value all the way to the end.

29
00:02:08,400 --> 00:02:13,770
So even though we started with four right, we bubbled up before, but it couldn't really bubble up

30
00:02:13,770 --> 00:02:15,480
past this point right here.

31
00:02:16,110 --> 00:02:22,260
Seven is the largest thing, so we swapped it to here, even if there really had more like values in

32
00:02:22,260 --> 00:02:29,070
it that were less than seven, like, I guess that would only be like two and five and six.

33
00:02:30,110 --> 00:02:37,130
Then seven would continue bubbling up until it was at the end, so you can take that information and

34
00:02:37,130 --> 00:02:42,140
make the assumption that on each full pass through of swapping.

35
00:02:43,230 --> 00:02:48,090
We are going to take the biggest item and bubble it all the way to the end.

36
00:02:48,180 --> 00:02:54,360
So the second pass through it will basically find the next biggest item.

37
00:02:54,540 --> 00:02:59,820
So like the second biggest item and it's going to bubble of that all the way to the end and it's going

38
00:02:59,820 --> 00:03:02,370
to stack up right against seven.

39
00:03:05,300 --> 00:03:10,250
So that's like what's going to happen on the next pass through and then and we can see that.

40
00:03:10,370 --> 00:03:16,490
So if we go here, we're going to not change one in four, but we are going to change four in three.

41
00:03:17,400 --> 00:03:22,680
And so now we noticed that four stacks up against seven.

42
00:03:25,350 --> 00:03:32,700
So the interesting thing is that when we continue doing this, you know, now we notice our whole array

43
00:03:32,700 --> 00:03:33,840
happens to be sorted.

44
00:03:34,920 --> 00:03:41,550
But we have this w we go and we check this again and then we're even checking this.

45
00:03:41,550 --> 00:03:43,650
We're doing that third pass through now.

46
00:03:43,830 --> 00:03:50,040
And on the third pass through, we are even checking these last two elements that we should know are

47
00:03:50,040 --> 00:03:58,050
like totally going to be sorted because we've already done the first pass, which put the biggest element

48
00:03:58,050 --> 00:03:59,800
on the end, bubbled it to the end.

49
00:03:59,820 --> 00:04:06,150
We did a second pass, which puts the second biggest element, bubbled up and smashed up against the

50
00:04:06,150 --> 00:04:07,780
seven now, which is the fourth.

51
00:04:07,800 --> 00:04:09,000
So it's like piling up.

52
00:04:09,450 --> 00:04:15,450
We do a third pass and even though we should know that we've already done two passes.

53
00:04:17,080 --> 00:04:23,800
And that that means that the last two elements, the right most elements in the array of Vector should

54
00:04:23,800 --> 00:04:25,480
be already handled and sorted.

55
00:04:25,750 --> 00:04:33,250
We still venture over into this zone and we're redundant when comparing four and seven when we don't

56
00:04:33,250 --> 00:04:33,940
need to.

57
00:04:35,550 --> 00:04:37,560
So that is one problem.

58
00:04:39,160 --> 00:04:41,430
Is that we don't need to be comparing this yet?

59
00:04:41,440 --> 00:04:44,020
We are we're just looping all the way to the end.

60
00:04:44,050 --> 00:04:45,680
This is the swapping the loop.

61
00:04:45,700 --> 00:04:47,110
This is the inner loop, right?

62
00:04:47,110 --> 00:04:48,430
Because we have our swap right here.

63
00:04:49,330 --> 00:04:53,380
So this inner loop is considered that whole pass through each time.

64
00:04:53,380 --> 00:04:57,490
Like, you know, I, we we do this many pass throughs.

65
00:04:58,860 --> 00:05:03,600
And then this represents each pass through, so we did one pass through the seven, got to the end,

66
00:05:03,600 --> 00:05:08,040
we did another pass through, the four got smashed up against the seven and we do another pass through

67
00:05:08,040 --> 00:05:08,490
now.

68
00:05:08,790 --> 00:05:12,420
And that's what we're currently on and there happens to be sorted.

69
00:05:14,670 --> 00:05:20,520
So we know that we can potentially eliminate this redundant calculation when we're looking at stuff

70
00:05:20,520 --> 00:05:23,340
that's already been sorted at the end.

71
00:05:24,090 --> 00:05:28,830
But another thing that we can do is, I mean, look at this, the array is already sorted.

72
00:05:29,460 --> 00:05:34,860
We should not have to look for a fourth time, right?

73
00:05:35,580 --> 00:05:41,170
There's going to be there's four elements in here and this is and I go zero, I less than my size.

74
00:05:41,670 --> 00:05:45,930
So that's going to be the zero one to three, which is four times.

75
00:05:46,410 --> 00:05:51,720
We don't need to go through yet another time when this thing is already sorted.

76
00:05:52,920 --> 00:05:59,540
So how could we handle fixing that kind of pointless calculation as well?

77
00:06:00,590 --> 00:06:05,510
So we don't want to have to go through and do all the swaps again because they're pointless.

78
00:06:06,050 --> 00:06:08,860
We could add a Boolean to do that.

79
00:06:08,870 --> 00:06:13,070
We should check to see whether any swaps happen at all.

80
00:06:13,100 --> 00:06:15,680
So think about this pass right here.

81
00:06:15,830 --> 00:06:17,570
We're on the third pass through, right?

82
00:06:18,230 --> 00:06:21,710
So if we go through and we didn't, we didn't swap it.

83
00:06:21,710 --> 00:06:22,250
All right.

84
00:06:22,250 --> 00:06:29,680
So here's the start of the third pass to one in three no swap three and four and no swap four and seven.

85
00:06:29,690 --> 00:06:31,940
I mean, we shouldn't even be comparing four and seven.

86
00:06:32,090 --> 00:06:35,990
That was another fix we just talked about, but four and seven, no swap.

87
00:06:36,230 --> 00:06:38,660
There's no swaps at all if there's no swaps.

88
00:06:39,530 --> 00:06:45,590
That means that nothing was out of order and therefore everything is in order.

89
00:06:45,830 --> 00:06:50,090
So therefore no ray is sorted.

90
00:06:50,090 --> 00:06:51,410
The victor is sorted.

91
00:06:52,220 --> 00:06:57,920
So if the vector is sorted and we had no swaps, we should just stop the loop.

92
00:06:58,800 --> 00:06:59,970
But how do we do that?

93
00:07:01,380 --> 00:07:07,470
So let's go ahead to the code and try and fix it up, and let's go over how we could stop doing the

94
00:07:07,470 --> 00:07:11,880
loop if we noticed that we did know swaps on one of the pass throughs.

95
00:07:11,880 --> 00:07:16,770
So once the array is sorted, we should not continue trying to sort it.

96
00:07:18,900 --> 00:07:23,040
So I'm going to go over here into them, and we're going to make some changes.

97
00:07:23,820 --> 00:07:27,300
First off, let's change the first thing we talked about.

98
00:07:27,540 --> 00:07:36,420
Why are we going all the way into this last two elements to look at them to swap every single time like

99
00:07:36,420 --> 00:07:38,340
we should not be going up to that point?

100
00:07:39,030 --> 00:07:45,050
We should only be going up to the point in which there are no sorted elements, right?

101
00:07:45,060 --> 00:07:46,530
And think about it.

102
00:07:47,280 --> 00:07:50,580
Stuff is getting piled up at the end here.

103
00:07:50,610 --> 00:07:50,970
Right?

104
00:07:51,300 --> 00:07:51,840
So.

105
00:07:52,920 --> 00:07:56,970
Here we have four and seven each passed through.

106
00:07:57,000 --> 00:08:02,700
We have one element that gets smashed up on the end, so first pass through seven, second pass through

107
00:08:02,700 --> 00:08:03,180
four.

108
00:08:03,570 --> 00:08:06,050
Now we don't need to look at this zone anymore.

109
00:08:07,220 --> 00:08:10,070
We should look only up to here, right?

110
00:08:11,950 --> 00:08:13,810
So how do we do that?

111
00:08:13,840 --> 00:08:15,800
What is that, what is that position?

112
00:08:15,820 --> 00:08:21,220
Well, the outer loop represents each pass through, right?

113
00:08:21,220 --> 00:08:27,460
In the fact that we've done two pass throughs means that there are two things all the way to the right.

114
00:08:27,970 --> 00:08:30,460
They have piled up that we do not need to look at.

115
00:08:30,460 --> 00:08:33,760
So therefore our inner loop should stop.

116
00:08:36,540 --> 00:08:44,100
Whatever point, you know, is less than how many items we have piled up at the end, so what does that

117
00:08:44,100 --> 00:08:44,370
mean?

118
00:08:44,400 --> 00:08:47,610
So whatever point, that's less than how many items we piled up at the end?

119
00:08:48,210 --> 00:08:54,540
Well, we noticed that this loop has iterated twice for two pass throughs and we notice we have two

120
00:08:54,540 --> 00:08:55,560
things at the end.

121
00:08:56,560 --> 00:08:58,930
We know that this is the end of the array.

122
00:08:59,260 --> 00:09:00,490
The size right.

123
00:09:01,580 --> 00:09:05,900
This array is one, two, three, four or Vector, whatever you want to consider, this vector is one

124
00:09:05,900 --> 00:09:12,140
two three four positions zero one two three position four would be out here.

125
00:09:12,590 --> 00:09:15,980
We noticed that the size of the vector is four.

126
00:09:17,060 --> 00:09:18,920
So if we do for.

127
00:09:20,520 --> 00:09:21,510
Minus.

128
00:09:22,820 --> 00:09:28,640
The amount of iterations that we've done, so let's say I is on.

129
00:09:30,410 --> 00:09:34,370
So we've done it two times will be zero and one.

130
00:09:36,140 --> 00:09:41,750
And then now we're on to right, because when the third passed through, so I will be two, so if we

131
00:09:41,750 --> 00:09:46,880
are going to do four, minus two is two.

132
00:09:47,120 --> 00:09:50,420
So we have a zero one two that puts us right here.

133
00:09:51,460 --> 00:09:56,370
But we don't want to really be right here and look at the swap, we want to be one before that, right,

134
00:09:56,380 --> 00:09:59,620
so that would be the size of the vector.

135
00:10:01,120 --> 00:10:07,390
Minus two, minus one more in two, was I right?

136
00:10:07,400 --> 00:10:11,500
So we want the size of the vector minus I whatever I wear on.

137
00:10:12,530 --> 00:10:17,780
Minus one more, so that will put us in front of all the stuff that's piled up at the end.

138
00:10:18,950 --> 00:10:21,020
So let's go ahead and put that into code.

139
00:10:22,700 --> 00:10:31,430
So what we are going to do is say that Jay is not less than my exercise, but it's less than I'm going

140
00:10:31,430 --> 00:10:32,720
to put this in parentheses.

141
00:10:33,440 --> 00:10:46,130
My vector size minus I minus one because we want to go up to the point that stops before we enter that

142
00:10:46,130 --> 00:10:49,220
piled up sordid portion on the right side.

143
00:10:50,030 --> 00:10:53,200
So if this is a little confusing, just take a moment to kind of break it down.

144
00:10:53,210 --> 00:10:55,310
Think of like, well, what is the size of the vector?

145
00:10:55,760 --> 00:11:02,070
How many iterations of the outer loop have we gone through and what does that mean?

146
00:11:02,090 --> 00:11:07,460
How does that relate to how many items have successfully been bubbled up to the end?

147
00:11:08,300 --> 00:11:09,770
The big it's got bubbled up.

148
00:11:09,980 --> 00:11:15,410
The second biggest got bubbled up, the third biggest got bubbled up and so on and so forth.

149
00:11:16,370 --> 00:11:20,870
Each one of those first, second and third is representative of this outer loop.

150
00:11:20,900 --> 00:11:24,680
This inner loop is just simply all of the swaps on each pass through.

151
00:11:25,520 --> 00:11:33,380
So we want to stop trying to swap at the point in which we realize that we're about to enter that piled

152
00:11:33,380 --> 00:11:39,470
up bubbled up portion that's already been sorted at the end of the era.

153
00:11:40,220 --> 00:11:41,790
And that's where this comes in right here.

154
00:11:41,810 --> 00:11:43,340
So now we have solved that issue.

155
00:11:43,370 --> 00:11:47,480
So let's go ahead and verify that everything works, OK?

156
00:11:47,930 --> 00:11:50,030
So I'm going to go ahead and say this.

157
00:11:51,380 --> 00:11:54,070
Let me make sure I don't have too big of an array.

158
00:11:54,110 --> 00:11:55,130
OK, it's just five.

159
00:11:55,130 --> 00:11:55,760
So that's fine.

160
00:11:56,510 --> 00:12:02,060
So I'm going to do it C++ and you've obviously that should be brought out.

161
00:12:03,980 --> 00:12:14,030
So let's go ahead and run out, and we'll just go ahead and do, let's just say, six.

162
00:12:16,120 --> 00:12:20,920
Four, seven, one three.

163
00:12:22,000 --> 00:12:27,370
All right, so now we notice that this is sorted one three four six seven despite us entering it in

164
00:12:27,370 --> 00:12:29,410
this order six four seven one three.

165
00:12:30,280 --> 00:12:31,330
So that still works.

166
00:12:31,330 --> 00:12:39,740
And even after adding our little small optimization to that, we noticed that everything is still sorting

167
00:12:39,760 --> 00:12:40,510
correctly.

168
00:12:41,410 --> 00:12:42,790
So what was the other thing?

169
00:12:42,820 --> 00:12:47,080
Well, we talked about not having to do anything.

170
00:12:47,080 --> 00:12:50,710
Once we realized that the array is fully sorted, we should stop, right?

171
00:12:50,950 --> 00:12:53,800
We should not do a full other pass through.

172
00:12:54,550 --> 00:13:01,630
We noticed here that everything is sorted and we're on our third pass through, but our loop.

173
00:13:02,580 --> 00:13:05,140
Would go ahead and do another full pass through, right?

174
00:13:05,160 --> 00:13:12,960
Because it's going four times and we've only gone three times, it's going to zero one to three.

175
00:13:13,190 --> 00:13:14,150
You know, I have zero.

176
00:13:14,160 --> 00:13:16,530
I one is two and three, that's four times.

177
00:13:17,220 --> 00:13:18,690
We're only on our third pass through.

178
00:13:18,990 --> 00:13:20,970
Yet the array is totally sorted.

179
00:13:21,750 --> 00:13:24,370
We would have gone through here and been like, This doesn't need to be solved.

180
00:13:24,390 --> 00:13:25,330
This doesn't need to be solved.

181
00:13:25,350 --> 00:13:26,530
This doesn't need to be solved.

182
00:13:26,550 --> 00:13:31,020
In fact, we're not going to do the last one anymore, are we, because we're stopping at the right

183
00:13:31,020 --> 00:13:31,440
time?

184
00:13:32,220 --> 00:13:35,110
So this doesn't need to be swapped and this doesn't need to be swapped?

185
00:13:35,130 --> 00:13:41,040
And by that, I mean, like this and this and we stop here and we notice that, you know what, we didn't

186
00:13:41,040 --> 00:13:41,980
do any swaps.

187
00:13:42,000 --> 00:13:44,550
That means that this array is sorting.

188
00:13:44,550 --> 00:13:45,810
This vector is sorted.

189
00:13:45,840 --> 00:13:48,240
So how do we check that?

190
00:13:48,270 --> 00:13:52,560
How do we check to see if we've done any swaps?

191
00:13:53,370 --> 00:13:55,020
This is where we're doing a swap, right?

192
00:13:56,310 --> 00:13:57,540
In this section right here.

193
00:13:58,810 --> 00:14:04,540
How do we know when to stop the outer loop if we haven't done any swaps?

194
00:14:06,590 --> 00:14:12,230
So what we're going to do is use a Boolean, and this is just the solution I'm going to do, so I'm

195
00:14:12,230 --> 00:14:13,520
going to say Boolean.

196
00:14:16,300 --> 00:14:27,580
I'll just call this swaps, or I could say, had swaps, so I could basically say had swaps equals false.

197
00:14:28,210 --> 00:14:33,310
So I said it's a false in the beginning, assuming that there is no swaps, so we would just assume

198
00:14:33,880 --> 00:14:35,650
that the array is sorted.

199
00:14:36,100 --> 00:14:42,460
But if we do in fact do a swap, it means the array is not sort sorted.

200
00:14:43,240 --> 00:14:48,910
And so if we do a swap, that means we're going to have to enter this if right here, right, because

201
00:14:48,910 --> 00:14:51,310
this is a situation that calls for a swap.

202
00:14:51,310 --> 00:14:53,710
And so we therefore do the swap right here.

203
00:14:53,740 --> 00:14:58,900
Afterwards, I can say, had swaps.

204
00:14:59,020 --> 00:15:00,610
I think that was what it was called.

205
00:15:00,610 --> 00:15:07,540
Had swaps equals true because we did, in fact, do a swap if we made it to this code in the scope of

206
00:15:07,540 --> 00:15:10,090
the if that means we did do a swap.

207
00:15:10,930 --> 00:15:15,700
So I can set had swaps to true, which is kind of like turning it on and off switch, right?

208
00:15:15,700 --> 00:15:16,300
The bullion.

209
00:15:17,050 --> 00:15:22,210
We're going to assume that the array is sorted and this will tell us whether it's sorted or not.

210
00:15:23,690 --> 00:15:24,020
Right.

211
00:15:24,590 --> 00:15:33,050
So each time, though, we're probably going to want to reset this to be false, right?

212
00:15:33,070 --> 00:15:37,790
So each time we go through, we're going to assume that it could be sorted each pass through.

213
00:15:38,040 --> 00:15:41,000
We're going to say, Hey, this might be sorted.

214
00:15:42,750 --> 00:15:50,250
So let's go ahead and do that, we'll say, had swaps equals false each time before we go through,

215
00:15:51,570 --> 00:15:56,220
if we actually need to swap, we know that it's not completely sorted yet.

216
00:15:56,220 --> 00:15:58,800
So it'll say has swaps equals true.

217
00:16:00,270 --> 00:16:03,280
But then let's say that had swapped equals false.

218
00:16:03,990 --> 00:16:07,390
We now go through a full pass through with this inner loop, right?

219
00:16:07,420 --> 00:16:08,880
This will do a full pass through.

220
00:16:09,030 --> 00:16:10,770
And we never do a swap.

221
00:16:11,160 --> 00:16:13,950
Had swaps will remain false.

222
00:16:14,940 --> 00:16:15,360
Right?

223
00:16:16,920 --> 00:16:18,570
And the switch never got flipped.

224
00:16:18,570 --> 00:16:22,770
If we never go in here, that means that we know that the array is sorted.

225
00:16:22,780 --> 00:16:33,270
So at this point, we can put it if and we can say if we had swaps and actually what we want to do is

226
00:16:33,270 --> 00:16:36,390
we could say if had swaps, of course, equals false.

227
00:16:36,750 --> 00:16:37,170
But we can.

228
00:16:37,170 --> 00:16:48,000
Also, just since it's a Boolean, we can just say if not had swaps, if it had no swaps, which means

229
00:16:48,930 --> 00:16:50,490
swaps is false, right?

230
00:16:52,320 --> 00:16:55,320
So if we not a false, it turns true.

231
00:16:55,950 --> 00:17:03,090
This would be the same thing as just saying if had swaps equals equals false, which, you know, we're

232
00:17:03,090 --> 00:17:03,840
sitting here.

233
00:17:03,840 --> 00:17:05,370
So let's say we said it to false.

234
00:17:05,370 --> 00:17:06,210
Here it goes.

235
00:17:06,210 --> 00:17:12,180
In this inner loop, it tries to go a full pass through all the way through all the iterations of J.

236
00:17:12,570 --> 00:17:13,410
Up to here.

237
00:17:14,160 --> 00:17:15,870
And it never enters this.

238
00:17:15,870 --> 00:17:20,490
If because everything is in sorted order, it gets down here.

239
00:17:20,490 --> 00:17:23,640
And we're like, if had swaps, equals equals false.

240
00:17:23,640 --> 00:17:26,970
If it's still is false, we never flipped the switch to true.

241
00:17:27,870 --> 00:17:32,340
That means it's sorted so we can stop the outer loop at this point.

242
00:17:32,760 --> 00:17:37,170
So this outer loop, we don't need to do this outer loop anymore.

243
00:17:38,880 --> 00:17:46,560
So I'm saying, if not had swaps instead of saying if had swaps equals equals false and what are we

244
00:17:46,560 --> 00:17:47,220
going to do?

245
00:17:47,370 --> 00:17:48,000
What do we do?

246
00:17:48,000 --> 00:17:51,510
If that's the case, how do we stop looping?

247
00:17:51,720 --> 00:18:00,990
The only thing that we really know about so far is that the for loop just goes as long as we have set

248
00:18:00,990 --> 00:18:02,340
a condition for it, right?

249
00:18:02,340 --> 00:18:06,450
Like it goes this long as long as I is less than my vector size.

250
00:18:06,450 --> 00:18:08,070
So it's just going to keep going and going.

251
00:18:08,700 --> 00:18:16,020
Luckily, there is a special word we can use to break out of the loops to stop doing the loops and break

252
00:18:16,020 --> 00:18:18,390
out, and it is called break.

253
00:18:20,160 --> 00:18:27,600
So I just put the word break like this, and what that's going to do is it's going to break out of this

254
00:18:27,600 --> 00:18:31,050
outer loop and it's no longer going to do any looping.

255
00:18:32,660 --> 00:18:38,750
So we've finished the inner loop, right, and we come back out to the scope to this level.

256
00:18:39,440 --> 00:18:46,460
So this level right here of the outer loop and then we're saying, OK, the array was sorted, it had

257
00:18:46,460 --> 00:18:50,310
no swaps because this never got actually set to true.

258
00:18:50,330 --> 00:18:52,280
So what we're going to do is break.

259
00:18:52,520 --> 00:18:58,490
And when we see break, we're going to break out of whatever loop we are currently in, right at this

260
00:18:58,490 --> 00:19:00,260
point, right here at this level.

261
00:19:01,220 --> 00:19:02,180
Of brackets.

262
00:19:02,430 --> 00:19:08,600
You know, we're in here, we're in this scope of the outer loop, so we're going to break out of this

263
00:19:08,600 --> 00:19:10,640
loop here and stop.

264
00:19:11,600 --> 00:19:12,560
Which is good, right?

265
00:19:12,570 --> 00:19:16,010
We don't want to have to do another pointless pass through a series sorted.

266
00:19:16,940 --> 00:19:20,390
So let's go ahead and make sure that our code runs with this.

267
00:19:24,320 --> 00:19:26,330
So I'm going to go ahead and compile this.

268
00:19:29,570 --> 00:19:31,100
And let's go ahead and run it.

269
00:19:33,020 --> 00:19:40,490
So let's go ahead and just into something else, I say eight nine one four two.

270
00:19:41,870 --> 00:19:42,380
There we go.

271
00:19:43,310 --> 00:19:49,610
One two four eight nine So it looks like everything is sorted and it's good to go so we can also check.

272
00:19:49,880 --> 00:19:52,310
It's good to check multiple kind of inputs.

273
00:19:53,510 --> 00:19:56,800
Let's go ahead and make a bigger number here.

274
00:19:56,810 --> 00:19:57,800
Let's just say 10.

275
00:19:58,190 --> 00:20:01,940
Save this compiler again and again.

276
00:20:12,200 --> 00:20:13,610
Let's say.

277
00:20:20,330 --> 00:20:25,910
All right, so I repeated some elements, but we have zero one one three four five six seven eight nine.

278
00:20:26,330 --> 00:20:29,240
So looks like this is working on this example as well, too.

279
00:20:30,620 --> 00:20:38,780
So what we essentially did just to kind of recap was to get rid of that like non-essential next pass

280
00:20:38,780 --> 00:20:42,560
through because at this point in time, we were on the third pass through.

281
00:20:44,100 --> 00:20:50,160
So we pretty much went one pass through to pass through three pass through.

282
00:20:50,940 --> 00:20:55,680
And then after this, we would have started back in the beginning for a fourth pass through, even though

283
00:20:55,680 --> 00:20:58,080
one three four seven is already sorted.

284
00:20:58,830 --> 00:21:00,680
So we got rid of that with the bullion.

285
00:21:00,690 --> 00:21:05,250
And the other thing we got rid of is that we shouldn't be checking this with the question mark here,

286
00:21:05,290 --> 00:21:05,550
right?

287
00:21:06,000 --> 00:21:08,340
We should have pretty much stopped here before.

288
00:21:08,340 --> 00:21:11,580
So we are stopping at this point right here.

289
00:21:11,820 --> 00:21:13,680
So we're not doing these extra checks.

290
00:21:13,680 --> 00:21:19,200
And what that will do is even if this was bigger, let's say we had four items piled up at the end.

291
00:21:19,380 --> 00:21:23,730
We would stop before those four items, right, because we changed this.

292
00:21:24,970 --> 00:21:34,780
Over to have this condition right here, so we're going as long as day is less than my vector size minus

293
00:21:34,780 --> 00:21:41,200
I, because we want to kind of go back before all the piled up items and we're doing minus one to be

294
00:21:41,200 --> 00:21:43,030
currently on the one before that, right?

295
00:21:45,430 --> 00:21:51,610
So hopefully that is enough for you to understand how to make some small optimizations to bubble sort

296
00:21:51,610 --> 00:21:55,780
and how to have a slightly more complex sort.

297
00:21:56,050 --> 00:22:01,240
You know, the first thing that we did was like the most rudimentary possible sort you could ever do,

298
00:22:01,240 --> 00:22:02,350
in my opinion, of course.

299
00:22:03,430 --> 00:22:09,040
But now we have kind of just made these small little optimizations that will not necessarily make it

300
00:22:09,370 --> 00:22:13,060
overall a better source compared to other sorts.

301
00:22:13,150 --> 00:22:16,540
But it still makes it a better bubble sort.

302
00:22:17,620 --> 00:22:24,760
All right, we have made our bubble sort of slightly more efficient in terms of certain cases where

303
00:22:24,760 --> 00:22:28,100
it would stop early, you know, when it sees everything sorted.

304
00:22:29,080 --> 00:22:30,610
It wouldn't do another pass through.

305
00:22:32,100 --> 00:22:40,020
OK, so with that, I'm going to end this lecture, and in the next lecture, we will actually start

306
00:22:40,020 --> 00:22:42,090
on another type of sort.