Original subtitles

1 1

(lively music) (keyboard clacking) 2

2

In this video, we're going to take a look 3

3

at the Radix Sort and this is another sort algorithm 4

4

that makes assumptions about the data it's sorting 5

5

and in this case, the assumptions that it makes 6

6

is that the data has the same radix and width. 7

7

Now, what do I mean by that? 8

8

The radix is the number of unique digits 9

9

or values in the case of characters 10

10

that a numbering system or an alphabet has. 11

11

For example, the radix for the decimal system is 10 12

12

because there are 10 possible digits 13

13

in the decimal system. 14

14

Zero to nine. 15

15

For binary numbers, the radix is two 16

16

because we use two digits in the binary system, zero and one 17

17

and for the English alphabet, the radix is 26 18

18

because there are 26 letters in the alphabet. 19

19

So, that's what we mean by radix. 20

20

Now, by width I mean the number of digits 21

21

or letters, for example, the number 1235 22

22

has a width of four. 23

23

The string hello has a width of five. 24

24

The number 10 has a width of two. 25

25

So, 1,235 or 1235 has four digits, 26

26

so it has a width of four, 27

27

the string hello has five letters, so it has a width of five 28

28

and the number 10 has two digits 29

29

and so, it has a width of two. 30

30

And so, the radix sort assumes 31

31

that all the values have the same radix and the same width 32

32

and so, that means that we can use the radix sort 33

33

to sort integers and strings. 34

34

The decimal point isn't a digit 35

35

and so, floating point numbers can't be sorted 36

36

using radix sort. 37

37

So, how does it work? 38

38

Well, we sort based on each individual digit 39

39

or letter position and you'll see what I mean 40

40

when we go through the algorithm on the slides. 41

41

So, we start at the rightmost position 42

42

and we sort based on that position, 43

43

the digit or the letter at that position 44

44

and then we move to the rightmost minus one digit 45

45

or letter and we sort based on that 46

46

and we keep doing that 47

47

until we've done all of the digits or letters 48

48

in the values. 49

49

Now, the important point here 50

50

and this is key, this is an absolute important point, 51

51

is we have to use a stable sort algorithm 52

52

at each stage, so when we sort the values based 53

53

on the rightmost position, 54

54

we have to use a stable sort algorithm. 55

55

And then when we sort the values based 56

56

on the rightmost minus one position, 57

57

we have to use a stable sort algorithm 58

58

and once again, you'll understand why 59

59

when we take a look at going through the algorithm. 60

60

So, let's do that now. 61

61

So, we have a different array here now 62

62

at the top of the screen. 63

63

It's got six integers in it 64

64

and you'll notice that they're all decimal numbers 65

65

and they're all of width four. 66

66

They all have four digits 67

67

and so, we can sort this array using the radix sot. 68

68

First we're going to sort this array 69

69

based on the one's position 70

70

and so, let's take a look at the first value, 71

71

4725, the number five is in the one's position 72

72

and for the second value, 73

73

4586, the number six is in the one's position 74

74

and so, what we're doing here 75

75

is we're sorting by the digit 76

76

that has the least weight 77

77

because the one's position has the least weight 78

78

in a decimal number 79

79

and so, once we've done that, 80

80

the bottom array will be the result. 81

81

1330 will come first 82

82

because it has zero in the one's position, 83

83

that'll be followed by 8792 84

84

because there's a two in the one's position. 85

85

Then we have 1594, 86

86

4725, 4586 and 5729 87

87

and if you look at their one's position 88

88

or the rightmost digit, 89

89

you'll see that the values have been sorted 90

90

according to what's in that position 91

91

and now we move to the second position 92

92

from the right or the second least significant digit 93

93

and we sort based on that. 94

94

And so, at the top is the array we just had 95

95

on the other slide 96

96

and now we're gonna sort based 97

97

on the second to last rightmost position. 98

98

So, for 1330 that will be three, 99

99

for 8792 it will be nine, 100

100

for 1594 it will be nine, 101

101

for 4725 it will be two et cetera 102

102

and so, down at the bottom, 103

103

we've now sorted based on that digit, 104

104

so we have 4725 'cause it has a two, 105

105

5729 which also have a two, 106

106

1330 'cause it has a three, 107

107

4586 because it has an eight 108

108

and then 8792 and 1594 both have nines. 109

109

Now, as I mentioned, 110

110

critically important, this is a stable sort 111

111

and so, you'll notice 112

112

that we have a couple of pairs of duplicates here, 113

113

4725 and 5729 114

114

both have twos in their rightmost digit minus one position 115

115

and you'll notice at the top 116

116

that 4725 came before 5729 117

117

and in the bottom, 4725 still comes before 5729 118

118

and that is critical 119

119

and that's because we have to use the stable sort algorithm 120

120

and the same thing goes for 8792 121

121

and 1594, they both have nines 122

122

in the second to right position 123

123

and in the top right, 8792 124

124

came before 1594 125

125

and it still does 126

126

and so, that's critical. 127

127

We have to use a stable sort algorithm. 128

128

