Original subtitles

1 1

(lively music) (keyboard clacking) 2

2

So, let's implement radix sort. 3

3

I've created a project, I've put the code 4

4

into package academy.learnprogramming.radixsort. 5

5

I've created our array that we're going to sort, 6

6

it's the same array that we went through in the slides 7

7

and I have code for printing out the array after the sort. 8

8

We're gonna create two methods, 9

9

one called radixSort and one called radixSingleSort 10

10

and you'll see what those do in a minute, 11

11

so let's start with radixSort, 12

12

so I'll say public static void radixSort. 13

13

We've gonna accept our input array, 14

14

the radix and the width. 15

15

Remember that for radixSort, 16

16

all the values have to have the same radix 17

17

and the same width 18

18

and then we're gonna say for int i equals zero, 19

19

i less than width, 20

20

i++ and we're gonna call the radixSingleSort method 21

21

that we haven't written yet 22

22

and we're gonna pass the input i and the radix. 23

23

And so, basically what we're doing here 24

24

is we're gonna call radixSingleSort 25

25

for each position in our values 26

26

and so, we have a width of four 27

27

and so, we're gonna loop four times 28

28

and each time we call radixSingleSort, 29

29

it'll do the sort based on one of the positions 30

30

and as you'll see, it'll start with the rightmost position 31

31

and then move to the rightmost minus one position et cetera, 32

32

so it'll be moving along the digits 33

33

from the least significant digit 34

34

to the most significant digit from right to left. 35

35

So, let's write the radixSingleSort method, 36

36

so we'll say public static void radixSingleSort 37

37

and it takes the input array, 38

38

the position and the radix. 39

39

And so, the first thing we're gonna do 40

40

is we're gonna say int numItems 41

41

equals the input array dot length, 42

42

so this just stores how many items 43

43

that we're gonna be sorting. 44

44

And then we're gonna say int countArray equals 45

45

and we're going to create a countArray 46

46

that's large enough to hold all the possible values, 47

47

our radix will be 10 'cause we will have digit zero to nine 48

48

and so, we'll have a countArray of length 10 49

49

and then we're gonna say for int value: input, 50

50

so for every value in our input array, 51

51

we're gonna count how many values have a certain digit 52

52

in whatever position we're looking at, 53

53

so we're gonna call getDigit 54

54

and we're gonna write this method in a minute 55

55

and we're gonna pass the position and the value 56

56

and the radix. 57

57

And this method is going to return the digit, 58

58

so it's gonna return zero to nine 59

59

and then we're going to increment the count by one, 60

60

so when we pass the first value, 4725, 61

61

five's gonna come back as the digit 62

62

and so, we're gonna increment countArray five by one. 63

63

So, before we go any further, 64

64

let's write the getDigit, 65

65

I'm just gonna remove this blank line here, 66

66

we don't really need it. 67

67

Let's write the getDigit method, 68

68

so you can see what it does. 69

69

So, we'll say public static int getDigit, 70

70

it accepts a position, 71

71

a value and the radix. 72

72

And it's not a difficult method. 73

73

It's gonna return value over, 74

74

we're gonna pass this to int 75

75

because we don't want to have 76

76

a floating point value returned. 77

77

I'm just gonna pass Math.pow 10, position 78

78

modded by the radix. 79

79

So, what the heck is this doing? 80

80

The Math.pow method takes the first parameter 81

81

and raises it to the second parameter. 82

82

We've passed in position zero 83

83

because here we're starting at zero, 84

84

so we've passed in zero for the position, 85

85

we have 4725 for the value and 10 for the radix 86

86

and so, we're gonna get Math.pow 10 raised to the zero 87

87

which is one, 'cause anything raised 88

88

to the zero power is one 89

89

and the division operator takes precedence 90

90

over the modulo operator, 91

91

so we're gonna divided the value by one, 4725 divided by one 92

92

is obviously 4725 93

