1
00:00:01,260 --> 00:00:02,440
- [Instructor] Hey there.

2
00:00:02,440 --> 00:00:03,943
Let's do radix sort.

3
00:00:04,920 --> 00:00:07,530
As you recall, radix sort works

4
00:00:07,530 --> 00:00:09,990
by distributing and collecting.

5
00:00:09,990 --> 00:00:13,710
It sorts without making comparisons.

6
00:00:13,710 --> 00:00:16,960
We proceed digit by digit
or letter by letter.

7
00:00:16,960 --> 00:00:21,490
And distribute out to bins or buckets

8
00:00:21,490 --> 00:00:25,020
and then collect the
values into our vector

9
00:00:25,020 --> 00:00:28,310
and we iterate as many times
as we have digits or letters

10
00:00:28,310 --> 00:00:29,964
that we need to work with.

11
00:00:29,964 --> 00:00:33,930
And so each implementation of radix sort

12
00:00:33,930 --> 00:00:35,870
is going to be a little different.

13
00:00:35,870 --> 00:00:38,420
I would write a very different algorithm,

14
00:00:38,420 --> 00:00:39,790
well, not a very different algorithm

15
00:00:39,790 --> 00:00:41,810
but I would write a different algorithm

16
00:00:41,810 --> 00:00:44,630
for working with strings

17
00:00:44,630 --> 00:00:46,720
than I would for working with integers

18
00:00:46,720 --> 00:00:47,880
and that's one of the reasons

19
00:00:47,880 --> 00:00:51,650
why we won't implement this
as a templated function,

20
00:00:51,650 --> 00:00:54,890
like we've done with so many others here.

21
00:00:54,890 --> 00:00:56,123
So let's begin.

22
00:00:57,990 --> 00:01:01,267
I'm gonna create a file called radixSort.

23
00:01:04,697 --> 00:01:06,364
And we're gonna need

24
00:01:09,450 --> 00:01:10,723
vector obviously.

25
00:01:12,140 --> 00:01:15,793
And we're gonna include cmath.

26
00:01:16,890 --> 00:01:18,930
Cmath is the standard math library

27
00:01:18,930 --> 00:01:21,660
and we're gonna use powers and logarithms.

28
00:01:21,660 --> 00:01:23,420
You'll see where we do that

29
00:01:23,420 --> 00:01:26,760
but that's for calculating
the number of digits

30
00:01:26,760 --> 00:01:31,230
and recovering a specific
digit for a given number.

31
00:01:31,230 --> 00:01:33,840
Include iostream

32
00:01:36,470 --> 00:01:41,470
and let's get that snippet we've
been using for printVector.

33
00:01:43,880 --> 00:01:44,713
Okay.

34
00:01:45,800 --> 00:01:49,133
And now let's get down with
the business of radix sort.

35
00:01:50,270 --> 00:01:52,363
So we're going to have a void function.

36
00:01:54,030 --> 00:01:54,930
Call it radixSort.

37
00:01:57,240 --> 00:01:58,490
That makes sense, right?

38
00:01:58,490 --> 00:02:01,810
And it's gonna take a std::vector

39
00:02:01,810 --> 00:02:04,783
and we're gonna make this
implementation for integers,

40
00:02:06,300 --> 00:02:10,000
specifically nonnegative integers.

41
00:02:10,000 --> 00:02:11,263
And we'll call that v.

42
00:02:12,260 --> 00:02:15,720
And we also need to pass
in the number of digits.

43
00:02:15,720 --> 00:02:17,103
Int numDigits

44
00:02:20,210 --> 00:02:23,160
so that radixSort knows how many digits

45
00:02:23,160 --> 00:02:25,080
it has to work with, okay?

46
00:02:25,080 --> 00:02:28,653
Because we're gonna iterate
over the number of digits.

47
00:02:29,820 --> 00:02:32,100
And let's do this.

48
00:02:32,100 --> 00:02:36,690
I showed you function overloading before

49
00:02:36,690 --> 00:02:40,713
and so we're gonna create
another void radixSort

