1
00:00:00,960 --> 00:00:08,670
OK, so now it is time for us to start going over some different types of sorting algorithms, and what

2
00:00:08,670 --> 00:00:15,660
I'm going to do is just kind of start out with the most rudimentary basic sorting algorithms and work

3
00:00:15,660 --> 00:00:22,230
our way up in terms of complexity and will not be going over every sorting algorithm because there's

4
00:00:22,230 --> 00:00:24,480
a ton of sorting algorithms.

5
00:00:24,480 --> 00:00:28,200
And I feel like there could be an entire course just on sorting.

6
00:00:28,680 --> 00:00:31,230
But I don't have time for that.

7
00:00:31,230 --> 00:00:37,890
So I'm just going to kind of pick a few basic ones, not go into a ton of detail on the efficiency because

8
00:00:37,890 --> 00:00:39,270
that's going to be close.

9
00:00:39,480 --> 00:00:43,470
That's going to be a big part of the second portion of the course.

10
00:00:43,500 --> 00:00:46,980
So, you know, algorithms and analysis of algorithms.

11
00:00:46,980 --> 00:00:47,280
So.

12
00:00:48,570 --> 00:00:53,010
I'm just going to introduce you to a few thoughts, haven't figured out what other one's going to I'm

13
00:00:53,010 --> 00:00:57,780
going to do, but the first of I want to start off with, which is pretty much considered to be the

14
00:00:57,780 --> 00:01:01,380
most simple type of sort, is bubble sort.

15
00:01:02,520 --> 00:01:04,620
So let's get into it.

16
00:01:04,770 --> 00:01:13,350
We're going to go ahead and solve the problem that I gave you the challenge in the last lecture by using

17
00:01:13,350 --> 00:01:14,020
bubble sort.

18
00:01:14,040 --> 00:01:17,610
But first, I'd like to show you what bubble it is and how it works.

19
00:01:18,990 --> 00:01:23,100
So the idea is that we have some array or vector right?

20
00:01:23,430 --> 00:01:29,370
And all we're going to do for bubble sort is start at the left and go to the right and keep swapping

21
00:01:29,370 --> 00:01:36,510
elements from left to right with the idea of bubbling up the larger values towards the right.

22
00:01:36,520 --> 00:01:41,370
So basically, it's just, you know, five is bigger than this.

23
00:01:41,370 --> 00:01:44,460
So let's swap them in kind of bubble five towards the right.

24
00:01:44,820 --> 00:01:47,910
Five is still greater than this, so we bubble five further.

25
00:01:47,910 --> 00:01:50,040
Five is still better than this, so we bubble five further.

26
00:01:50,040 --> 00:01:51,450
So that's what we're going to be doing.

27
00:01:52,470 --> 00:01:57,330
Keep swapping elements from left to right, over and over and over and tell the array is sorted.

28
00:01:59,390 --> 00:02:02,900
So let's check out the first one is five greater than three.

29
00:02:02,930 --> 00:02:03,770
Yes, it is.

30
00:02:04,190 --> 00:02:06,740
So we're going to swap it, so we swap it.

31
00:02:07,250 --> 00:02:09,710
Next is five greater than one.

32
00:02:10,010 --> 00:02:10,940
Yes, it is.

33
00:02:11,360 --> 00:02:13,120
So we're going to swap it.

34
00:02:13,130 --> 00:02:13,700
Let's swap.

35
00:02:13,700 --> 00:02:16,100
It is five greater than four.

36
00:02:16,130 --> 00:02:16,890
Yes, it is.

37
00:02:16,970 --> 00:02:19,010
So let's go ahead and swap it.

38
00:02:19,430 --> 00:02:20,910
We now reach the end.

39
00:02:20,930 --> 00:02:25,730
So let's go back to the beginning and do it all over again is three great and one.

40
00:02:25,760 --> 00:02:26,480
Yes, it is.

41
00:02:26,690 --> 00:02:27,740
We're going to swap them.

42
00:02:29,000 --> 00:02:30,710
Is three greater than four.

43
00:02:30,740 --> 00:02:31,760
No, it's not.

44
00:02:31,910 --> 00:02:33,300
Is four and five.

45
00:02:33,320 --> 00:02:34,160
No, it's not.

46
00:02:34,520 --> 00:02:36,170
Now we go back to the beginning.

47
00:02:36,890 --> 00:02:37,700
Oh, look.