So, now we're gonna sort based on the hundreds position. 129

129

So, we sorted here based on the tens position, 130

130

and now we're gonna sort based on the hundreds position 131

131

and so, when we do that, 132

132

1330 comes first 'cause it's got three in that position, 133

133

followed by 4586, 134

134

1594, 4725, 5729 135

135

and 8792 and once again, 136

136

we have to use a stable sort algorithm 137

137

and so, you'll notice here 138

138

that we have two fives in the hundreds position 139

139

and 4586 still comes before 1594 140

140

as it did in the top array 141

141

and we have three values with seven in the hundreds position 142

142

and the relative positions of those three values 143

143

have been preserved. 144

144

So, 4725 still comes before 5729 145

145

and that still comes before 8792 146

146

and then the final step is we sort based 147

147

on the thousands position. 148

148

And so, 1330 has a one, 1594 has a one, 149

149

4586 and 4725 both have fours 150

150

and then there's 5729 and 8792 151

151

and we have sorted our array. 152

152

Now once again, this had to be a stable sort 153

153

and so, 1330 had to come before 1594, 154

154

4586 had to come before 4725. 155

155

Now maybe you can understand at this point 156

156

why the sort has to be stable. 157

157

If it wasn't stable, this radix sort wouldn't work 158

158

because at each stage, for example, 159

159

in this stage, if 1594 could cross 1330, 160

160

we wouldn't get the correct sorted order. 161

161

If 4725 could end up before 4586, 162

162

we would not get the correct sorted order 163

163

and it's kind of interesting 164

164

because when we first start doing a sort, 165

165

it just means, you start to wonder, 166

166

how is this ever going to work? 167

167

Because when we sort on the one's position, 168

168

we got, we go back there, 169

169

we got a certain array 170

170

but then when we sorted on the 10 position, 171

171

all the elements are changing positions again 172

172

and you're wondering how is this ever going to end up 173

173

in sorted order? 174

174

But the key is we're sorting 175

175

from the least significant digit, 176

176

the one with the least weight 177

177

when it comes to the value 178

178

to the most significant digit 179

179

and at every phase, it's a stable sort. 180

180

And so, because of that, 181

181

as we move from right to left, 182

182

as we go from the least significant digit 183

183

to the most significant digit, 184

184

you'll see that a sorted order is starting to emerge 185

185

and then on the final step, 186

186

because it's a stable sort, 187

187

all of the previous sorts that we've done still count, 188

188

they don't get undone at each stage, 189

189

it kind of looks like we're not sorting at each stage 190

190

but we are, the data is gradually becoming more 191

191

and more sorted 192

192

and the fact that we're using a stable sort algorithm means 193

193

that on that final sort, 194

194

when we're sorting on the most significant digit, 195

195

values that have the same most significant digit 196

196

will not switch relative positions 197

197

and so, the values that have a higher hundreds, 198

198

a higher digit in the hundreds will remain 199

199

after values that have a lower digit in the hundreds 200

200

and the same will go when we do the sort with the tens. 201

201

When we do the sort based on the tens, 202

202

values that have a duplicate tens value, 203

203

well, the value with the higher digit in the one's position 204

204

will come after the value with the lower digit 205

205

in the one's position 206

206

and so, you can see 207

207

that because we're using a stable sort algorithm 208

208

at each phase 209

209

and we're going from the least significant digit 210

210

to the most significant digit, 211

211

or letter depending on what we're sorting, 212

212

the results of previous sorting phases are preserved 213

213

and that's why radix sort works. 214

214

So, counting sort is often used 215

215

as the sort algorithm for radix sort. 216

216

In the last video I said 217

217

that the implementation I showed you was not stable, 218

218

so when we implement radix sort, 219

219

you'll have a chance to see the stable version 220

220

of counting sort. 221

221

Now, once again, because radix sort makes assumptions 222

222

about the data, we can achieve linear time. 223

223

Even so, this often runs slower 224

224

than O to the nlog of n 225

225

because of the overhead involved 226

226

and by overhead, 227

227

I mean that you have to isolate each individual digit 228

228

or letter at each phase 229

229

and so, there's overhead involved 230

230

just to figure out what value you're supposed to be sorting 231

231

at each phase and because of that, 232

232

even though it can achieve linear time, 233

233

it often runs a little bit slower than that. 234

234

Now whether or not it's in place 235

235

will depend on which sort algorithm you use 236

236

because as we've seen, some sort algorithms are in place 237

237

and some aren't. 238

238

So, radix sort can be in place 239

239

or it might not be place. 240

240

It's gonna depend on what sort algorithm you choose 241

241

to do the sorting at each phase. 242

242

It's a stable algorithm as we've seen 243

243

because the sort algorithm we use at each phase 244

244

has to be stable, radix sort turns out to be stable 245

245

and in fact, that's key to making it work 246

246

is that the sorts in earlier phases 247

247

aren't being undone as we sort based 248

248

on the more significant positions. 249

249

So, that's it for the theory. 250

250

Let's move onto implementation. 251

251

I'll see you in the next video.