Original subtitles

1 1

(lively music) (keyboard clacking) 2

2

So, let's implement counting sort. 3

3

Once again I've created a project, 4

4

I've got the code in package 5

5

academy.learnprogramming.countingsort. 6

6

And I'm going to write a method called countingSort. 7

7

So, I'll say public static void countingSort 8

8

and we're going to accept the input array 9

9

and the minimum value in the range 10

10

and the maximum value in the range. 11

11

Remember, that countingSort assumes 12

12

that all the values fall within the range min to max. 13

13

So, the first thing we're going to do 14

14

is to create the counting array, 15

15

the array that's going to keep track of the count, 16

16

so we'll say int countArray 17

17

and this array has to be large enough 18

18

to be able to count each possible value 19

19

and so, we're gonna say new int 20

20

and we want it to be max minus min plus one in length. 21

21

If our minimum is one, and our maximum is 10, 22

22

which is what we're going to pass in, 23

23

then we're going to create an array of length 10 24

24

minus one which is nine plus one which is 10 25

25

and that's what we want 26

26

because we have a possible 10 values, 27

27

one to 10 inclusive. 28

28

So, once we've created our countArray, 29

29

what do we wanna do? 30

30

We want to traverse our input array 31

31

and here's our input array up here, 32

32

it's not our usual array, 33

33

it's the aray that we went through in the slides. 34

34

And so, we're gonna traverse this array 35

35

and we're gonna count how many of each value we have. 36

36

And so, we're gonna say for int i equals zero, 37

37

i less than input.length, 38

38

i++ and we're gonna say countArray 39

39

and the way that we figure out 40

40

where each value is counted 41

41

is we say input i minus min. 42

42

That's going to be the index 43

43

of where to count each value. 44

44

So, for example, let's say input i 45

45

is equal to five, 46

46

so let's say we're at the point 47

47

where we're counting this one. 48

48

To figure out which element we should increment 49

49

in the countArray, we would say five minus one 50

50

because that's our minimum 51

51

and so, we'd increment count array four 52

52

because remember, we could have values let's say going 53

53

from 10 to 20 54

54

and in that case, the countArray would be 11 elements long 55

55

and so, we need to translate the values 10 to 20 56

56

to indices zero to 10 57

57

and that's what we're doing here 58

58

and we can do that just by subtracting out the minimum 59

59

from whatever value we're counting 60

60

and so, to count ones, 61

61

if we got a one, we'd subtract one minus one, 62

62

so we'd increment element zero. 63

63

If we got a two, two minus min is one 64

64

and so, we'd increment element one. 65

65

If we got a 10, 10 minus one is nine 66

66

and we'd increment element nine in the countArray. 67

67

And so, all this is doing 68

68

is translating the value we wanna count 69

69

into its index in the countArray. 70

70

And what do we wanna do? 71

71

We wanna increment that position 72

72

and so, that's all we do here. 73

73

So, this is the counting phase. 74

74

That's all it involves. 75

75

We go through each element in the array, 76

76

we look at the value, 77

77

we figure out where we're counting that value 78

78

in the countArray 79

79

and we increment that value by one. 80

80

So, once we've finished counting, 81

81

we now wanna write the values back into the input array, 82

82

so we're gonna say int j equals zero 83

83

and then for int i equals min, 84

84

i less than or equal to max. 85

85

I++. 86

86

So, what are we doing here? 87

87

J is the index we're going to use 88

88

to write to the input array. 89

89

And i is the index that we're going to use 90

90

to traverse the countArray. 91

91

We're setting i to min 92

92

and i less than or equal to max 93

93

because as you'll see, 94

94

because we're doing it this way, 95

95

we can just write the value of i back 96

96

to the input array on each iteration. 97

97

So, inside the loop, we're gonna say while countArray 98

98

i minus min 99

99

is greater than zero. 100

100

And you'll see why in a minute. 101

101

Let me write the rest of the code. 102

102

So, we'll say input j++ equals i 103

103

and countArray i minus min minus minus. 104

104

So, what's going on here? 105

105

What we're doing here 106

106

is remember that each element in the countArray 107

107

has a count and that count can be greater than one. 108

108

So, let's go through this for the number of twos 109

109

because we know we have two twos in our array 110

110

and the count of twos is kept in countArray one. 111

111

So, when i is two, 112

112

we say while countArray two minus one 113

113

which is countArray one is greater than zero, 114

114

we wanna keep writing twos to the input array 115

115

because at this point, we're writing the number of twos. 116

116

And so, the first thing we do 117

117

is we write a two 118

118

to the input array 119

119

and then we need to decrement the count. 120

120

We've already written one two 121

121

and so, we only have another two left to write 122

122

and so, we started with countArray one equals two 123

123

because we have two twos, 124

124

we write one of the twos to the input array 125

125

and then we decrement the count to one 126

126

because we only have one two remaining. 127

127

We loop around, countArray one is still greater than zero, 128

128

so we're gonna write another two 129

129

and then we're gonna decrement the count again 130

130

and at this point, the count will be zero 131

131

because we've written both of the twos 132

132

back to the input array 133

133

and so, when we loop back around, 134

134

at this point countArray one will be equal to zero 135

135

and we drop out of the loop 136

136

and then i will be incremented to three 137

137

and we enter this loop to write the number of threes 138

138

and once again, each time we write a three, 139

139

I don't believe we have any, 140

140

we do, one at the end, so each time we write a three, 141

141

the count will be decremented by one 142

142

until we've written all the threes 143

143

and then we'll loop around and we'll write the fours. 144

144

So, we've written the loop this way 145

145

starting i at min because then we can just 146

146

when we're writing out the number of ones, 147

147

i will be one, 148

148

when we're writing out the number of twos, i will be two. 149

149

So, we can just stick i in 150

150

and subtract here. 151

151

We could have started i at zero 152

152

but then we'd need to do a different type 153

153

of calculation here. 154

154

We'd need to figure out what value we're writing. 155

155

So, I think it's clear to set i to min 156

156

because then we know that on the first iteration 157

157

we're writing out one, 158

158

the second iteration we're writing the twos, 159

159

the third iteration we're writing the threes et cetera. 160

160

And of course j is keeping track 161

161

of where we are in the input array. 162

162

So, this is a fairly straightforward algorithm I would say. 163

163

If you're having trouble understanding it, 164

164

you can go and check the slides 165

165

but of course we wanna see if it works, 166

166

so let's call countingSort 167

167

and we'll call it with intArray, 168

168

our minimum value is one, 169

169

and our maximum value is 10, 170

170

so let's go ahead and run. 171

171

And here we go. 172

172

Two, two, three, four, five, 173

173

seven, eight, eight, nine and 10. 174

174

Exactly what we expect. 175

175

And so, that's countingSort 176

176

and once again, this algorithm 177

177

is only good to use under specific circumstances. 178

178

You only wanna use it when the range 179

179

of values is reasonable, 180

180

meaning it's not too large 181

181

and the dataset is a reasonable size as well. 182

182

So, ideally the number of unique values 183

183

or the range won't be significantly greater 184

184

than the number items you wanna sort. 185

185

So, as I said earlier, 186

186

if you have an array of length 10 187

187

and it can hold values from one to a million, 188

188

that's not a good candidate for counting sort 189

189

because you're gonna have to create a counting array 190

190

of length a million to sort 10 items 191

191

and obviously that wouldn't be a very good idea. 192

192

I'll see you in the next video.