48
00:02:37,730 --> 00:02:39,560
One three four five.

49
00:02:39,590 --> 00:02:42,170
They're all sorted now, so all numbers are now sorted.

50
00:02:42,680 --> 00:02:44,270
We should be done right.

51
00:02:44,660 --> 00:02:50,100
But what we're going to do is actually make something even more rudimentary.

52
00:02:50,120 --> 00:02:56,480
We're not going to even add some code that makes this slightly more efficient and even knows that it's

53
00:02:56,480 --> 00:02:56,870
done.

54
00:02:57,260 --> 00:03:04,130
We're just going to write code that checks for all possible swaps for all elements in the array vector.

55
00:03:04,130 --> 00:03:11,910
So you know, there's one two three four elements and we're going to try and just go through, you know,

56
00:03:11,930 --> 00:03:14,450
like this, swap this swap in this swap.

57
00:03:14,450 --> 00:03:17,540
So three different potential swaps for those four elements.

58
00:03:17,540 --> 00:03:21,380
So it's not going to be very efficient, but that's what we're going to start out with.

59
00:03:21,390 --> 00:03:25,580
So because we're just trying to make the most basic possible sorting algorithm.

60
00:03:26,720 --> 00:03:29,600
So what I'm going to do is head over here.

61
00:03:30,820 --> 00:03:38,470
I'm actually in the terminal and I'm going to go ahead and make a new file, and I'm going to call this

62
00:03:38,620 --> 00:03:41,100
bubble story CP.

63
00:03:42,280 --> 00:03:45,670
I'm going to include Io stream.

64
00:03:46,630 --> 00:03:49,310
I will also include Vector.

65
00:03:49,330 --> 00:03:55,480
I'm going to go ahead and use this and think you guys should get some practice with vectors, either

66
00:03:55,480 --> 00:03:59,320
they're using their faces to do a main function.

67
00:04:01,480 --> 00:04:03,700
Now put this or zero here.

68
00:04:05,350 --> 00:04:08,560
I'm going to need to make a vector.

69
00:04:08,590 --> 00:04:11,800
I'm going to make a vector integers and I call it my effect.

70
00:04:12,610 --> 00:04:16,700
I'm going to need to make some sort of input variable.

71
00:04:16,720 --> 00:04:22,690
I think I'm just going to call this and my aunt or something like that.

72
00:04:22,700 --> 00:04:24,240
Now I'm going to go ahead and read in.

73
00:04:24,250 --> 00:04:29,000
So I'll actually just say we're going to do five, right?

74
00:04:29,000 --> 00:04:32,380
So I'll say four and I equals zero.

75
00:04:32,410 --> 00:04:40,780
I have less than five have plus plus and I will just print out into and number right.

76
00:04:40,780 --> 00:04:46,060
And that's when it said, I think and then I will sign in into my aunt.

77
00:04:47,500 --> 00:04:54,430
And then what we will do is doing my vector push back so we can add it to our vector and it's going

78
00:04:54,430 --> 00:04:56,130
to push back my aunt, right?

79
00:04:57,490 --> 00:04:57,820
All right.

80
00:04:57,820 --> 00:05:03,580
So that's a loop that should get input five times into an integer variable and then push that variable

81
00:05:03,580 --> 00:05:05,650
back to the vector.

82
00:05:06,730 --> 00:05:09,070
So now we need to think about sorting it right.

83
00:05:09,080 --> 00:05:13,630
We filled our vector with numbers, and we need to now do both sort.

84
00:05:13,660 --> 00:05:15,080
So what was bubble sort?

85
00:05:15,110 --> 00:05:21,630
Well, we said we were going to go over all the possible swaps for all of the integers inside this race.

86
00:05:21,640 --> 00:05:23,490
So there's five integers.

87
00:05:23,500 --> 00:05:27,280
But what I'm going to do is is, say four and I was zero.

88
00:05:27,610 --> 00:05:36,640
I less than and I will say my vec dot size because I'm just going to go through the whole size and I

89
00:05:36,640 --> 00:05:37,990
will say I was plus.

90
00:05:38,710 --> 00:05:46,510
And then in here, I'm going to need to now go over all the possible swaps that I could do for each

91
00:05:46,510 --> 00:05:47,100
one of those.

92
00:05:47,110 --> 00:05:51,340
So we're just going to try and attempt to bubble up.