50
00:02:43,403 --> 00:02:46,063
that takes, I'm just gonna
copy this, std::vector.

51
00:02:48,230 --> 00:02:50,360
And just that.

52
00:02:50,360 --> 00:02:53,110
And so that's gonna have
to calculate numDigits

53
00:02:53,110 --> 00:02:55,840
and then make a call to radixSort,

54
00:02:55,840 --> 00:02:58,790
providing numDigits, so the
last thing this is gonna do

55
00:02:58,790 --> 00:02:59,940
is gonna call radixSort

56
00:03:03,600 --> 00:03:06,667
with v and numDigits.

57
00:03:09,400 --> 00:03:12,570
And that's gonna live there in red

58
00:03:12,570 --> 00:03:15,790
until we get that resolved.

59
00:03:15,790 --> 00:03:17,420
And then finally, we need main.

60
00:03:17,420 --> 00:03:18,613
Int main.

61
00:03:21,270 --> 00:03:24,363
And no parameters and return zero.

62
00:03:25,770 --> 00:03:26,603
Okay.

63
00:03:28,300 --> 00:03:30,010
So let's get started.

64
00:03:30,010 --> 00:03:31,500
I'm gonna start with this one.

65
00:03:31,500 --> 00:03:34,210
So the first thing that
we're gonna wanna do

66
00:03:34,210 --> 00:03:38,320
is we're gonna want to
calculate the number of digits

67
00:03:38,320 --> 00:03:42,630
and that's gonna add some
overhead to our algorithm

68
00:03:42,630 --> 00:03:45,300
but it's only gonna add one pass,

69
00:03:45,300 --> 00:03:47,890
we have to make one
pass through the vector

70
00:03:47,890 --> 00:03:51,250
in order to find the largest number

71
00:03:51,250 --> 00:03:53,010
and then from the largest number,

72
00:03:53,010 --> 00:03:55,340
we'll calculate how many digits it has

73
00:03:55,340 --> 00:03:58,400
and then call radixSort
with that number of digits.

74
00:03:58,400 --> 00:04:03,400
So scanning the vector to find
the largest number is easy.

75
00:04:03,560 --> 00:04:06,150
We start with int maxNum

76
00:04:08,110 --> 00:04:11,040
and since we're working
with nonnegative integers,

77
00:04:11,040 --> 00:04:13,080
we'll start that at zero.

78
00:04:13,080 --> 00:04:16,033
And for int,

79
00:04:17,010 --> 00:04:21,980
we'll call that num in the vector, right?

80
00:04:21,980 --> 00:04:23,530
And we know that's gonna be an integer

81
00:04:23,530 --> 00:04:25,490
because we're working
with a vector of integers,

82
00:04:25,490 --> 00:04:27,223
not a vector of comparables.

83
00:04:28,100 --> 00:04:32,673
If num is greater than maxNum,

84
00:04:36,620 --> 00:04:37,720
then we update maxNum.

85
00:04:44,760 --> 00:04:46,223
Okay, that's it.

86
00:04:47,290 --> 00:04:51,710
So now we know what the largest
number is in the vector.

87
00:04:51,710 --> 00:04:55,490
And then we need to calculate
how many digits it has.

88
00:04:55,490 --> 00:04:57,103
So int numDigits

89
00:05:00,810 --> 00:05:03,980
equals, and I'm gonna type this out here

90
00:05:03,980 --> 00:05:05,800
and then explain it to you.

91
00:05:05,800 --> 00:05:10,800
We're gonna use the standard
log base 10 function

92
00:05:13,960 --> 00:05:16,460
and we're gonna call that providing maxNum

93
00:05:19,760 --> 00:05:21,550
as a parameter

94
00:05:21,550 --> 00:05:23,670
and then we're gonna add one.

95
00:05:23,670 --> 00:05:25,270
Okay, so what are we doing here?

96
00:05:26,520 --> 00:05:28,320
We've got maxNum,

97
00:05:28,320 --> 00:05:32,350
so we're calling log base 10 on maxNum

98
00:05:32,350 --> 00:05:35,130
and so if maxNum is say one,

