All language subtitles for 16. Counting Sort (Theory)

The algorithms we've looked at so far
2

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

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

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

Specific implementations do
6

but not the algorithms themselves.
7

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

is bound in any way.
9

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

being sorted will be less than 100.
11

There are algorithms that do make assumptions
12

about the data being sorted
13

and because they make assumptions
14

they can sort the data more efficiently.
15

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

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

make assumptions about the data they're sorting
18

and the first algorithm is called counting sort.
19

So counting sort makes assumptions
20

about the data that it's sorting,
21

it assumes that all the values are discrete
22

and they're within a specific range.
23

So this algorithm only works
24

with non-negative discrete values.
25

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

because they don't have discrete values.
27

So practically speaking, you'll usually use
28

this algorithm with whole numbers.
29

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

so it doesn't actually compare values
31

in the array against each other
32

instead it counts the number of occurrences of each value
33

and you'll see how it does this
34

when we go through the algorithm
35

for a specific array in just a minute.
36

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

and the range has to be reasonable.
38

It can't be huge.
39

You're not going to use counting sort
40

to sort values that are between
41

one and a million, for example.
42

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

is not a good candidate for counting sort.
44

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

array to go through this algorithm by hand
46

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

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

that are between one and 10 inclusive,
49

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

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

We have 10 possible values and so what we do
52

is we create a counting array of length 10.
53

So this is going to be a separate array
54

from the one that we're sorting
55

and then we traverse the input array,
56

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

and using the counting array we track how many
58

of each value are in the input array
59

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

using the counts in the counting array,
61

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

And so we're going to sort the array
63

that you see on the screen
64

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

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

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

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

in the counting array position zero
69

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

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

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

and so in the first position we found a two
73

so we increment counting array index one,
74

we increment it by one.
75

Then we're going to increment i to one
76

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

so we're going to increment counting array four
78

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

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

so we're going to increment counting array
81

position eight by one because we found one nine.
82

When i is three we have an eight,
83

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

At position four we found another two
85

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

so now we have two there because
87

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

Next we find another eight, so counting array seven
89

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

because we've seen two eight's.
91

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

increment counting array six.
93

We found a 10 so we're going to
94

increment counting array nine.
95

We found a four, so we going to
96

increment counting array three
97

and finally we find a three
98

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

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

and we have counted how many occurrences
101

of each value we've seen
102

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

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

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

and the input array is at the bottom,
106

after we've written it back.
107

So the way this would work is,
108

we'd traverse the counting array
109

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

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

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

Okay there's two two's
113

and so at this point we're gonna write
114

two two's into the input array
115

and then there's one three
116

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

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

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

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

There is one seven, so we write
121

one seven to the input array.
122

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

two eight's to the input array.
124

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

and finally there's one 10
126

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

So essentially counting sort has two phases.
128

The first phase is we traverse the input array
129

and we count how many of each value we have
130

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

we write values back into the input array
132

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

and we didn't do any comparisons.
134

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

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

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

Now this is not an in-place algorithm.
138

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

and the length of the counting array
140

will depend on the range of values we have,
141

and because of this counting sort is best used,
142

when the range of values you have
143

is around the same length of the input array.
144

So if you have an input array of 20,
145

ideally the number of values that there are,
146

you want to be that to be around 20
147

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

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

then your going to have to create a counting array
150

of length 10,000 to sort 10 elements
151

which would obviously be ridiculous.
152

So counting sort works best when
153

the range of values that you can have,
154

the number of values in that range
155

is roughly equivalent to the number of values
156

that you want to sort.
157

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

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

As I mentioned this algorithm can achieve linear time
160

and it can do that because it's making
161

assumptions about the data
162

and so because it can make these assumptions,
163

it can achieve linear time.
164

Now the counting sort I showed you is unstable.
165

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

we can take with counting sort
167

instead of just incrementing a counter for example
168

you would perhaps use what's called linked list
169

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

Okay that's it for learning what
171

the counting sort algorithm is.
172

Let's go ahead and implement it.
173

I'll see you in the next video.