Original subtitles

1 1

(upbeat music) 2

2

(typing) 3

3

I said in the last video 4

4

that we were gonna move on 5

5

to the implementation of radix sort, 6

6

but when I was looking over the implementation, 7

7

I thought it would be helpful to go through 8

8

the stable counting sort that we're going to use first, 9

9

before we actually get to the implementation. 10

10

So that's what we're gonna do in this video. 11

11

So as I said in the video about counting sort, 12

12

the implementation that I showed you was unstable. 13

13

If you want it to be stable, we have to do some extra work. 14

14

Now the implementation that I'm going to show you calculates 15

15

where values should be written back to the original array, 16

16

and then by writing the values into the array 17

17

in backwards order, we get stability, 18

18

and I think probably going through the slides 19

19

will make this clear. 20

20

In the last video, we went through sorting this array, 21

21

and I'm going to go through the stable counting sort 22

22

for when we sort the array based on the 10's position. 23

23

And so if you look at the last video, 24

24

we've already sorted based on the one's position, 25

25

and we end up with the array on the screen, 26

26

and now we're going to sort this array 27

27

based on the 10's position, 28

28

and the reason we're looking at the 10's 29

29

is because the 10's actually have some duplicate values. 30

30

So 1594 31

31

has to remain after 8792 32

32

after the sort, 33

33

and 5729 34

34

has to remain after 4725, 35

35

'cause the sort has to be stable. 36

36

So how are we gonna accomplish this using counting sort. 37

37

So what we do, is we do the count just as we did before, 38

38

and we're gonna end up with the counting array below. 39

39

So we have two values that have two in the 10's position, 40

40

4725 and 5729, 41

41

1330 has a three in the 10's position, 42

42

and then we don't have any fours, fives, sixes, or sevens 43

43

in the 10's position. 44

44

4586 has eight in the 10's position, 45

45

and then we have two values 46

46

with nine in the 10's position, 47

47

8792 and 1594, 48

48

and so our counting array is what you see in the bottom, 49

49

zero, zero, two, one, zero, zero, zero, zero, one, two, 50

50

and so that tells us we have two values with a two 51

51

in the 10's position, 52

52

one value with three in the 10's position, 53

53

one value with eight in the 10's position, 54

54

and two values with nine in the 10's position, 55

55

and that's all fine and dandy 56

56

but how are we gonna write these values back? 57

57

'Cause we don't actually have the values 58

58

in the counting array, 59

59

and on top of that, we want the sort to be stable. 60

60

And so what we're gonna so is we're going to create 61

61

a temporary array that matches the length 62

62

of the array we're sorting. 63

63

And so we're going to create 64

64

a temporary array of length six, 65

65

because we're sorting six values. 66

66

And we can use the counts to figure out 67

67

which range of indices in the temporary array 68

68

will be occupied by each value. 69

69

For example, 70

70

because we don't have any zeros 71

71

in the 10's position and any ones, 72

72

we know that the two values that have a two 73

73

in the 10's position are going to occupy 74

74

positions zero and one in the sorted array. 75

75

And then we have one value with a three 76

76

in the 10's position, 77

77

so we know that'll go into position two. 78

78

And then we don't have any values 79

79

with four, five, six, and seven, 80

80

but we have one value with an eight, 81

81

so we know that's going to go into position three, 82

82

and then positions four and five are gonna hold 83

83

the two values that have a nine in the 10's position. 84

84

So because we know how many values we're sorting, 85

85

and because we know how many of each value 86

86

have a specific digit in their 10's position, 87

87

we can figure out what range of positions the values 88

88

with a specific digit in the 10's position are gonna occupy. 89

89

The way that we figure out these ranges is 90

90

after we've done our first counting pass, 91

91

and we've ended up with our usual counting array, 92

92

we adjust the counts. 93

93

So instead of just keeping the number of values 94

94

that have a specific 10's digit, 95

95

we want to store how many values 96

96

have a specific 10's digit or less. 97

97

So for example, at index three in the counting array, 98

98

which currently contains the number of values 99

99

that have a three in the 10's position. 100

100

Instead of that, we want to know how many values 101