99
00:05:35,130 --> 00:05:37,750
we take log 10 of one.

100
00:05:37,750 --> 00:05:42,750
That gets us zero plus one
gives us the number of digits.

101
00:05:43,030 --> 00:05:47,390
If it were 10, we take
log base 10 of maxNum

102
00:05:47,390 --> 00:05:50,110
and we'd give us one

103
00:05:50,110 --> 00:05:52,820
because log base 10 of 10 is one.

104
00:05:52,820 --> 00:05:54,530
Add one to get the number of digits.

105
00:05:54,530 --> 00:05:56,870
We have two digits and so on.

106
00:05:56,870 --> 00:06:01,000
So this gives us the number of digits

107
00:06:01,000 --> 00:06:03,100
and now we can call radixSort

108
00:06:03,100 --> 00:06:04,810
with that number of digits

109
00:06:04,810 --> 00:06:09,810
and so that's going to
be this function here.

110
00:06:09,890 --> 00:06:12,460
We're gonna start by
creating a number of buckets

111
00:06:12,460 --> 00:06:14,400
and again, we're working in base 10

112
00:06:14,400 --> 00:06:16,000
and we know they're integers,

113
00:06:16,000 --> 00:06:19,913
so std::vector,

114
00:06:22,048 --> 00:06:24,913
std:vector, oops,

115
00:06:26,570 --> 00:06:27,703
of integers.

116
00:06:29,700 --> 00:06:31,023
We'll call that buckets.

117
00:06:32,730 --> 00:06:34,760
And we're gonna have 10 of 'em, okay?

118
00:06:34,760 --> 00:06:37,880
So all this is doing is
creating a vector of vectors.

119
00:06:37,880 --> 00:06:40,340
So it's creating a vector of our buckets.

120
00:06:40,340 --> 00:06:41,910
Our buckets hold integers

121
00:06:41,910 --> 00:06:44,030
and there're gonna be 10 of them.

122
00:06:44,030 --> 00:06:46,610
One for the digit zero,
one for the digit one,

123
00:06:46,610 --> 00:06:50,977
one for the digit two,
up to nine and so on.

124
00:06:50,977 --> 00:06:55,520
And now we're gonna iterate
through the digits, okay?

125
00:06:55,520 --> 00:06:59,540
Remember, radixSort is
gonna do what it does

126
00:06:59,540 --> 00:07:00,633
for each digit.

127
00:07:01,650 --> 00:07:06,650
So for, and I'm gonna call
this iteration equals zero.

128
00:07:10,030 --> 00:07:14,203
Iteration less than numDigits.

129
00:07:17,515 --> 00:07:19,682
And ++iteration.

130
00:07:23,930 --> 00:07:24,763
Okay?

131
00:07:25,700 --> 00:07:27,763
So that's our outer loop.

132
00:07:28,690 --> 00:07:29,920
And then what we're gonna do

133
00:07:29,920 --> 00:07:33,110
is we're gonna copy the items

134
00:07:34,500 --> 00:07:35,580
from the vector

135
00:07:37,000 --> 00:07:39,503
into the appropriate buckets.

136
00:07:43,840 --> 00:07:45,141
Okay?

137
00:07:45,141 --> 00:07:46,380
And we do that with another for loop.

138
00:07:46,380 --> 00:07:50,643
For int i equals zero,

139
00:07:52,090 --> 00:07:55,223
i less than the size of the vector.

140
00:07:58,148 --> 00:07:58,981
++i.

141
00:08:00,440 --> 00:08:02,343
And then in the body of our for loop,

142
00:08:03,770 --> 00:08:05,610
we have to calculate the digit,

143
00:08:05,610 --> 00:08:07,690
so int digit

144
00:08:08,970 --> 00:08:11,853
and here we're gonna make use
of the math library again.

145
00:08:13,330 --> 00:08:18,330
V sub i divided by int
std::power 10, iteration.

146
00:08:28,230 --> 00:08:32,270
And we're going to take the modulus 10.

147
00:08:32,270 --> 00:08:36,610
So that's a lot to grasp at a stroke.