93
00:05:52,180 --> 00:05:58,750
Every single number in there, all the way to the end, so if it could potentially bubble up until the

94
00:05:58,750 --> 00:06:00,910
end, which it doesn't really make sense, right?

95
00:06:00,910 --> 00:06:04,960
Because if we're pushing like all these sort of things to the end?

96
00:06:06,440 --> 00:06:12,410
There that everything that's been bubbling up and bumping into the end and kind of stacking up from

97
00:06:12,410 --> 00:06:18,020
the right to the left, that's going to be all sorts of stuff, that whole thing that's stacked up from

98
00:06:18,020 --> 00:06:22,250
right to left because we're bubbling stuff from left to right right.

99
00:06:22,250 --> 00:06:26,690
And it's kind of like smashing up like traffic, backing up from the right to the left.

100
00:06:27,680 --> 00:06:32,900
So we don't really need to go back through that sort of section, but we're just going to say whatever

101
00:06:32,960 --> 00:06:36,650
will make the most brute force kind of algorithm that we can.

102
00:06:37,220 --> 00:06:45,560
And I'll just say, for instance, J equals zero and I'll say J is less than my vector size.

103
00:06:45,560 --> 00:06:48,400
And what I'm going to do here is do a minus one.

104
00:06:48,410 --> 00:06:49,760
And why am I going to do that?

105
00:06:49,790 --> 00:06:51,890
Well, think about the last element.

106
00:06:51,890 --> 00:06:57,980
So I'm going to go ahead and here I'll just minimize this and we'll go back here, think about this

107
00:06:57,980 --> 00:06:58,670
last element.

108
00:06:58,680 --> 00:07:00,080
So if we're on the last.

109
00:07:01,970 --> 00:07:08,090
So my vector net size is one two, three four, and this is zero one two three, so four would be out

110
00:07:08,090 --> 00:07:08,720
here, right?

111
00:07:10,220 --> 00:07:16,430
My vector size minus one is here, so last element and we're saying less than my vector size and minus

112
00:07:16,430 --> 00:07:18,920
one, so we're talking about everything up to here.

113
00:07:19,400 --> 00:07:21,560
Why would we want to stop here?

114
00:07:21,590 --> 00:07:28,910
Well, what I'm going to be doing for my swabs is looking at where I am, which could be maximum here.

115
00:07:29,870 --> 00:07:37,130
So if I'm here, this is the last spot since it's my exercise minus one, it's less than that.

116
00:07:38,550 --> 00:07:45,510
So I'm going to try and look at I, which could be here and I +1 if I was to go all the way up to here,

117
00:07:45,510 --> 00:07:48,990
if I looked at I +1, I'd be out here in no man's land.

118
00:07:49,500 --> 00:07:50,490
So I don't want that.

119
00:07:50,490 --> 00:07:55,770
So I want to stop here so I can still look at my plus one and potentially do a swap between these two.

120
00:07:56,010 --> 00:08:00,750
I'm always going to look one ahead of where I am, so if I'm here, I'm going to look at here.

121
00:08:01,170 --> 00:08:03,390
If I'm here, I'm going to look at here.

122
00:08:03,840 --> 00:08:05,730
If I'm here, I'm going to look you here.

123
00:08:06,240 --> 00:08:12,090
But I don't want to be here because if I am here, I don't want to have to look out into empty space.

124
00:08:12,270 --> 00:08:14,190
So that's what I'm talking about.

125
00:08:15,240 --> 00:08:19,500
So that's why I'm going to do less than my vector size minus one.

126
00:08:19,620 --> 00:08:25,500
This is less than my vector size, so it'll go as long as it's not my vector size, it'll go up to the

127
00:08:25,500 --> 00:08:26,280
last element.

128
00:08:26,310 --> 00:08:29,280
This will go up to one before the last element.

129
00:08:29,830 --> 00:08:30,930
I just want to make that clear.

130
00:08:32,880 --> 00:08:34,140
So what do we do now?

131
00:08:34,170 --> 00:08:36,380
Well, I want to put a check here, right?

132
00:08:36,390 --> 00:08:41,820
We need to see if the thing we're at is greater than the thing to the rest of us.

133
00:08:41,970 --> 00:08:50,220
So I'm going to say if my vector and I'm I say my vector j, because this is the loop that swaps.

134
00:08:51,360 --> 00:09:00,000
This first loop is just saying, do all of this swapping and bubbling for as many times as there are