101

have three or less in the 10's position, 102

102

and in this case that's three values right? 103

103

Because we have two values that have two 104

104

in the 10's position 105

105

and one value that has three in the 10's position, 106

106

and so we have three values 107

107

that have a three or less in the 10's position. 108

108

And we can calculate how many values 109

109

have a specific digit or less by summing up 110

110

all the counts that come before it. 111

111

And so for example, by summing up zero, zero, two, and one, 112

112

we get three, and that's how many values 113

113

have a three or less in the 10's position, right? 114

114

Because we don't have any values with zero, 115

115

we don't have any values with one, 116

116

we have two values with two and one value with three. 117

117

And so after we've adjusted our counts, this is what we get. 118

118

So we don't have any values with zero. 119

119

We don't have any values with one or less. 120

120

We have two values with two or less. 121

121

We have three values with three or less, 122

122

and then three values with four or less, 123

123

three values with five or less. 124

124

Up to the value for eight, 125

125

where we have four values that have eight or less, 126

126

and then finally we have six values with nine or less, 127

127

and that last position 128

128

is always gonna basically equal the number of values we have 129

129

because everything in the array is gonna have 130

130

the highest possible digit or letter, or less. 131

131

And so this is our adjusted count array, 132

132

where each element, instead of containing the exact count 133

133

of how many values 134

134

have a specific digit in their 10's position, 135

135

instead it contains a count 136

136

of how many values have that digit or less. 137

137

And now we're going to use that 138

138

to write back to our input array. 139

139

So the code at the top is what we're going to use. 140

140

So we initialise our temp array, 141

141

and n is the number of elements we're sorting. 142

142

So we'll have a temp array of length six. 143

143

And then, we traverse the array backwards. 144

144

So we traverse the array from right to left, 145

145

because this is going to make us write 146

146

the rightmost values before the leftmost values 147

147

and that's what's going to ensure stability. 148

148

And so we start with n of six, 149

149

k is gonna go from five to zero. 150

150

So when k is five, 151

151

we're going to get the digit in the 10's position, 152

152

that's what that getDigit method is doing, 153

153

and we're going to get it for input k, 154

154

and k is starting at five. 155

155

So if we go back, 156

156

that's 5729. 157

157

We're going to look at countArray[2], 158

158

because we're going to figure out that 159

159

the getDigit call is going to return two. 160

160

And so we're gonna index countArray[2], 161

161

and we're using the prefix operator 162

162

so we're gonna subtract one from countArray[2], 163

163

that's gonna give us one. 164

164

And then we're going to assign input k, 165

165

which we just saw back here is 5729. 166

166

We're gonna assign that into tmp[1]. 167

167

So let's go through that one more time. 168

168

We're going to get the digit 169

169

of input five, 170

170

the 10's digit, 171

171

and that digit is two, 'cause we're dealing with 5729. 172

172

And then we're going to decrement the value at countArray[2] 173

173

which is gonna give us one. 174

174

And then we're going to use that result as the index 175

175

into our temp array. 176

176

So we're gonna assign input of k, input five, 177

177

which is 5729, 178

178

into temp at position one. 179

179

And so we're gonna end up with this situation, 180

180

where we have 5729 181

181

in the temp array. 182

182

So now we have the temp array at the top, 183

183

and our count array at the bottom. 184

184

Now we've decremented countArray[2] by one, 185

185

because we're written one value 186

186

with two in the 10's position, 187

187

and notice that it's gone into temp array one. 188

188

And so the second value that has two 189

189

is gonna go into temp array zero. 190

190

And because we're going right to left in the input array, 191

191

we're writing rightmost values before leftmost values. 192

192

So that means if we have a duplicate, 193

193

the rightmost duplicate will be written 194

194

to the right of the leftmost duplicate, 195

195

and that's what's preserving the stability. 196

196

And so now k is gonna get decremented to four. 197

197

We're gonna be handling value 4586. 198

198

The 10's digit is eight. 199

199

So we're gonna decrement countArray[8] by one, 200

200

which will give us three, 201

201

and so we're gonna assign 4586 into temp at position three. 202

202