148
00:08:36,610 --> 00:08:38,290
But if you'll think back,

149
00:08:38,290 --> 00:08:43,110
I did present this formula
in the earlier video

150
00:08:43,110 --> 00:08:48,010
and what we're doing is this std::power

151
00:08:48,010 --> 00:08:50,710
is just exponentiation.

152
00:08:50,710 --> 00:08:53,870
It's taking 10 and raising
it to the iteration power.

153
00:08:53,870 --> 00:08:57,020
So on the first iteration,
iteration is zero.

154
00:08:57,020 --> 00:08:58,580
10 to the zero is one.

155
00:08:58,580 --> 00:08:59,940
This becomes one.

156
00:08:59,940 --> 00:09:03,670
On the second iteration, iteration is one.

157
00:09:03,670 --> 00:09:05,400
So 10 to the one is 10.

158
00:09:05,400 --> 00:09:07,040
This becomes 10.

159
00:09:07,040 --> 00:09:10,430
On the second pass, or the
third pass I should say,

160
00:09:10,430 --> 00:09:12,030
this value's gonna be two,

161
00:09:12,030 --> 00:09:14,820
this is gonna return 100 and so on.

162
00:09:14,820 --> 00:09:19,720
And then we divide v sub i by that amount

163
00:09:19,720 --> 00:09:23,180
and then we take the modulus base 10.

164
00:09:23,180 --> 00:09:25,543
So let's say we had the value 2,712

165
00:09:28,430 --> 00:09:30,570
and we were in the third iteration.

166
00:09:30,570 --> 00:09:35,050
On the third iteration,
iteration will be two power of 10

167
00:09:36,616 --> 00:09:38,950
raised to the two is gonna be 100.

168
00:09:38,950 --> 00:09:41,100
We're gonna treat that as an integer.

169
00:09:41,100 --> 00:09:42,970
We're gonna divide v sub i,

170
00:09:42,970 --> 00:09:47,970
which I just said is this
hypothetical number, 2,712 by 100.

171
00:09:48,260 --> 00:09:51,380
That's gonna give us 27.12.

172
00:09:51,380 --> 00:09:54,080
And then we're gonna
take the modulus base 10

173
00:09:54,080 --> 00:09:55,560
and that's gonna give us seven.

174
00:09:55,560 --> 00:10:00,220
So the digit then, the third digit

175
00:10:00,220 --> 00:10:05,023
of 2,712 is seven, and that's
what this code does here.

176
00:10:06,660 --> 00:10:09,980
So now we use that digit value

177
00:10:09,980 --> 00:10:11,650
as an index into buckets.

178
00:10:11,650 --> 00:10:15,083
So buckets, digit,

179
00:10:17,430 --> 00:10:21,700
push_back v sub i.

180
00:10:21,700 --> 00:10:24,080
So we're gonna push that value

181
00:10:24,080 --> 00:10:25,480
into the appropriate bucket.

182
00:10:26,490 --> 00:10:29,483
And that is our first loop.

183
00:10:30,450 --> 00:10:32,560
And now what we're gonna do

184
00:10:32,560 --> 00:10:35,730
is we're going to copy everything

185
00:10:37,530 --> 00:10:39,423
from the buckets.

186
00:10:41,860 --> 00:10:42,693
Ah.

187
00:10:43,730 --> 00:10:47,150
Back into the vector

188
00:10:49,010 --> 00:10:50,063
in appropriate order.

189
00:10:53,850 --> 00:10:56,980
Okay, so here's how we do that.

190
00:10:56,980 --> 00:10:59,260
We start by initializing a value.

191
00:10:59,260 --> 00:11:03,883
Call it int i equals zero, okay?

192
00:11:05,360 --> 00:11:07,580
And then for

193
00:11:09,090 --> 00:11:11,210
int bucket

194
00:11:14,010 --> 00:11:17,320
equals zero, that's an
index into the buckets.

195
00:11:17,320 --> 00:11:22,320
Bucket less than buckets.size.

196
00:11:30,565 --> 00:11:31,398
++bucket.

197
00:11:32,610 --> 00:11:35,773
So here, we're iterating
through the buckets.

