1
00:00:00,820 --> 00:00:01,653
- [Instructor] Okay.

2
00:00:01,653 --> 00:00:03,210
So in the previous video,

3
00:00:03,210 --> 00:00:06,560
we gave a brief introduction
to selection sort,

4
00:00:06,560 --> 00:00:09,050
and we showed some pseudo-code

5
00:00:09,050 --> 00:00:11,610
and walked through how
selection sort works.

6
00:00:11,610 --> 00:00:13,780
In this video we're going to code it up

7
00:00:13,780 --> 00:00:16,163
in C plus plus like we
did with bubble sort.

8
00:00:17,070 --> 00:00:18,560
So let's start

9
00:00:19,590 --> 00:00:23,180
and we'll create a new file
again I'm gonna put everything

10
00:00:23,180 --> 00:00:25,950
in one file, no headers, no fuss, no Moss.

11
00:00:25,950 --> 00:00:27,833
And we'll call this selection sort.

12
00:00:31,300 --> 00:00:32,133
Okay.

13
00:00:34,530 --> 00:00:36,970
And we're gonna need a couple of things,

14
00:00:36,970 --> 00:00:38,463
We're gonna need vector.

15
00:00:44,160 --> 00:00:47,793
And we're gonna need iostream.

16
00:00:55,080 --> 00:00:57,750
And then I'm gonna go to the code

17
00:00:57,750 --> 00:01:00,570
that we had from the last time.

18
00:01:00,570 --> 00:01:03,170
And I'm gonna borrow this code here

19
00:01:03,170 --> 00:01:06,300
that we use this function
for printing the vector.

20
00:01:06,300 --> 00:01:08,853
We're just gonna borrow that copy paste.

21
00:01:10,060 --> 00:01:10,893
Okay.

22
00:01:10,893 --> 00:01:15,570
And then we're going to create a function

23
00:01:15,570 --> 00:01:17,673
that implements selection sort.

24
00:01:26,090 --> 00:01:29,223
And that's gonna take us in your,

25
00:01:31,730 --> 00:01:32,563
vector

26
00:01:35,070 --> 00:01:37,000
And we'll make that comparable

27
00:01:39,190 --> 00:01:40,223
As before.

28
00:01:46,470 --> 00:01:50,343
Let's just copy this
template code here too.

29
00:01:54,625 --> 00:01:57,170
And so now we need to complete
the body of the function.

30
00:01:57,170 --> 00:02:00,210
Now let's recall what
happens in selection sort.

31
00:02:00,210 --> 00:02:02,740
In selection sort we take a vector

32
00:02:02,740 --> 00:02:05,150
and it's divided into two parts

33
00:02:05,150 --> 00:02:06,750
in the first iteration.

34
00:02:06,750 --> 00:02:11,143
One part is empty and the other
part is the entire vector.

35
00:02:12,618 --> 00:02:13,910
And we find the minimum value.

36
00:02:13,910 --> 00:02:16,500
And then we swap the
minimum value that we find

37
00:02:16,500 --> 00:02:17,840
in the unsorted part

38
00:02:17,840 --> 00:02:21,350
with the left most element in the vector

39
00:02:21,350 --> 00:02:23,903
of the element with the smallest index.

40
00:02:26,990 --> 00:02:30,600
And then we just continue to iterate.

41
00:02:30,600 --> 00:02:32,770
So we're going to need a for loop

42
00:02:37,150 --> 00:02:39,463
and we'll call the swap index,

43
00:02:45,220 --> 00:02:48,263
and swap index.

44
00:02:51,860 --> 00:02:54,283
Less than the size of the vector,

45
00:02:59,120 --> 00:03:00,393
and Increment swap Index.

46
00:03:07,551 --> 00:03:09,920
And that's our outer loop.

47
00:03:09,920 --> 00:03:11,680
Then inside,

48
00:03:11,680 --> 00:03:14,920
we're going to have integer,

49
00:03:14,920 --> 00:03:16,863
variable mean index.

50
00:03:19,760 --> 00:03:21,070
Use the index of the minimum