135
00:09:00,000 --> 00:09:05,940
things in the vector which you notice this will go from zero to four.

136
00:09:05,970 --> 00:09:06,420
Right?

137
00:09:06,690 --> 00:09:15,300
So zero one to three four, that's five times this inner loop is the actual swapping bubbling part.

138
00:09:15,320 --> 00:09:17,050
So that's why I'm using J.

139
00:09:17,370 --> 00:09:30,000
I'm going to say if my Vector J is greater than my Vector J plus one, then what we want to do is we

140
00:09:30,000 --> 00:09:31,890
want to swap them.

141
00:09:32,400 --> 00:09:38,490
So this is where you might have been a little confused during the lecture, but I said something like

142
00:09:38,490 --> 00:09:50,820
We don't really want to put my vector J equals my act j plus one and then just go here and then you're

143
00:09:50,820 --> 00:09:52,560
like, Oh, great, now I'll just do it backwards.

144
00:09:52,560 --> 00:10:00,300
My back j plus one equals my vector, j.

145
00:10:00,330 --> 00:10:06,150
Oh, wait, no, I just said that my VC j is equal to my vector j plus one.

146
00:10:07,680 --> 00:10:09,720
So now my vector J.

147
00:10:10,730 --> 00:10:15,830
Holds my vote plus one, so when I go here and I say my big J plus one.

148
00:10:17,010 --> 00:10:23,040
I'm just storing mine like J Plus one in my verdict, J Plus one, so they're just both going to have

149
00:10:23,040 --> 00:10:23,630
the same thing.

150
00:10:23,640 --> 00:10:24,450
I don't want that.

151
00:10:24,600 --> 00:10:27,470
I just kind of overrode J.

152
00:10:27,750 --> 00:10:29,040
It's been overwritten.

153
00:10:29,070 --> 00:10:29,460
It's.

154
00:10:30,450 --> 00:10:32,740
Copied over, and now I don't have it yet.

155
00:10:32,760 --> 00:10:37,950
It's just been covered up, clobbered whatever you want to use, whatever term, so it doesn't even

156
00:10:37,950 --> 00:10:38,600
exist anymore.

157
00:10:38,610 --> 00:10:39,770
We lost that value there.

158
00:10:39,780 --> 00:10:46,200
So what we have to do is actually save Jay in some sort of variable.

159
00:10:46,210 --> 00:10:49,380
So why don't we make a new variable up here?

160
00:10:49,410 --> 00:10:51,080
I'm going to say and temp.

161
00:10:51,090 --> 00:10:53,250
So it's like a temporary variable, right?

162
00:10:54,870 --> 00:11:04,190
And then what I'm going to say down here is I'm going to say temp equals my index, j.

163
00:11:05,550 --> 00:11:11,040
So now what I can do is I've saved my leg j into temp and I haven't.

164
00:11:11,040 --> 00:11:17,400
Oh, since I over wrote this, but I can just use a copy of it and now say my like j plus one equals

165
00:11:17,520 --> 00:11:21,690
what used to be at my Beck J before it got overwritten with this.

166
00:11:22,560 --> 00:11:24,300
So that's how you should do swaps.

167
00:11:24,300 --> 00:11:25,800
You should make a temp variable.

168
00:11:25,810 --> 00:11:28,380
You can also make your own swap function.

169
00:11:28,390 --> 00:11:29,700
That would be a lot cleaner.

170
00:11:30,630 --> 00:11:31,950
Just make a separate function.

171
00:11:31,950 --> 00:11:36,300
And then all you have to do is replace all of this with a call to that swap function.

172
00:11:37,620 --> 00:11:39,480
But I'm just going to do it in the for loop for now.

173
00:11:41,070 --> 00:11:46,770
So I'm going to go ahead and add this little bracket here for that, and then I'm going to add one more

174
00:11:46,770 --> 00:11:47,520
bracket there.

175
00:11:47,760 --> 00:11:50,520
And now we need to do is go ahead and print this out.

176
00:11:50,520 --> 00:11:55,210
So I'm just going to have pretty much another loop just like this.

177
00:11:55,380 --> 00:12:05,100
I actually could probably just copy paste this, come down here or what's actually I want to do that,

178
00:12:05,730 --> 00:12:06,360
you see,