198
00:11:36,850 --> 00:11:38,710
And then for each bucket,

199
00:11:38,710 --> 00:11:40,870
we're gonna iterate through
the items in the bucket

200
00:11:40,870 --> 00:11:42,810
and then distribute them back out to

201
00:11:42,810 --> 00:11:46,230
or collect them into our vector.

202
00:11:46,230 --> 00:11:49,890
So for int item

203
00:11:51,740 --> 00:11:53,203
equal zero,

204
00:11:54,300 --> 00:11:58,823
item less than buckets,

205
00:12:01,840 --> 00:12:06,043
bucket.size,

206
00:12:08,180 --> 00:12:10,620
so we're gonna iterate through the bucket

207
00:12:12,430 --> 00:12:16,003
and that's, sorry, ++item.

208
00:12:19,840 --> 00:12:21,423
So for each bucket,

209
00:12:23,080 --> 00:12:25,770
we're gonna iterate through
the items in that bucket

210
00:12:26,860 --> 00:12:28,750
and we're gonna collect
them into our vector.

211
00:12:28,750 --> 00:12:33,490
So v sub i equals buckets

212
00:12:35,700 --> 00:12:36,533
bucket

213
00:12:39,070 --> 00:12:39,903
item.

214
00:12:42,070 --> 00:12:45,420
Right, so remember, bucket
is an index into buckets

215
00:12:45,420 --> 00:12:49,813
and item is an index into
the individual buckets, okay?

216
00:12:50,674 --> 00:12:53,790
Then what we need to do
is to clear our buckets.

217
00:12:53,790 --> 00:12:55,630
So buckets

218
00:12:57,980 --> 00:13:01,293
bucket clear.

219
00:13:02,480 --> 00:13:05,527
And clear is just a function, a method

220
00:13:05,527 --> 00:13:07,930
that empties out a vector.

221
00:13:07,930 --> 00:13:11,980
So we have this vector of buckets

222
00:13:11,980 --> 00:13:15,310
and for this bucket, now
that we're done with it,

223
00:13:15,310 --> 00:13:16,850
we're just gonna empty it out.

224
00:13:16,850 --> 00:13:17,823
So we empty it out.

225
00:13:18,940 --> 00:13:23,423
And then lastly, we'll printVector.

226
00:13:26,650 --> 00:13:28,060
V.

227
00:13:28,060 --> 00:13:29,490
So we can see what's going on.

228
00:13:29,490 --> 00:13:33,723
So we're going to watch what happens here.

229
00:13:35,730 --> 00:13:37,103
And this is wrong.

230
00:13:38,800 --> 00:13:41,100
Now, see, I've made a mistake here.

231
00:13:41,100 --> 00:13:43,300
This is what I get for
talking while I type.

232
00:13:44,920 --> 00:13:49,280
This all belongs

233
00:13:51,090 --> 00:13:51,923
in here.

234
00:13:53,180 --> 00:13:54,013
Okay?

235
00:13:54,013 --> 00:13:55,200
Sorry, about that.

236
00:13:55,200 --> 00:13:56,730
My bad.

237
00:13:56,730 --> 00:14:01,500
For each iteration on
the number of digits,

238
00:14:01,500 --> 00:14:03,000
we're going to copy items

239
00:14:03,000 --> 00:14:05,220
from the vector into
the appropriate buckets

240
00:14:05,220 --> 00:14:06,540
and then copy everything

241
00:14:06,540 --> 00:14:08,290
from the buckets back into the vector

242
00:14:08,290 --> 00:14:10,200
in the appropriate order.

243
00:14:10,200 --> 00:14:14,793
So sorry, I got a little ahead
of myself typing that way.

244
00:14:15,760 --> 00:14:19,473
So that should be radixSort.

245
00:14:20,880 --> 00:14:22,890
Okay, so now let's test it.

246
00:14:22,890 --> 00:14:24,793
We'll flesh out main here.

247
00:14:26,910 --> 00:14:28,840
Let's see, we're gonna need a vector

248
00:14:32,640 --> 00:14:33,603
of ints.