51
00:03:21,070 --> 00:03:23,803
and we're gonna set that
to swap index to start.

52
00:03:25,770 --> 00:03:28,010
Then we're gonna have our inner loop

53
00:03:29,550 --> 00:03:34,550
for I equal swap index plus one

54
00:03:40,840 --> 00:03:43,640
because we start the
iteration of our inner loop

55
00:03:43,640 --> 00:03:47,720
from the first unsorted
element in our vector.

56
00:03:47,720 --> 00:03:51,440
And I less than

57
00:03:56,885 --> 00:03:57,733
and increment.

58
00:04:03,820 --> 00:04:06,900
This is the loop where
we're finding the index

59
00:04:06,900 --> 00:04:08,230
of the minimum value

60
00:04:08,230 --> 00:04:12,030
in the unsorted portion of our effector.

61
00:04:12,030 --> 00:04:17,030
So if the sub pop user by is less

62
00:04:22,290 --> 00:04:26,803
than the current, the index,

63
00:04:28,500 --> 00:04:32,050
then we found a smaller value.

64
00:04:32,050 --> 00:04:34,060
And so we'll update mean index

65
00:04:36,480 --> 00:04:37,513
with high,

66
00:04:39,420 --> 00:04:40,540
simple as that.

67
00:04:40,540 --> 00:04:42,710
So when we encounter a smaller value,

68
00:04:42,710 --> 00:04:44,563
we update that mean index value.

69
00:04:46,950 --> 00:04:49,770
Having completed that inner loop.

70
00:04:49,770 --> 00:04:52,230
Now we know the smallest element

71
00:04:52,230 --> 00:04:54,520
in the unsorted portion of the vector.

72
00:04:54,520 --> 00:04:57,990
And so we're going to swap it
with the appropriate element

73
00:04:57,990 --> 00:04:59,540
but to complete the outer loop.

74
00:05:02,690 --> 00:05:07,373
So we'll swap comparable,

75
00:05:10,130 --> 00:05:12,040
and call it temp.

76
00:05:12,040 --> 00:05:14,990
And this should look similar
to what we did in bubble sort.

77
00:05:19,720 --> 00:05:23,060
That's the element in the vector.

78
00:05:23,060 --> 00:05:28,060
That's the smallest minimum
value in the unsorted portion.

79
00:05:29,220 --> 00:05:30,373
And then,

80
00:05:31,830 --> 00:05:33,023
in index,

81
00:05:36,580 --> 00:05:37,533
we'll take,

82
00:05:39,010 --> 00:05:41,953
this one we swap it.

83
00:05:45,960 --> 00:05:49,483
That's the left most on the sorted.

84
00:05:51,610 --> 00:05:56,610
And then we do V swap
index will take time.

85
00:06:02,900 --> 00:06:06,880
And that my friends is our selection sort.

86
00:06:06,880 --> 00:06:09,570
I'm gonna put in a little extra code here

87
00:06:09,570 --> 00:06:13,170
that is not strictly
necessary for selection sort,

88
00:06:13,170 --> 00:06:16,740
but will help us keep
track of what's going on

89
00:06:16,740 --> 00:06:19,340
and allow us to compare the result

90
00:06:19,340 --> 00:06:20,660
we get with selection sort

91
00:06:20,660 --> 00:06:22,483
with what we get from bubble sort.

92
00:06:23,330 --> 00:06:27,120
So I'm gonna put In two
additional variables here

93
00:06:27,120 --> 00:06:28,760
and again these are not necessary

94
00:06:28,760 --> 00:06:31,280
for the implementation of selection sort.

95
00:06:31,280 --> 00:06:34,573
Int and I'm gonna call
this non comparisons.

96
00:06:37,470 --> 00:06:40,860
which is gonna track the number
of comparisons that we make

97
00:06:40,860 --> 00:06:44,190
and Int num swaps

98
00:06:46,340 --> 00:06:48,180
we'll set that also equal to zero

99
00:06:48,180 --> 00:06:50,560
So we can count the number of comparisons