179
00:12:09,300 --> 00:12:17,100
so I can actually just come here, paste this and then I can, like, delete this because I only want

180
00:12:17,100 --> 00:12:26,720
to see our stuff so I can see out and I will see out my next high ranking.

181
00:12:26,720 --> 00:12:27,810
It's going to be five.

182
00:12:27,810 --> 00:12:32,460
I really should put my vector size in here, though, because that's a lot cleaner.

183
00:12:33,600 --> 00:12:35,910
The five is just how many we want to start out with.

184
00:12:35,910 --> 00:12:38,820
And then subsequently, I can use my vector size.

185
00:12:40,290 --> 00:12:44,220
This just kind of a cleaner way to go about it, so now I have these three loops, I'll go ahead and

186
00:12:44,220 --> 00:12:44,720
print that out.

187
00:12:44,730 --> 00:12:48,630
I should probably put a little space between them just so it looks kind of clean.

188
00:12:49,410 --> 00:12:51,340
So let's go ahead and test this out.

189
00:12:51,360 --> 00:12:52,440
It should be good to go.

190
00:12:53,160 --> 00:12:55,140
I'm going to go ahead and pilot.

191
00:12:58,800 --> 00:13:03,660
So now I can runs that out into some numbers.

192
00:13:03,670 --> 00:13:07,950
So how about we do like five three?

193
00:13:09,060 --> 00:13:09,900
One two.

194
00:13:11,950 --> 00:13:13,620
And seven.

195
00:13:14,590 --> 00:13:18,910
And there we see one, two, three, five, seven, it's in order we should probably put a new line,

196
00:13:18,910 --> 00:13:23,330
though, so let me go back to bubble bubble sort C.P..

197
00:13:23,380 --> 00:13:27,760
We'll go ahead and just see out in the line here.

198
00:13:28,750 --> 00:13:33,220
I'll save this running in an analogy.

199
00:13:33,220 --> 00:13:36,280
Just like take some random stuff.

200
00:13:38,680 --> 00:13:39,590
And there we go.

201
00:13:39,610 --> 00:13:40,840
Look, we got them all in order.

202
00:13:40,840 --> 00:13:42,940
720 for thirty to forty five.

203
00:13:42,940 --> 00:13:43,840
Sixty seven.

204
00:13:45,000 --> 00:13:46,570
So pretty simple.

205
00:13:46,590 --> 00:13:56,700
This is like the most simple sort that you could do if you weren't able to figure out the sort of thing,

206
00:13:56,700 --> 00:14:01,860
don't worry, it is a little bit confusing the whole swapping thing and knowing how to set it up.

207
00:14:02,190 --> 00:14:09,090
You might have come up with another sorting algorithm that already exists.

208
00:14:09,600 --> 00:14:15,460
So it would be cool to go check to see if what you did is something that already exists.

209
00:14:15,480 --> 00:14:20,280
I'm going to be going over some other algorithms and you may realize when we go over them that this

210
00:14:20,280 --> 00:14:22,920
is the algorithm that you actually came up with.

211
00:14:23,730 --> 00:14:30,290
There are some sorting algorithms out there that are much more efficient than Bulbasaur.

212
00:14:30,300 --> 00:14:36,990
In fact, mobile is pretty much the worst sorting algorithm out of them all in terms of speed or efficiency.

213
00:14:38,490 --> 00:14:42,730
But nevertheless, it gets the job done, and that's what's important.

214
00:14:42,780 --> 00:14:48,450
In the beginning, we want to find a naive brute force solution just so we can at least solve the problem,

215
00:14:48,450 --> 00:14:48,750
right?

216
00:14:49,260 --> 00:14:52,590
Afterwards, we can look at making a better, more efficient solution.

217
00:14:52,620 --> 00:14:56,640
This is something that will come up a lot in the algorithms section of the course.

218
00:14:56,650 --> 00:15:01,260
Right now, we're not going to focus too heavy on trying to optimize all of our solutions, but we will

219
00:15:01,260 --> 00:15:08,580
cover a few algorithms that can sort and come in like slightly more complex ways, maybe not necessarily

220
00:15:08,580 --> 00:15:11,520
more efficient, but just look into some different algorithms.

221
00:15:12,830 --> 00:15:13,470
First sorting.

222
00:15:13,490 --> 00:15:14,210
So, all right.

223
00:15:14,450 --> 00:15:17,090
So with that, I will see you in the next lecture.