249
00:14:35,260 --> 00:14:36,293
Call it v.

250
00:14:37,270 --> 00:14:42,270
And we'll give it some
values with various digits.

251
00:14:44,120 --> 00:14:46,480
17, so some two-digit numbers,

252
00:14:46,480 --> 00:14:48,793
some three-digit numbers and so on.

253
00:14:51,721 --> 00:14:52,753
A one-digit number.

254
00:14:59,620 --> 00:15:02,560
Oops, I left out a comma, sorry.

255
00:15:02,560 --> 00:15:04,733
I'm doing a terrible job typing this time.

256
00:15:06,130 --> 00:15:08,983
44, 115,

257
00:15:10,170 --> 00:15:11,003
289,

258
00:15:12,450 --> 00:15:14,029
28,

259
00:15:14,029 --> 00:15:14,862
815,

260
00:15:15,770 --> 00:15:18,047
71, 9, 84.

261
00:15:19,010 --> 00:15:20,110
That should be enough.

262
00:15:20,993 --> 00:15:23,753
And now we're gonna printVector.

263
00:15:27,590 --> 00:15:29,340
And then we're gonna call radixSort

264
00:15:33,260 --> 00:15:36,730
on v and that's gonna print automatically

265
00:15:36,730 --> 00:15:38,020
but what it's gonna do first

266
00:15:38,020 --> 00:15:40,780
is it's gonna call this radixSort,

267
00:15:40,780 --> 00:15:43,120
which just takes a vector.

268
00:15:43,120 --> 00:15:44,870
It's gonna calculate the largest,

269
00:15:44,870 --> 00:15:46,370
it's gonna find the largest number,

270
00:15:46,370 --> 00:15:47,810
then it's gonna calculate the number

271
00:15:47,810 --> 00:15:51,330
of digits and call radixSort
with the number of digits

272
00:15:51,330 --> 00:15:53,393
and that's when we get to this radixSort.

273
00:15:55,190 --> 00:15:56,893
So let's run it and test it.

274
00:16:00,330 --> 00:16:01,810
And there we go, okay?

275
00:16:01,810 --> 00:16:04,123
So this is our input vector,

276
00:16:05,510 --> 00:16:07,123
which matches what we have here.

277
00:16:09,770 --> 00:16:12,720
This is after the first sorting.

278
00:16:12,720 --> 00:16:14,210
Remember, we have three digits.

279
00:16:14,210 --> 00:16:16,923
So we're gonna have three sortings.

280
00:16:18,350 --> 00:16:21,790
And notice here that we have a zero

281
00:16:21,790 --> 00:16:23,870
in the first digit position,

282
00:16:23,870 --> 00:16:26,580
ones followed by twos, three,

283
00:16:26,580 --> 00:16:29,973
four, four, five, five,
seven, eight, nine.

284
00:16:31,110 --> 00:16:32,403
And now here,

285
00:16:33,920 --> 00:16:36,773
on our second pass through the digits,

286
00:16:37,640 --> 00:16:40,660
the second digit here is a zero.

287
00:16:40,660 --> 00:16:42,100
This is a zero.

288
00:16:42,100 --> 00:16:44,140
This is a zero.

289
00:16:44,140 --> 00:16:49,043
This is a one, one, one, one,
two, two, three and so on.

290
00:16:50,010 --> 00:16:52,940
And then here's the
result of our final pass

291
00:16:53,970 --> 00:16:57,300
where this three is implicitly preceded

292
00:16:57,300 --> 00:17:02,140
by two zeros, two zeros,
one zero and so on.

293
00:17:02,140 --> 00:17:04,683
Up to 901 and we get a sorted vector out.

294
00:17:06,470 --> 00:17:07,610
I think that's pretty cool.

295
00:17:07,610 --> 00:17:09,377
I really like radixSort.

296
00:17:11,080 --> 00:17:13,450
But anyhow, here's the code.

297
00:17:13,450 --> 00:17:14,800
I'll post it on Blackboard.

298
00:17:16,320 --> 00:17:17,520
And we'll see you later.