100
00:06:50,560 --> 00:06:51,393
in the number of swaps

101
00:06:51,393 --> 00:06:55,310
that we make when we go
through this algorithm.

102
00:06:55,310 --> 00:06:59,190
And so where do we make comparisons?

103
00:06:59,190 --> 00:07:03,850
We're gonna make comparisons
in this inner loop here

104
00:07:03,850 --> 00:07:07,160
where we're searching
for the minimum value

105
00:07:07,160 --> 00:07:10,240
in the unsorted portion of our vector.

106
00:07:10,240 --> 00:07:13,330
And so every time we iterate

107
00:07:13,330 --> 00:07:15,630
through this part, this inner loop

108
00:07:15,630 --> 00:07:20,630
we're going to increase num comparisons,

109
00:07:20,670 --> 00:07:22,070
we're keeping count

110
00:07:22,070 --> 00:07:24,360
so every iteration of that inner loop

111
00:07:24,360 --> 00:07:26,793
is gonna be another comparison.

112
00:07:27,840 --> 00:07:31,220
And then when we get down here,

113
00:07:31,220 --> 00:07:35,593
we've made a swap so we're
gonna count numb swaps.

114
00:07:39,430 --> 00:07:40,830
Okay.

115
00:07:40,830 --> 00:07:43,570
And then at the very end,

116
00:07:43,570 --> 00:07:47,460
let's put in a little code
to print out what we've done.

117
00:07:47,460 --> 00:07:52,033
So under see out comparisons

118
00:08:00,870 --> 00:08:02,993
and then numb comparisons,

119
00:08:04,520 --> 00:08:07,123
and then a standard in line.

120
00:08:10,860 --> 00:08:12,463
And then one more line,

121
00:08:13,780 --> 00:08:15,803
to print out the number of swaps.

122
00:08:35,000 --> 00:08:39,830
And now let's write a
little main function here

123
00:08:41,720 --> 00:08:43,273
Int main,

124
00:08:49,020 --> 00:08:52,770
and what we're gonna do here
is we're gonna create a vector

125
00:08:52,770 --> 00:08:55,853
so we can test our
selection sort algorithm.

126
00:08:57,698 --> 00:08:58,880
And so I'll need a vector

127
00:09:01,380 --> 00:09:04,030
and we'll make it a vector
of ints cause that's easy.

128
00:09:05,370 --> 00:09:08,420
We'll call it V and we'll
initialize it just the way we did

129
00:09:08,420 --> 00:09:10,570
in the last one using these curly braces.

130
00:09:10,570 --> 00:09:15,570
So four, nine, seven, three,
eight, five zero, one, two, six

131
00:09:24,318 --> 00:09:26,543
and that's all our
values from zero to nine,

132
00:09:27,380 --> 00:09:28,430
which should be fine.

133
00:09:29,930 --> 00:09:31,630
And we'll print that vector

134
00:09:38,940 --> 00:09:40,990
and then we'll do a selection sort on it.

135
00:09:44,620 --> 00:09:45,453
And you know what?

136
00:09:45,453 --> 00:09:46,343
I forgot something.

137
00:09:47,830 --> 00:09:49,523
I'm gonna do one more thing here.

138
00:09:52,280 --> 00:09:53,530
Let me do numb swaps.

139
00:09:53,530 --> 00:09:57,653
I'm gonna do vector.

140
00:09:59,300 --> 00:10:00,750
Just like we did with bubble sorts.

141
00:10:00,750 --> 00:10:03,880
So we can see at each
iteration of the outer loop

142
00:10:03,880 --> 00:10:06,450
what the vector looks
like as we're sorting it.

143
00:10:06,450 --> 00:10:07,360
Okay.

144
00:10:07,360 --> 00:10:11,913
So now we have the house

145
00:10:11,913 --> 00:10:14,230
This is the actual code

146
00:10:14,230 --> 00:10:18,853
that's implementing selection
sort minus this line here.

147
00:10:19,770 --> 00:10:24,770
The rest is for our own
purposes here in demonstration,