93

and then we're gonna mod that by the radix which is 10. 94

94

Well, 4725 divided by 10 is 472 95

95

and the remainder's gonna be five 96

96

and so, that's what we're gonna return 97

97

and so, for position zero, 98

98

we're always gonna be returning 99

99

what's in the one's position. 100

100

So, let's say we call getDigit with position two instead, 101

101

so instead of calling it with position zero, 102

102

we called it with position two 103

103

which would mean that we're handling the hundreds. 104

104

We'd have 10 to the power of two which is 100, 105

105

we divided 4725 by 100 106

106

and we get 47 and then we mod 47 with 10 107

107

and that would give us a remainder of seven 108

108

and so, we'd return seven for the hundreds position. 109

109

If we wanted the tens position, 110

110

this would be one 111

111

and so, we divide 4275 by 10 112

112

and we get 427 113

113

and then we'd mod that with 10 114

114

and the remainder would be seven 115

115

and so, that's how the getDigit method 116

116

is figuring out what the value of the digit 117

117

at each position is. 118

118

So, returning back to our radixSingleSort method. 119

119

For each value, we're going to get the digit 120

120

at the position and on the first call 121

121

that position will be zero, 122

122

so we're gonna be returning all of the one positions 123

123

and so, it's going to increment the countArray, 124

124

it's gonna count all the values that have zero 125

125

in the one's position, 126

126

all the values that have one, two, three et cetera. 127

127

So, by the time we finish this loop. 128

128

We have a conventional countArray 129

129

where all we're doing is counting the number of values 130

130

that have a specific digit in their one's position. 131

131

But we want this to be a stable counting sort 132

132

and so, we're now going to do the step 133

133

that we discussed in the slides, 134

134

and we need to adjust these counts 135

135

so that instead of having just raw counts 136

136

of how many values, how many specific digit, 137

137

we want each position in the countArray 138

138

to contain how values have that digit 139

139

or less than that digit 140

140

and so, as I said, when we went over the slides, 141

141

all we have to do to get that 142

142

is sum up all of the counts up to and including the digit 143

143

that we're working on, 144

144

so to get the number of values that have three or less 145

145

in the one's position, 146

146

we have to sum up the counts in positions zero, one, 147

147

two and three and so, let's do that now, 148

148

so we'll say for int j equals one, 149

149

we don't have to handle the first index 150

150

because the number of values that have zero 151

151

or less in their one's position 152

152

are gonna be the number of values that have zero, 153

153

so we don't have to worry about changing 154

154

the first count, we just have to worry about changing 155

155

the counts in positions one and beyond, 156

156

so for int j equals one, 157

157

j is less than the radix 158

158

'cause that's the length of our countArray, j++ 159

159

and we just say countArray j 160

160

plus equals countArray j minus one. 161

161

And so, what this loop is doing 162

162

is adding up if j is three, 163

163

it'll add up indices zero, one, two, and three 164

164

and assign and that'll be what countArray three 165

165

ends up being. 166

166

If countArray is five, 167

167

it'll add up indices zero, one, two, three, four and five. 168

168

That's what countArray five'll end up being. 169

169

So, at the end of this I'll put a comment in here, 170

170

adjust the count array. 171

171

And so, at the end of this loop, 172

172

the countArray has been adjusted, 173

173

so instead of containing raw counts, 174

174

it now contains the number of values 175

175

that have that digit or less than that digit 176

176

in the position that we're working with. 177

177

And so, at this point, we're going to do the step 178

178

that we went through on the slides 179

179

where we're going to copy the values 180

180

into a temporary array, 181

181

we're gonna work from right to left 182

182

so that we're preserving the relative ordering 183

183

of duplicates and so, we're gonna create 184

184

that temporary array, 185

185

so we'll say int temp equals 186

186

new int and we need that to be enough 187

187

to hold the number of items we have, 188

188

so we'll say numItems 189