And we're gonna end up with this situation. 203

203

So 4586 has gone into the temporary array at position three, 204

204

and countArray[8] is now three, 205

205

because we've decremented it by one 206

206

'cause we've written out one value was eight 207

207

in the 10's position. 208

208

So now k will be three, so we're gonna be handling 4725, 209

209

that has a two in the 10's position. 210

210

We're gonna decrement countArray[2] 211

211

so that's gonna become zero. 212

212

And so we're gonna assign 4725 to temp zero. 213

213

And so this is our array, 214

214

and notice that we have preserved the relative positions 215

215

of 4725 and 5729, 216

216

because we're going right to left. 217

217

So when we write the rightmost duplicate value, 218

218

we write that value into the rightmost position 219

219

of the set of positions for that 10's value. 220

220

And so we knew that the two values 221

221

that have a two in the 10's position 222

222

were gonna occupy positions zero and one. 223

223

And so we write the rightmost value in the original array 224

224

into position one, 225

225

and the leftmost value into position zero. 226

226

And by doing that we have preserved the relative positions. 227

227

So this is a stable sort. 228

228

And you'll notice now that countArray[2] is zero 229

229

because we've now written out both values 230

230

with two in the 10's position. 231

231

So now when k equals two, 232

232

we're gonna be handling value 1594, 233

233

it has a nine in the 10's position 234

234

so we're gonna decrement countArray[9]. 235

235

It'll become five, 236

236

and then we assign 1594 to temp five. 237

237

And so the rightmost value with nine 238

238

is being written in the rightmost position, 239

239

for values that have nine in the 10's position. 240

240

k will be one, we'll handle 8792. 241

241

We decrement countArray[9] to four, 242

242

and we assign 8792 to temp four, 243

243

and we have preserved 244

244

the relative positions of 8792 and 1594. 245

245

And then finally k will be zero, we'll handle 1330. 246

246

We'll subtract one from countArray[3] to get two, 247

247

and we'll write 1330 to position two in the temporary array. 248

248

And there we go, 249

249

we have completed our sort of the values 250

250

based on the 10's position, 251

251

and the relative positioning of any duplicates 252

252

have been preserved. 253

253

And so this is a stable counting sort. 254

254

It works because we traverse 255

255

the input array from right to left, 256

256

and we write duplicate values 257

257

into the temp array from right to left. 258

258

So if we know that duplicate values will go into, 259

259

let's say positions three and four, 260

260

we write the rightmost value in the input array 261

261

into position four 262

262

and the leftmost value into position three, 263

263

and this preserves the relative positioning 264

264

of duplicate values. 265

265

And so by adjusting the counting array 266

266

after the initial pass, 267

267

so that we, instead of storing just the raw counts, 268

268

instead we store how many values 269

269

have that value or less. 270

270

So for us, it was how many values 271

271

have a specific digit or less in the 10's position. 272

272

We can use those adjusted counts 273

273

to map values back to indices in the temp array. 274

274

Now another way of doing this 275

275

is to use something called linked lists, 276

276

we haven't covered those yet. 277

277

We'll be covering those soon. 278

278

But another way of doing this, 279

279

is instead of just using counts the way that we did, 280

280

you can actually store a list of the actual values 281

281

at each position in a count array, 282

282

and then you write the list out backwards. 283

283

So we're not gonna cover that, 284

284

because we haven't covered linked lists yet, 285

285

but that's another way that you could do it. 286

286

Now obviously we've sorted into a temporary array, 287

287

so at this step here the top array is a temporary array. 288

288

So obviously there would be one more step, 289

289

and that would be copying the temporary array 290

290

back into the input array. 291

291

Okay so that's it for the stable counting sort. 292

292

The code up here is the code 293

293

that we're actually gonna use in the implementations. 294

294

So now that you've seen it, 295

295

when we code the implementation, I won't have to spend time 296

296

trying to explain to you what's going on, 297

297

and not having any slides to do it. 298

298

So I thought that having slides and going through it 299

299

would make it easier for you to understand. 300

300

So now finally, 301

301

let's move on to the implementation of radix sort. 302

302

I'll see you in the next video.