148
00:10:27,140 --> 00:10:29,560
And then we haven't mean
where we create a vector

149
00:10:29,560 --> 00:10:30,840
we're gonna print the vector,

150
00:10:30,840 --> 00:10:31,940
we're gonna sort the vector

151
00:10:31,940 --> 00:10:33,890
and every time we iterate
on that outer loop

152
00:10:33,890 --> 00:10:36,170
we're gonna get a print out of the vector.

153
00:10:36,170 --> 00:10:37,433
So let's give it a try.

154
00:10:44,660 --> 00:10:46,120
Okay. So

155
00:10:47,090 --> 00:10:49,600
this looks about right
let's just walk through this

156
00:10:49,600 --> 00:10:50,690
and make sure that this

157
00:10:50,690 --> 00:10:53,670
is in accordance with our expectations.

158
00:10:53,670 --> 00:10:56,340
So we start with this input factor,

159
00:10:56,340 --> 00:10:58,933
which agrees with this year,

160
00:10:59,830 --> 00:11:03,400
and then we search the entire thing

161
00:11:04,540 --> 00:11:07,280
and we find the minimum value
and we swap that with four.

162
00:11:07,280 --> 00:11:09,630
So now we find that zero
and four are swapped

163
00:11:09,630 --> 00:11:12,003
see here's zero and four and zero four.

164
00:11:13,920 --> 00:11:16,740
And then we go through the next iteration

165
00:11:16,740 --> 00:11:19,960
and we only search this
part of the vector.

166
00:11:19,960 --> 00:11:22,110
And we find the smallest value is one

167
00:11:22,110 --> 00:11:23,770
and we swap that with nine

168
00:11:23,770 --> 00:11:26,550
and you see we're swapping
nine and one here.

169
00:11:26,550 --> 00:11:31,550
And so we get this vector
and then we search this part

170
00:11:34,317 --> 00:11:36,040
of the vector and we
find the minimum value

171
00:11:36,040 --> 00:11:38,340
which is two that gets swapped with seven.

172
00:11:38,340 --> 00:11:39,730
And you can see swap seven

173
00:11:39,730 --> 00:11:42,040
and two are being swapped here

174
00:11:42,040 --> 00:11:45,743
and we get this factor.

175
00:11:46,670 --> 00:11:49,270
And one more time,

176
00:11:49,270 --> 00:11:51,280
then we search this part

177
00:11:51,280 --> 00:11:52,810
and we find three

178
00:11:52,810 --> 00:11:55,110
and three is already in
the correct position.

179
00:11:55,110 --> 00:11:56,610
So we swap three with three

180
00:11:56,610 --> 00:11:58,900
and we wind up in the same place.

181
00:11:58,900 --> 00:12:02,683
And so nothing happened in that iteration.

182
00:12:03,840 --> 00:12:06,110
And then we search

183
00:12:08,300 --> 00:12:10,270
this part here, sorry,

184
00:12:10,270 --> 00:12:11,350
and we find four

185
00:12:11,350 --> 00:12:12,340
we swap four with eight.

186
00:12:12,340 --> 00:12:14,870
So this looks like it's doing exactly

187
00:12:14,870 --> 00:12:16,470
what we expect it to do.

188
00:12:16,470 --> 00:12:18,210
And our little bookkeeping is telling us

189
00:12:18,210 --> 00:12:21,740
that we performed 45
comparisons and 10 swaps.

190
00:12:21,740 --> 00:12:22,630
And if you recall,

191
00:12:22,630 --> 00:12:24,300
you can see here

192
00:12:24,300 --> 00:12:26,850
we have 10 elements in our vector.

193
00:12:26,850 --> 00:12:29,050
We've performed exactly 10 swaps.

194
00:12:29,050 --> 00:12:30,853
And that is exactly what we expect.

195
00:12:31,790 --> 00:12:35,250
And so now, just for
the sake of comparison

196
00:12:35,250 --> 00:12:38,120
we compared a selection
sort, a bubble sort

197
00:12:38,120 --> 00:12:40,100
in the earlier video,