189

and then for int tempIndex equals numItems 190

190

minus one, so we're starting at the end, 191

191

tempIndex greater equal to zero 192

192

and we're going to decrement it. 193

193

On each iteration, we're going to say temp 194

194

minus minus countArray 195

195

and again we're gonna use getDigit, 196

196

position, input tempIndex, radix 197

197

equals and this is gonna equal input tempIndex. 198

198

Now, when we went through the slides, 199

199

I actually called tempIndexK, 200

200

so we're doing exactly, 201

201

this is the exact same code we went through 202

202

on the slides and so, we're working from right to left 203

203

and we're looking at the countArray, 204

204

we're decrementing, remember using the prefix operator, 205

205

so we decrement the value at the countArray 206

206

for the digit first 207

207

and then we use that index to index into the temp array 208

208

and we assign the value at input tempIndex, 209

209

'cause that's what we're working with 210

210

and tempIndex starts at the end of the input array 211

211

and moves right to left. 212

212

So, because we're moving right to left 213

213

with the input array 214

214

and because we're writing from right to left 215

215

in the range of positions occupied 216

216

by a specific digit, 217

217

we preserve the ordering of duplicate values, 218

218

so if you're confused by what this code is doing, 219

219

go to the last video 220

220

because we went through it there, 221

221

just keep in mind that I called in the code 222

222

that I showed you tempIndex and K are one and the same. 223

223

So, at this point, we've copied our values 224

224

into the temporary array. 225

225

They're in sorted order in the temporary array, 226

226

so the last thing we have to do is copy them back 227

227

from the temporary array into the input array. 228

228

So, we could use system.arrayCopy 229

229

but let's just do it using a regular loop, 230

230

so for int, let's use the tempIndex again, 231

231

tempIndex equals zero, 232

232

tempIndex is less than the number of items 233

233

and we'll just increment it, 234

234

tempIndex++, input tempIndex 235

235

equals temp, tempIndex. 236

236

Nothing Earth shattering going on here, 237

237

just a regular old loop. 238

238

And so, to recap, we do the counting, 239

239

we just get the raw counts of how many values 240

240

have a specific digit at the position we're working at. 241

241

We then adjust those counts. 242

242

As we saw in the slides in the last video, 243

243

we then write the values into a temporary array 244

244

as we saw in the slides in the last video 245

245

and in the final step, we copy the temporary array 246

246

back into the input array 247

247

and then we return from this method 248

248

and then we return here to radixSort, 249

249

the values have been sorted based on that position. 250

250

And as you can see, we're going from zero, 251

251

one, two, three, four, five et cetera 252

252

depending on the width, 253

253

zero is the rightmost position, 254

254

it's the least significant digit. 255

255

That's how this getDigit method operates 256

256

because it raises 10 to the position. 257

257

Actually there's a mistake here. 258

258

This should be radix. 259

259

So, the final thing that we have left to do 260

260

is to actually call this method, 261

261

so we're gonna call radixSort 262

262

and we're gonna pass it our radixArray, 263

263

that's our input array, our radix is 10 264

264

and our width is four and let's run. 265

265

And we have 1330, 1594, 266

266

4586, 4725, 267

267

5729 and 8792. 268

268

We have sorted our array 269

269

and remember that the key thing here 270

270

is this has to be a stable sort 271

271

and so, that's why we're doing these extra steps. 272

272

We need a stable counting sort here, 273

273

an unstable counting sort will not work 274

274

because it would undo previous sorts 275

275

when we've sorted on less significant digit positions, 276

276

so we've done extra work here 277

277

to make our counting sort stable 278

278

and because of that, our radixSort 279

279

is able to sort these values. 280

280

So, that's it for sorting algorithms right now. 281

281

We're gonna see a few more later in the course 282

282

after we've covered some more data structures 283

283

because they make use of those data structures 284

284

but for now that's it, so I'll see you in the next video.