Original subtitles

1 1

The algorithms we've looked at so far 2

2

don't make any assumptions about the data they're sorting. 3

3

We can sort integers, floats, strings, objects anything. 4

4

The algorithms don't assume a certain data type. 5

5

Specific implementations do 6

6

but not the algorithms themselves. 7

7

They also don't assume that the data being sorted 8

8

is bound in any way. 9

9

For example, they don't assume that all the values 10

10

being sorted will be less than 100. 11

11

There are algorithms that do make assumptions 12

12

about the data being sorted 13

13

and because they make assumptions 14

14

they can sort the data more efficiently. 15

15

In fact they can achieve linear time, O to the N complexity 16

16

and so the next couple of algorithms we're going to look at 17

17

make assumptions about the data they're sorting 18

18

and the first algorithm is called counting sort. 19

19

So counting sort makes assumptions 20

20

about the data that it's sorting, 21

21

it assumes that all the values are discrete 22

22

and they're within a specific range. 23

23

So this algorithm only works 24

24

with non-negative discrete values. 25

25

We can't sort floating point numbers, we can't sort strings 26

26

because they don't have discrete values. 27

27

So practically speaking, you'll usually use 28

28

this algorithm with whole numbers. 29

29

So the way it works is it doesn't use comparisons, 30

30

so it doesn't actually compare values 31

31

in the array against each other 32

32

instead it counts the number of occurrences of each value 33

33

and you'll see how it does this 34

34

when we go through the algorithm 35

35

for a specific array in just a minute. 36

36

Now as I said, values must be within a specific range 37

37

and the range has to be reasonable. 38

38

It can't be huge. 39

39

You're not going to use counting sort 40

40

to sort values that are between 41

41

one and a million, for example. 42

42

Now our array, the usual array that we've been using, 43

43

is not a good candidate for counting sort. 44

44

It has negative numbers, so we're going to use a different 45

45

array to go through this algorithm by hand 46

46

and so this is the array we're going to use. 47

47

We're going to assume that we're sorting values 48

48

that are between one and 10 inclusive, 49

49

so the values can be one, two, three, four, 50

50

five, six, seven, eight, nine or 10. 51

51

We have 10 possible values and so what we do 52

52

is we create a counting array of length 10. 53

53

So this is going to be a separate array 54

54

from the one that we're sorting 55

55

and then we traverse the input array, 56

56

the one we're sorting, from left to right 57

57

and using the counting array we track how many 58

58

of each value are in the input array 59

59

and then once we've traversed the entire input array, 60

60

using the counts in the counting array, 61

61

we write the values in sorted order back to the input array. 62

62

And so we're going to sort the array 63

63

that you see on the screen 64

64

and so when i = 0, we're going to look 65

65

at the value at position zero and we see it's two 66

66

and so we add one to the counting array at position one 67

67

because we know the values are between one and 10, 68

68

in the counting array position zero 69

69

is going to hold the number of one's we find. 70

70

Position one will hold the number of two's we find. 71

71

Position two will hold the number of three's we find etc 72

72

and so in the first position we found a two 73

73

so we increment counting array index one, 74

74

we increment it by one. 75

75

Then we're going to increment i to one 76

76

and at the input array position one we have a five 77

77

so we're going to increment counting array four 78

78

because that's where we're counting the number of fives. 79

79

We increment i to two, we have a nine, 80

80

so we're going to increment counting array 81

81

position eight by one because we found one nine. 82

82

When i is three we have an eight, 83

83

so we're going to increment counting array seven by one. 84

84

At position four we found another two 85

85

and so we're going to increment counting array one by one, 86

86

so now we have two there because 87

87

so far we've seen two two's in our array. 88

88

Next we find another eight, so counting array seven 89

89

will be incremented by one so we now have a two there 90

90

because we've seen two eight's. 91

91

Then we find a seven so we're going to 92

92

increment counting array six. 93

93

We found a 10 so we're going to 94

94

increment counting array nine. 95

95

We found a four, so we going to 96

96

increment counting array three 97

97

and finally we find a three 98

98

and so we're going to increment counting array two by one. 99

99

And so at this point we've traversed our entire input array 100

100

and we have counted how many occurrences 101

101

of each value we've seen 102

102

and so what we want to do now is using the counting array, 103

103

we're going to write back the values to the original array. 104

104

So in this slide the counting array is at the top 105

105

and the input array is at the bottom, 106

106

after we've written it back. 107

107

So the way this would work is, 108

108

we'd traverse the counting array 109

109

and we would say okay so there is zero one's 110

110

and so we don't have to do anything. 111

111

We just move to the next position in the counting array. 112

112

Okay there's two two's 113

113

and so at this point we're gonna write 114

114

two two's into the input array 115

115

and then there's one three 116

116

so we'll write one three to the input array. 117

117

There's one four so we'll write one four to the input array. 118

118

There's one five so we'll write one five to the input array. 119

119

There are zero sixes, so we don't do anything. 120

120

There is one seven, so we write 121

121

one seven to the input array. 122

122

There are two eights, so we're gonna write 123

123

two eight's to the input array. 124

124

There's one nine, so we write one nine to the input array 125

125

and finally there's one 10 126

126

and so we write one 10 to the input array. 127

127

So essentially counting sort has two phases. 128

128

The first phase is we traverse the input array 129

129

and we count how many of each value we have 130

130

and then in the second phase using the counting array, 131

131

we write values back into the input array 132

132

and so as you can see our input array is now sorted 133

133

and we didn't do any comparisons. 134

134

We didn't compare any of the elements against each other. 135

135

We're just merely counting, how many of each value we have 136

136

and that's why the algorithm is called counting sort. 137

137

Now this is not an in-place algorithm. 138

138

As we've seen we have to create a counting array 139

139

and the length of the counting array 140

140

will depend on the range of values we have, 141

141

and because of this counting sort is best used, 142

142

when the range of values you have 143

143

is around the same length of the input array. 144

144

So if you have an input array of 20, 145

145

ideally the number of values that there are, 146

146

you want to be that to be around 20 147

147

because think about if you have an array of 10 elements 148

148

and the range of values can go from one to 10,000, 149

149

then your going to have to create a counting array 150

150

of length 10,000 to sort 10 elements 151

151

which would obviously be ridiculous. 152

152

So counting sort works best when 153

153

the range of values that you can have, 154

154

the number of values in that range 155

155

is roughly equivalent to the number of values 156

156

that you want to sort. 157

157

So in our case we had a range of 10 values 158

158

and we had an array of 10 so it was perfect. 159

159

As I mentioned this algorithm can achieve linear time 160

160

and it can do that because it's making 161

161

assumptions about the data 162

162

and so because it can make these assumptions, 163

163

it can achieve linear time. 164

164

Now the counting sort I showed you is unstable. 165

165

If we want it to be stable there are extra steps 166

166

we can take with counting sort 167

167

instead of just incrementing a counter for example 168

168

you would perhaps use what's called linked list 169

169

in the counting array, we're gonna cover linked list later. 170

170

Okay that's it for learning what 171

171

the counting sort algorithm is. 172

172

Let's go ahead and implement it. 173

173

I'll see you in the next video.