198
00:12:40,100 --> 00:12:42,690
let's just copy and paste some code

199
00:12:42,690 --> 00:12:44,560
from our bubble sort

200
00:12:45,960 --> 00:12:48,493
from the last coding session.

201
00:12:51,040 --> 00:12:52,463
And we already have that.

202
00:12:55,630 --> 00:13:00,630
We already have included in
that the code that keeps track

203
00:13:01,930 --> 00:13:03,670
of the number of comparisons

204
00:13:03,670 --> 00:13:06,060
let's also put in code

205
00:13:06,060 --> 00:13:09,360
that keeps track of the number of swaps

206
00:13:09,360 --> 00:13:12,630
and num swaps

207
00:13:14,150 --> 00:13:15,600
let's call that just probable search

208
00:13:15,600 --> 00:13:17,440
cause we don't have three anymore.

209
00:13:17,440 --> 00:13:18,350
Okay.

210
00:13:18,350 --> 00:13:19,760
And where do we swap?

211
00:13:19,760 --> 00:13:21,840
We swap here.

212
00:13:21,840 --> 00:13:25,963
So here is where we will
increment num swaps.

213
00:13:29,450 --> 00:13:32,880
And then let's just borrow this code here

214
00:13:34,640 --> 00:13:37,250
cause that's gonna be identical in both.

215
00:13:37,250 --> 00:13:39,590
And this will print out
the number of comparisons

216
00:13:39,590 --> 00:13:43,360
in the number of swaps that
we've made for bubble sort.

217
00:13:43,360 --> 00:13:47,023
And so let's just copy all this,

218
00:13:49,000 --> 00:13:51,343
and we don't need this.

219
00:13:54,590 --> 00:13:55,890
We're gonna do bubble sort

220
00:13:59,800 --> 00:14:02,103
and let's just put a
blank line between them.

221
00:14:10,570 --> 00:14:12,580
Okay. So there we go.

222
00:14:12,580 --> 00:14:14,830
So now let's run this

223
00:14:16,810 --> 00:14:18,003
and compare,

224
00:14:19,990 --> 00:14:21,260
Oh, dear.

225
00:14:21,260 --> 00:14:22,940
we have a problem.

226
00:14:22,940 --> 00:14:24,993
I forgot to initialize them swaps.

227
00:14:26,130 --> 00:14:29,483
See that bad, bad, bad.

228
00:14:31,140 --> 00:14:31,973
Do it again.

229
00:14:34,070 --> 00:14:36,500
Sorry. Okay.

230
00:14:36,500 --> 00:14:38,670
So here we are.

231
00:14:38,670 --> 00:14:40,380
Here's our output.

232
00:14:40,380 --> 00:14:44,650
What we have in the beginning,
this is our selection sort

233
00:14:44,650 --> 00:14:48,280
notice that it has to go through 10 times

234
00:14:48,280 --> 00:14:52,063
if it has 10 elements, but
it only makes 10 swaps.

235
00:14:53,160 --> 00:14:55,970
Because bubble sort knows
how to bail out early.

236
00:14:55,970 --> 00:15:00,070
If it's not making any more
swaps, we only do one, two

237
00:15:00,070 --> 00:15:03,060
three, four, five, six, seven iterations

238
00:15:03,060 --> 00:15:05,000
before it's finished.

239
00:15:05,000 --> 00:15:10,000
It performs 42 comparisons,
but it performs 29 swaps

240
00:15:10,090 --> 00:15:13,150
which is almost three
times the number of swaps

241
00:15:13,150 --> 00:15:15,410
that selection sort makes.

242
00:15:15,410 --> 00:15:18,483
And so let's just go back
to the code real quick.

243
00:15:19,460 --> 00:15:21,250
So we can end on this.

244
00:15:21,250 --> 00:15:24,070
This is our implementation
of selection sort

245
00:15:24,070 --> 00:15:25,713
with a little extra bookkeeping.

246
00:15:26,930 --> 00:15:28,460
And I hope that makes it clear to you

247
00:15:28,460 --> 00:15:30,023
how selection sort works.